（计算机软件与理论专业论文）基于skyline的一种改进的数据流查询算法的研究.pdf

啥尔滨工程大学硕士学位论文 i i i i i i i 摘要 随着信息技术的不断发展和应用，数据收集手段越来越丰富，海量存储 也越来越普遍。由此，一种新的操作算子s k y l i n e 查询被引入了数据库领域， 冒的是要查找数据集中不被其它点支配的所有点。s 姆l i n e 查询能够反映隧标 数据集的整体轮廓且有利于用户查询数据集中感兴趣的目标，从而在多目标 决策、数据挖掘、数据库可视化等方面有很大的应用。 c c s 算法是一种有效的数据流上的s k y l i n e 计算方法。它通过构造支配 关系树对整个s p 集合进行实时的维护，从而大大降低了s k y l i n e 计算的复杂 度。但该算法同样也存在一些弊端：其一，大量计算时对数据的利用不合理， 造成时间和空间的浪费；其二，进行查询计算的时候部分操作重复计算；其 三，没焉充分剩焉算法执行期闻已经产生豹s p 集合。 针对上述问题，本文给出了一种新的数据流上的s k y l i n e 查询模型，同时， 甜入了最近邻算法，结合最近邻算法在s k y l i n e 查询计算时的先天优势，对数 据元组提前进行预处理，通过去除不必要的对象来有效地减少资源的消耗。 同时采用了加权欧式距离的方法，在满足用户的偏好性也进行了一定程度上 的改进。最后对改进后的算法进行了验证实验，实验标明基于s k y l i n e 的改进 的数据流查询算法的研究在一定程度上降低了时空复杂度并且满足了用户一 定的偏好往。对改进后的算法进行仿真实验，验证算法的可行性，并通避在 相同环境下与原来算法的查询效率做对比，验证改进算法的优越性，同时针 对算法的特性，对不同数据类型进行验证，检验算法对各种数据类型的执行 效果。 关键词：数据流：s k y l i n e 计算；最近邻算法：支配 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t l lt h ec o n t i n u o u sd e v e l 6 p m e n ta n da p p l i c a t i o no ft h ei n f o r m a t i o n t e c h n o l o g y ，t h em e t h o d so f t h ed a t ec o l l e c t i o nb e c o m er i c h e ra n df i c h e r ，a n dm a s s m e m o r yb e c o m ec o l n l t l o n b a s e do nt h e s ef a c t s ，an e wo p e r a t o rc a l l e df o rs k y l i n e c o m p u t i n g ，w h i c hw a su s e dt of i n dt h ep o i n t sw h i c ha r e n td o m i n a t e db ya n y o t h e rp o i n ti nt h ed a t as e t ，h a db e e ni n t r o d u c e di n t od a t a b a s ef i e l d t h es k y l i n e c o m p u t i n ga a nd r a wap i c t u r eo ft h eo b j e c td a t a b a s e ，a n dh e l pt h eu s e r st of i n dt h e i n t e r e s t i n go b j e c t s a l s o ，i tc a np l a ya ni m p o r t a n tp a r ti nm u l t i o b j e c t i v ed e c i s i o n a n dd a t am i n i n ga n dd a t av i s u a l i z a t i o n ，a n ds oo n c c sa l g o r i t h mi sa ne f f e c t i v es k y l i n ec o m p u t i n go nt h ed a t as t r e a m w h i c h k e e p st h es ps e tb yt h ed o m i n a n c et r e e t h i sa l g o r i t h mc a ng r e a t l yr e d u c et h e s k y l i n ec o m p u t i n gc o m p l e x i t y ：, a l i s o ，c c sh a ss o m ed r a w b a c k s f i r s t ，i tm a y r e s u l tt h ew a s t eo ft h et i m ea n ds p a c ew h e nt h ed a t aq u a n t i t yi sl a r g e s e c o n d ，i t r e s u l t st h er e p e a t i n gc o m p u t i n g t h i r d ，i tc o u l d n tm a k ef u l lu s eo ft h es ps e t i nr e s p o n s et ot h e s eq u e s t i o n s ，t h i st h e s i se s t a b l i s h san e wd a t as t r e a mq u e r y m o d e lo ft h es k y l i n e a tt h es a m et i m e ，t h i sa l g o r i t h md e a l sw i t ht h ed a t aa h e a do f t i m eb yt h en e a r e s tn e i g h b o ra l g o r i t h m i tw i l le f f e c t i v e l yr e d u c et h er e s o u r c e t h r o u g hc u t t i n g o f fu n n e c e s s a r yo b j e c t s t h i s a l g o r i t h m m e e t st h el a s e r s p r e f e r e n c e sb yu s i n g t h e w e i g h t e de u c l i d e a n d i s t a n c em e t h o d f i n a l l y , t h e i m p r o v e da l g o r i t h mb a s e do nt h es k y l i n e c a nr e d u c et h et i m ea n ds p a c e c o m p l e x i t ya n dm e e tu s e r s p r e f e r e n c e sb yt h ee x p e r i m e n t s t h ee x p e r i m e n t s s h o wt h a tt h ei m p r o v e da l g o r i t h mi sv i a b l e t h ei m p r o v e da l g o r i t h mi sm o r e e f f e c t i v et h a nt h ea l g o r i t h mw l q i f i h i s n ti m p r o v e d a l s o ，t h ee x p e r i m e n t st e s tt h e e f f e c to ft h ed i f f e r e n td a t at y p e s k e y w o r d s ：d a t as t r e a m ；s k y l i n ec o m p u t i n g ；t h en e a r e s tn e i g h b o r sa l g o r i t h m ； d o m i n a n c e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本入独立完成的。有关观点、方法、数据和文献的弓 用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其健个人或集体已经公开发表的作最成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：御一 日期：多钟彳年3 月7 护曰 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：于庸一 导师( 签字) ：芊乡即 ， 、 日期： 沙呵年弓月矽目 0q 年3 月；q 日 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 近几年，随着经济发展和科技进步，在数据库的各个应用领域，数据产 生速度越来越快，数据以流的形式源源不断到达和动态变化的特征日益显现。 与传统数据库应用环境不同，这种新的应用背景数据更新的频率高得多、需 要动态处理的数据量也相对大得多、对实时性要求比较高。传统数据库管理 系统所处理的数据环境是静态的和较小规模的。研究能够适应新的数据流环 境下的数据模型成为一项迫切的需求。在这种情况下，数据流查询的研究逐 步兴起，并迅速成为引起关注的热点问题。 数据流上一类重要的查询就是连续查询。这种查询通常需要持续很长一 段时间，随着新数据的到来连续地进行评估，随时间的变化不断地产生结果。 基本的连续查询操作有选择、投影、t o p k 检测、聚集、多数据流的连接等 等。由于数据流上的数据量一般都是海量的，因此，这一类查询通常都是近 似查询，对数据的精确度不要求正确无误，只要求尽可能的接近正确值，但 对查询的结果要求不能出现错误的数据。 鉴于s k y l i n e 查询在多目标决策、数据挖掘、数据库可视化等很多方面的 潜在应用，越来越多研究者也开始关注s k y l i n e 查询。通过找到多维数据集中 那些不被任何其它点所支配的点集合，在保证数据精度的前提下删除不必要 的数据。常见的传统静态s k y l i n e 查询方法有d & c 、b n l 、b i t m a p 、n n 和 b b s 等方法。但这些算法对数据流应用不太适用，因为这些算法假设数据是 静态地存储在磁盘上的，而不是动态变化的。同时，算法每执行一次，只返 回一个s k y l i n e 值，并不是连续查询。算法不断地对s k y l i n e 进行维护和更新， 目的仅仅在于减少i o 费用，而不是考虑尽可能地减少对c p u 和内存资源的 占用。因而，研究有效地在数据流上的s k y l i n e 查询计算是一个的新课题。 哈尔滨工程大学硕士学位论文 1 2 国内外研究现状 s k y l i n e 计算是一个典型的多目标优化问题，早在2 0 世纪七十年代，就 以最大向量问题的形式出现。1 9 7 5 年k u n g 针对二维或三维数据提出了一种 查询复杂度为o ( n l o g ，2 ) 的算法，后来，b e n t l e y 在假定各维数据分布独立的 情况下，提出了人们期望的线性查询算法所有这些研究都假定数据量比较 小，可以放入内存，所提出的算法也都是内存算法。 2 0 0 1 年s k y l i n e 查询在数据库领域的研究开始展开，最早由b o r z s o n y i 等人提出，主要关注在数据量很大、无法放入内存的情况下如何处理s k y l i n e 计算。b o r z s o n y i 等提出b n l ”1 和d & c 。1 两种计算方法。b n l 可以应用到任意 维空间，无需建立索引，也不用对数据文件进行排序，但是它依赖主存，当 候选列表比主存还大时，需要将列表中的部分数据保存到临时文件中，导致 算法执行很多遍。d & c 方法在数据规模较小时具有较高的效率，遇到海量数 据的时候，频繁的划分合并过程会产生大量的i o 代价，不利于数据流上的 s k y l i n e 查询计算的推广。k o s s m a n n 等基于r - t r e e 索引结构提出的最近邻方 法n n 算法是渐进的、公平的，而且能够接受外界交互信息，从而按照不同 顺序生成s k y l i n e 集合，因此具有很好的灵活性。p a p a d i a s 分析了n n 方法在 i o 和存储方面存在的不足并对之进行了改进，提出b b s 算法”，并在理论上 证明了b b s 算法在数据流上的应用是i o 最优的。周红福研究了基于索引的 s k y l i n e 算法的研究b i ，该算法通过结合索引的优势，有效的改进了s k y l i n e 查询的效率。 鉴于s k y l i n e 计算在多规则决策上的广阔前景，近几年国内研究人员也开 始了对数据流上的s k y l i n e 计算展开了研究。王爱冬等人研究了分布式数据流 上的s k y l i n e 计算提出了一种过程丢弃算法”。该算法通过选择一个临界值， 对那些不可能满足s k y l i n e 查询条件的数据元组提前的处理掉，从而在一定程 度上节省了计算空间。田李等人针对更新的数据流提出了一种b u s h 算法。 该算法将更新过程看作是旧的位置点失效且增加一个新的位置点，并分别独 立处理。但是，由于它将一个更新元组引起的数据更新看成是旧点失效和新点 增加分别进行独立处理，因此会引入一些无谓的运算，加大了s k y l i n e 查询的 2 哈尔滨工程大学硕士学位论文 计算量。 分布式s k y l i n e 计算也在这几年开始进行开来。针对垂直划分的数据库， b a l k e 提出了基于f a g i n 的t a 算法，这是分布式数据库上的第一个s k y l i n e 计算算法。随着电子技术与无线通信的发展，越来越多具有存储和计算能力 的移动设备被使用，并组成了一个个移动自组织网络。移动自组织网络上 z h u a n g 提出m a n e t 算法l ，m a n e t 算法在传递s k y l i n e 查询的同时传递 一个过滤数据，帮助子节点提前去除非s k y l i n e 点，并将过滤数据动态更新。 然而，仅仅从已有的计算结果中筛选可能具有最大过滤能力的点并传送给所 有子节点，而没有考虑子节点本身存储数据的分布情况，这样的过滤数据缺 乏针对性，而过滤数据的个数固定为一个，也限制了算法的灵活性和过滤的 高效性。 其他的诸如对等网络等一系列分布式系统上的s k y l i n e 算法也渐渐的被 越来越多的人开始研究。由于s k y l i n e 查询计算涉及到的数据元组大都是高维 的，因此，研究人员们对s k y l i n e 计算在多个方面进行了扩展与探索。在高维 数据空间里，不同的用户可能对不同的维度感兴趣，子空间上的s k y l i n e 计算 成为了一个热门话题。s k y l i n e 计算从集中到分布，从静态到动态，从精确到 近似，从全空间到子空间的发展趋势。随着s k y l i n e 研究的成熟、拓展与深化， s k y l i n e 计算必将对信息科学的发展和人类社会的进步带来巨大的利益。 可以看出s k y l i n e 的查询处理尤其是数据流上的s k y l i n e 查询问题已经引 起了国内外研究者的高度重视，近几年，在s i g m o d ，v l d b ，k d d ，p o d s ， i c d e ，i c d m 等相关的高水平国际会议上发表了许多高质量的论文，展示出 大量的研究成果。在t k d e ，t o d s 等期刊中也发表了大量成果。 1 3 研究热点及难点 近年来，数据流技术己经发展成为现代数据库研究的主要方向之一。然 而数据流领域，尤其是涉及到数据流上的s k y l i n e 查询计算的领域还面临着诸 多挑战和研究问题。 1 近似查询 ( 1 ) 低空间复杂度：数据流规模在理论上是无限的。要保证数据流算法 3 哈尔滨工程大学硕士学位论文 持续稳定运行，其空间复杂度要非常小，并且要有有效的预防措施。如当前 数据流的长度是，则数据流算法的空间复杂度要求在o ( p l o y ( 1 0 9 n ) ) 之内。 在这种情况下，数据流算法的空间占用量的增长速度上远远小于数据流自身 规模增长的速度。 ( 2 ) 结果的精确度：数据流模型下的数据规模大、速率快，而一些复杂 问题不可能只通过一遍扫描就得到准确答案。数据流算法的一大特征就是它 返回的值通常是近似的。算法的精确度往往和内存空间紧密相关，当存在更 多内存空间，算法的准确度也就更高。 ( 3 ) 计算的标准化：数据流查询需要在流数据计算理论下进行标准化。 标准化应当适应于有数学基础的算法设计和开发。近似技术和统计学理论是 这一理论的重要基础。近似技术可以提供解决方案，使用统计学理论可以提 供数据查询问题的损失函数。 2 资源问题 ( 1 ) 资源消耗最小化：在资源限制环境下有大量数据流产生。传感器网 络就是一个典型的例子。这些设备的电池使用寿命较短。节能的设计技术是 个关键问题，这是因为除了伸缩性差的问题外，将所有产生的数据流发送到 中心基地的所消耗能源很大。 ( 2 ) 无限存储器的需求：机器学习技术是数据挖掘算法的主要来源。大 多数机器学习方法在执行分析算法的时候需要将数据存储在存储器中。由于 产生了大量的流数据，需要为到来的数据流设计高效的空间，或在不丢失重 要信息的前提下对流数据做更为简单的描述。 3 分布式数据流的研究 在分布式环境下，大量的连续查询以操作链集合的形式分布到多个服务 器。这些查询本质上是能接受和处理来自外部数据源产生的连续的数据流实 时监听系统就适合这种环境：在这个领域提供低等待时间、高吞吐量的查询 结果是非常重要。 由于s k y l i n e 查询在数据流上应用要涉及到大量、实时、无序的数据，因 此，在查询处理前必须筛选部分数据进行查询处理，这就要求必须选择合适 的数据流查询模型。通过数据流模型针对数据流查询近似性的特点，采用数 据抽样的方法，本文主要是采用滑动数据窗口来提取那些最近的数据。同时， 4 哈尔滨工程大学硕士学位论文 s k y l i n e 查询算法在选择的时候，针对海量的数据不可能储存在外存上，只能 在内存进行处理，算法也必须充分考虑减少c p u 、内存和i 0 消耗。 1 4 研究内容及论文结构 本文主要分析介绍了几方面的内容： ( 1 ) 分析研究s k y l i n e 查询算法的特点及概况，找出该算法的优缺点和 适用的环境，通过对比得出什么样的算法适合在数据流上应用。 ( 2 ) 针对海量、实时、无痔的数据流的时候，s k y l i n e 查询算法在形成 s p ( s k y l i n ep o i n t s ) 集合的时候可能会占用大量的系统资源。必须充分的考 虑算法的合理性，以及合理建立查询模块。 ( 3 ) 通过对现有s k y l i n e 算法的研究和分析，针对算法对各种不同的数 据( 正相关数据、反相关数据、独立数据) 的不同环境，分析s k y l i n e 算法的 优缺点，尤其是涉及到数据流上的s k y l i n e 查询计算。 ( 4 ) 在对现有s k y l i n e 算法算法分析的基础上，提出一种新的改进的 s k y l i n e 查询算法，通过仿真与其他现存的针对数据流查询的s k y l i n e 算法进 行比较，从而总结改进的效果及依旧存在的问题。 本文的结构安排如下： 第l 章在研究s k y l i n e 查询算法的背景及意义、国内外发展现状的基础上， 确定主要研究工作及论文的结构安排。 第2 章对数据流查询技术进行分析研究，简要介绍应用于数据流查询的 各种技术，归纳总结它的优点和不足。同时介绍了s k y l i n e 查询的数学理论和 目前s k y l i n e 计算的基本算法，然后研究该算法在数据流查询中的应用。 第3 章首先分析研究数据流的s k y l i n e 查询算法，对近年来对s k y l i n e 算 法的改进做了一个总结，针对存在的问题提出了一种新的改进算法。 第4 章实验及结果分析。通过对改进算法进行仿真，对改进算法和原算 法进行了测试对比，并针对算法的应用进行仿真实验。证明改进算法的优势。 在结论中全面总结了本文的研究成果，并给出今后进一步研究工作的展 望。 5 哈尔滨工程大学硕士学位论文 第2 章，s k y l i n e 计算概述 本章主要介绍数据流上的s k y l i n e 计算所用到的技术。简单的介绍了一下 s k y l i n e 数学依据，根据s k y l i n e 数学理论，推导出适合数据流上的s k y l i n e 查询，从而在改进算法的时候做到有理有据。为了方便算法的改进，本章对 目前的一些比较经典的s k y l i n e 算法做了一些简单的介绍，从而可以针对目前 算法的优缺点，更加完善数据流上的s k y l i n e 查询计算。 2 1s k y l i n e 理论 2 。1 1s k y l i n e 查询理论概述 s k y l i n e 查询是一个典型的多目标优化问题。对它的研究最早可以追溯到 1 9 7 5 年。k u n g 曾经提出了只针对二维数据和三维的数据，这种算法的查询 复杂度为o ( n l o g ，) 的算法，针对大于三维的数据，提出了查询复杂度为 o ( ( n l o g ，行) 如2 ) ( 矗为数据元组的维度) 的算法。后来，b e n t l e y 在假定各维 数据分布独立的情况下提出了人们期望的线性查询算法。所有这些研究假定 数据量比较小的情况下，数据可以放到内存，所提出的算法也是内存算法。 数据库领域的s k y l i n e 查询研究始于2 0 0 1 年，最早由b o r z s o n y i 等人提 出，主要关注海量的数据，当数据无法放入内存的情况下，如何处理s k y l i n e 查询，数据流上的s k y l i n e 计算也可以归属于此类。最近几年，对s k y l i n e 查 询大致可以分为四类： ( 1 ) 单s k y l i n e 查询处理算法：这类算法假定所有的s k y l i n e 对象都处 在一个特定的d 维空间中，返回的结果集合也只有一个。根据查询过程中是 否借助索引，单s k y l i n e 查询处理算法又可以分为两类：不带索引的s k y l i n e 查询算法和带索引的s k y l i n e 查询算法。前者假定没有任何索引存在，通过扫 描整个数据集( 至少扫描一次) 来返回s k y l i n e 查询的结果集；后者通过引入 6 哈尔滨工程大学硕士学位论文 适当的索引结构，如r 树，来提高查询处理的效率。 ( 2 ) 多s k y l i n e 查询处理算法：现实生活中不同的用户可能有不同的兴 趣和偏好，针对这种情况，需要在不同的子空间中处理s k y l i n e 查询的需求， 数据仓库和o l a p 领域的研究者对不同子空间上进行s k y l i n e 查询的研究产 生了浓厚的兴趣，提出了s k y c u b e 的概念，s k y c u b e 是借用传统的d a t a c u b e 的多维层次结构，同时计算多个s k y l i n e 查询的思想，该类算法主要包含针对 s k y c u b e 的计算、维护和压缩等。 ( 3 ) 不同应用环境下的s k ) l i n e 查询处理：主要包括w e b 信息系统的 s k y l i n e 查询处理、p 2 p 网络环境下的s k y l i n e 查询处理、数据流环境下的 s k y l i n e 查询处理、移动的公路网络环境下的s k y l i n e 查询处理等。 ( 4 ) s k y l i n e 查询处理问题的扩展。例如：国外学者扩展了空间数据库 中不同数据点之间的控制关系的概念，将其用于经济学框架下的商业分析， 提出了控制关系分析的概念；针对高维空间下出现的s k y l i n e 查询结果中的点 非常多，从而导致该结果在很多时候对用户失去意义的问题，提出了 k d o m i n a n t 的概念等等。 总之，鉴于s k y l i n e 查询在多目标决策方面的优势，s k y l i n e 查询处理问 题已经引起了国内外研究者高度的重视，并出现了许多高质量的论文，展示 出大量的研究成果。为了更好的应用s k y l i n e 查询处理在多决策树方面的重要 应用价值和在实时在线服务方面的良好应用前景，捕捉s k y l i n e 查询处理的发 展动态，对s k y l i n e 查询处理研究有一个总体上的把握，促进国内的研究步伐， s k y l i n e 查询计算，尤其是在数据流上的查询计算具有十分重要的意义。 2 1 2s k y l i n e 查询理论基础 s k y l i n e 查询问题也称为p a r e t o 最优或极大向量问题，作为数据挖掘的重 要研究分支，广泛应用于多标准决策、用户参考查询和网络计算中作业调度 优先等领域，主要是从一个潜在的、大的数据集中找出有兴趣的点( 元组或 者目标) 1 ，这些点都是不被其它点支配的。它和c o n v e xh u l l s 、t o p k 查询、 最近邻( n e a r e s tn e i g h b o r ) 查谢等都有关系。主要是通过s k y l i n e 查询首先 过滤点一些不必要的点，保留那些相对而言比较重要的数据集合s p ( s k y l i n e 7 哈尔滨工程大学硕士学位论文 p o i n t s ) ，从而可以为以后的数据处理减少了不必要的资源浪费。 具体地讲，s k y l i n e 查询不是将问题转化为单目标优化的问题，而是直接 采用多目标优化算法解决原始的多目标问题多目标优化算法最终返回的结 果集是一系列平行的、互相不受支配的解( 位于s k y l i n e 上的多个s p ) 。这里 的“支配”是指一个数据元组在每一维上都不比另一点“差”，而且必须至 少在一维上比另一点要“好。其中，差和好并无统一的定义，根据用户 的查询和选择条件的语义而定。s k y l i n e 查询处理就是指从给定的一个d 维空 间对象集合s 中选择一个子集，该子集中的任意一个点都不能被s 中的任意 一个其它的点所支配。所谓支配关系是指给定一个人r 维空间中的多个对象( 对 象集合) ，若存在这样两个对象尸和q ，对象尸在所有维度上的属性值都不 比对象q 差，并且至少在某一维上的属性值优于对象q ，则称尸支配q 。此 时，称该s 的子集为s p 的集答。 假设有d 维空间d ，d = 口，a 2 ? 口d ) 。其中属性a l ，a 2 ，( d 的定义域均 为区间( o ，1 】。集合u 中的对象均来自空间d 。 定义2 1 ：支配：d 维空间上的任意给定两个对象p ( p l ，p e ，p o ) ， q ( q l ，q 2 ，g d ) ；p ，q eu 。若尸在任意一个属性上的取值都不大于对 象q ，并且至少在某一个属性上的取值p 比q 要小，即尸，q 如果满足下列 两个条件，那么称元组p 在d 维空间上支配元组q ”： ( 1 ) w ( p j q j ) ，l ，z y , ( 2 ) 可( p j - q i ) 记为尸q 。若p 在d 的某个子空间b 上支配q ，则记为尸b o 。 定义2 2 ：s k y l i n e 集合d 维空间u 上，u 中所有不被其他对象所支配的 点( 对象或者元组) 组成的集合，记为s p “”。 定义2 3 ：子空间s k y l i n e 在d 的某一子空间b ( b 互d ，群g ) 上，u 中所 有不被其他对象所支配的对象组成的集合，记为船“”。 定义2 4 ：子空间b 上的种子s k y l i n e 它是这样集合，若s 且不存在 t e s ，b s ，则s 为该集合的成员子空间召上的种子s k y l i n e 记为s e e d ( b ) 。 在不引起混淆的情况下也可简记s e e d 川。 其中为了算法更好的运行，也可以利用定义自行推理的一些定理、引理 等等，从而可以很方便的降低算法的复杂度，提高整个系统的运行效率。 8 哈尔溟工程大学硕士学位论文 引理2 1 ：己知数据集彳b ，对v s s p ( b ) ，若s a ，则s s p ( a ) 1 6 1 。 反证法：假设s 仨s i 尸( 么) 即3 e a ，e 支配s ；又么口，所以eeb ；即 3 e b ，使得e 支配s 成立，这与已知s s p ( b ) 矛盾。从而引理2 1 得证。 定理2 1 ：设数据集：u n ，蹦叼= s ( i = i ，2 ) ，贝1 j s p ( n ) ：即( 已墨) 。 j = 1 i = l 证明：( 1 ) 首先证明任何在卵( 加中的元素必定出现在妒( 已s i ) 中。 v ses p ( n ) ，必定存在某个f ，使得sn i 。由引理2 1 ，se s ，故s 鱼薯； 又因为已s i u 行：n ，再由引理2 1 ，从而得到se 艘( u n s f ) 。 f 1 f - 1 f - 1 ( 2 ) 证明任何不在s p ( 川中的元素也一定不在s p ( 已s f ) 中出现。 v e 仨驴( ) ，则必定3 s e s p ( n ) 使得s 支配e ； 因为s s p ( n ) ，由( 1 ) 就会得到s 艘( ( ) s ) 。 由( 1 ) 、( 2 ) 的，s p ( n ) ：s p ( 已墨) 。 佶1 定理2 1 说明，如果各个分布式节点n o d e ( ，) 能够分别计算出各自监测 到数据流的s k y l i n e 集合卵f ，然后实时传递给集中式节点c 进行再次计算， 则可确保最终运算结果的正确性。一般来说s k y l i n e 集合内元素个数会远远小 于原数据集规模，因此通过预计算数据子集的s k y l i n e 可以大大降低网络通信 开销。考虑到在一般的分布式数据流环境下( 如传感器监测网络) ，n o d e ( d 的运算能力和存储能力非常有限，因此计算数据子集s k y l i n e 方法的适用性受 到一定限制。 引理2 2 ：数据集asb c ，如果s p ( a ) = s p ( c ) ，则 s p ( a ) = s p ( b ) = s p ( c ) “。 证明：由s p ( a ) = 即( c ) 得，对v e c a ，必定3 s s p ( a ) ，使得s 支 配e 。又因为彳b c ，所以b - a c - a ，故对v e b a ，必3 s s p ( a ) ， 使得s 支配e 。所以s k ( a ) = s k ( a + b + c ) = s k 。原命题得证。 9 哈尔涣工程大学硕士学位论文 定理2 2 ：设数据集= ( ) m ，s = s p ( n ) i ) n i ，( f = 1 ，力) 。若对v i i = 1 都存在集合m 满足m 朋，则s p ( n ) = 肛( c ) n i ) 。 。 i = l 这里主要介绍了s k y l i n e 查询计算的理论基础，方便以后的工作顺利的展 开，下面各章节都要围绕这个理论推广。不管是建立查询模型，还是对s k y l i n e 查询算法进行改进。其中涉及到的各种定理定义也可以从中延伸出所需要的 推理，也是对算法改进的基础理论。 2 2 滑动窗口模型 对数据流进行数据挖掘的时候，不管是聚类分类突变检测，还是查询操 作，由于系统的资源的局限性，而数据流的数据量是无限的，有限的内存空 间无法存储数据流的全部数据。虽然采用外存可以处理大容量数据集，但磁 盘等存储介质在执行查询时需要进行大量的i o 操作，其响应的速度往往很 慢，难以适应实时、大量数据的查询要求。实际上，在数据流分析中人们关 心的往往是那些最新的数据，新的数据要比历史数据更加重要，例如仅仅考 虑最近一周中的数据等。滑动窗口就是在内存中设定一个区间，该区间只包 括数据流中最近到来的那部分数据。伴随着数据流上新数据的到来，滑动窗 口不断地更新，滑动窗口查询只用滑动窗口中的数据得到查询结果，其它数 据则在滑动数据窗口的更新过程中被删除。 滑动窗口的大小可以用时间或数据量进行定义，按照时间和数据量不同 定义，可以分为基于时间的滑动窗口和基于数据量的滑动窗口。基于数据量 的滑动窗口当窗口内的数据流状态达到形时，如果有一个新的数据流状态到 达，则应当将其插入到滑动窗口的前部，同时删除滑动窗口的最后一个数据 流状态，从而可以保持窗口内的数据永远是最新的。 滑动窗口的数据元素到达后被缓存起来，对查询的回答在响应时间允许 的情况下，周期性地计算。通过把窗口细分成基本窗口的小块，查询系统可 以仅存储滑动窗口中每一个基本窗口的摘要和时间戳，当旧的基本窗口的时 间戳失效，便将其从存储器中去除，而后再增加一个新的基本窗口到存储器 1 0 哈尔滨工程大学硕士学位论文 当中，窗口的缺点是只有当新的数据流添加到当前基本窗口后，计算结果才 更新。对s k y l i n e 查询的计算结果有一定的影响。 可以说，滑动窗口是数据流上应用比较多的一种特殊的数据抽样方法。 由于数据流的实时、无序等特性i 伴随着海量数据，滑动窗口在数据流的查 询、聚类分析等都有广泛的应用。随着新数据窗口向前移动，用最新的数据 替换最旧的数据。与其它抽样方法相比，滑动窗口的优点在于其语义明确。 更重要的是，在许多应用中，例如传感器网络，用户关心的只是数据流中新 近到来的那部分数据。此时，滑动窗口是一种十分理想的抽样方法。 基于时间的滑动窗口结构：将大小为时间乃的滑动窗口w i 分割为若干 时间大小为b ，的基本窗口b f ，基本窗口个数n i p i 2 - 卜，所有维上的属性值范围都映射到 0 ，1 】； ( 4 ) 本算法考虑去大操作为优( m a x ) ； 1 9 哈尔滨工程大学硕士学位论文 算法基于的规则：一个点工= ( j c l ，x 9 ，工彳) 用一个m 位的向量表示，其中， x i 用k i 的总和，即为点了在所有维上不同属性值的个数之和，每位依次为 只l ，p i 2 ，如果t 是f 维上的第p 婶个不同属性值，则薯的磅个位上的值分别 为：第1 位到第口j 位设置为o ，第a 位到第岛位设置为l ，这样就把每个数 据点转换为了相应的点阵结构。 判断方法：设砖代表位片在第f 维上的第，个不同的属性值，根据以下 规则判断一个点x = ( j c l ，b ，x a ) 是否是s p - ( 1 ) 让4 = b s m & b s 2 日2 & s s d q d , 则当且仅当第刀个点在所有维上的 属性值都优于( 或等于) 其它点x 在相应维上的属性值时，a 的第玎位置为1 ： ( 2 ) 让b = b s i ”，b s 2 酬b 一，则当且仅当第”个点在所有维上的 属性值都优于其它点x 在相应维上的属性值时，召的第刀位置为1 ： ( 3 ) 让c = 彳& b ，则当且仅当第n 个点在所有维上的属性值都优于( 或 等于) 其它点x 在相应维上的属性值，且在某些维上的属性值优于其它点x 在相应维上的属性值时( 满足p 定义) ，c 的第玎位置为1 这样，无须遍历 整个数据集，算法就能判断出一个点是否是s p ，从而提前返回查询结果。 虽然b i t m a p 能较快计算出一些s k y l i n e 点，但由于它每计算一个点都需 要将这个点与其它所有的点相比较，效率较低。此外，b i t m a p 所采用的映射 方式会导致所在位串的长度随各维度上不同取值数的增大而急剧增加，耗费 大量的空间。 i n d e x 采用映射的方法，它将高维数据转化为一维数据的处理思想，然后 对转换后的数据建立一个b + 树索引，将每个点索引到它取值最小的一维所对 应的链表上，分批地处理数据点并产生s k y l i n e ，具有较好的渐进性。 该算法的基本思想是将各个维上的属性值按降序排列( 基于各个维上的 排序) ，同时按序扫描各维上的元组，因此很容易得到第1 个匹配的s p 。第 1 个s p 一定在某个维度上拥有最大的属性值，所以，在找第1 个s p 时，只 要找那些在某维上的属性值为最大的点即可而在各维上都排在已找出的s p 之后的点，一定受控于那个s p ，因此可以直接删除这样的点，从而节省i o 2 0 哈尔滨工程大学硕士学位论文 开销。但同时降序排列的时候无疑会浪费大量的计算空间，从而阻碍了算法 在数据流上的拓展。 但如同前面提出的各种算法一样，i n d e x 算法不具有良好的用户友好性， 不能将用户的偏好融入s k y l i n e 计算的过程中来按用户规定的顺序返回结果。 并且，i n d e x 不是一个公平的算法，它偏向于先求出那些在某一维上取值特别 好的点，而没有综合考虑各个维度。同时，如果第一个s p 点不能还快找到的 时候，就会大大降低算法的执行效率，从而浪费了计算空间。 2 4 4 最近邻法 最近邻算法n n 是第一个用户友好的s k y l i n e 计算算法。它根据用户自定 义的距离公式，将所有数据用r 树索引。每一次，找到离原点距离最小的点， 用这个点将数据空间划分成若干子部分。1 。显然这个点是一个s k y l i n e 点，可 以立即被输出给用户。而n n 将在每一子部分上递归调用这一过程直到子部 分只含有一个点为止。n n 算法是一个公平的算法，且能够根据用户规定的 顺序返回s k y l i n e 点，具有良好的用户友好性。n n 算法在四维及以下的数据 库上都能比前面几种算法更快计算出结果，并能很快地返回第一个s k y l i n e 点。然而，随着数据空间的不断递归划分，很多子空间将被重复搜索，这些 多余的工作导致n n 的渐进性不如i n d e x 算法，且耗费了大量的时间空间。 2 4 5 分枝界限法 分枝界限算法b b s 与n n 一样也是基于最近邻搜索的，且同样采用了r 树对数据索引。b b s 为r 树的每个节点，或称为一个最小包容矩形( m i n i m u m b o u n d i n gr e c t a n g l e ，m b r ) ，计算其到原点的最小距离。算法首先将r 树根 节点的所有子m b r 按其到原点的最小距离插入一个最小堆中。每一次，从 最小堆中取出根节点，并扩展出它的所有子m b r ，一一的插入堆里。而当最 小堆的根节点不包含子m b r 时，则扩展出此节点里所含的数据，求出新的 s k y l i n e 点 b b s 是一个正确、公平的算法。当数据库维数小于6 维时，b b s 在计算 2 1 哈尔滨工程大学硕士学位论文 时间、占用空间、输入输出上都展示出很高的效率和很好的扩展性。当维数 达到6 维及以上时，由于r 树在高维空间上性能的降低，b b s 的性能也受到 影响，但是r 树可以方便用户在任何子空间上用b b s 算法求取s k y l i n e ，灵 活高效。由于每次扩展m b r 后求出的s k y l i n e 都可以立即返回给用户，b b s 也具有很好的渐进性。通过改变最小距离公式，b b s 还可以很好地适应用户 需求。因此，从性能的各个方面考虑，b b s 都远远优于以前提出的所有算法， 被认为是当前最优的集中式s k y l i n e 计算算法。 在算法效率方面，b b s 无论是c p u 计算时间或是i 0 开销都远远小于其 它算法，为所有算法中最佳。n n 在返回所有s k y l i n e 结果的时间开销上比 i n d e x 要小，整体效率优于i n d e x 。而s f s 独有的预排序过程确定了点的支配 偏序关系，大大提高了b n l 的效率。b i t m a p 虽然仅仅使用位运算，但由于 它每计算一个点都需要将这个点与其它所有点相比较，总体效率较低。 表2 】 集中式s k y l i n e 查询算法性能的比较 正确性公平性用户友好性 b n l 、， s f s v d & c、，、， b i t m a p 、， i n d e x n n、， b b s d & c 在数据可以完全写入内存时效率很高，当内存较小或数据很大时， 就耗费了严重的i o 开销。对于可扩展性，b b s 仍然独占鳌头，而n n 由于 在数据空间的不断递归划分的过程中产生了大量的子空间，很多子空间被重 复搜索，导致扩展性不如b b s 。在五维以下，s k y l i n e 集合增大时，n n 的可 扩展性比i n d e x 好，且随着s 蚴讪e 集的增大差距越来越大。 b n l ，s f s ，d & c 算法都极大地依赖于内存。b i t m a p 所采用的映射方式 会导致位串的长