（计算机软件与理论专业论文）topk潜力skyline查询的研究.pdf

t o p - k 潜力s k y l i n e 查询的研究 论文题目：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 查询会找出其中的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 酒店的点做为投资对象，因为这些点可以让他们的投资带来更大的回报。 基于这样的实际需求，本文提出了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 点。本文给出了问题的形式化定义， 并提出了两种基于数据网格的求解算法和相关的剪枝策略。g r i d e 算法是第一个 算法，它的主要思想是迭代遍历数据网格的交点；第二个算法g r i d p 采用了递 归的集合划分和空间投影方法来求解问题，针对该算法本文给出了它的正确性证 明。在本文的最后，我们在真实数据和合成数据集上对这两个算法进行了详细的 实验测试，实验结果说明了算法的有效性。 关键词：s k y l i n e 、潜力s k y l i n e 、临界点、关键临界点、临界代价、最小临界代 价 t o p - k 潜力s k y l i n e 查询的研究 a b s t r a c t t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： f i n d i n gt o p - kp o t e n t i a ls k y l i n e s c o m p u t e rs o f t w a r ea n dt h e o r y z h o n g k a n gf a n g y u b a o l i u a b s t r a c t g i v e nam u l t i d i m e n s i o ns e td ，s k y l i n ei st h es e to fp o i n t sw h i c ha r e s td o m i n a t e d b yo t h e r si nd i t sm a i n l yu s e df o rm u l t i - c r i t i e r i ad e c i s i o n , f o re x a m p l e ，s k y l i n eq u e r y c a nf i n dt h es k y l i n eh o t e l st h a tn oo t h e rh o t e l sc a nb eb e t t e rt h a nt h e mo na l la t t r i b u t e s ， a n du s e r sc a nj u s tc h o o s eo n eo ft h e s eh o t e l s s k y l i n eq u e r yc a l lf i n dt h eb e s tp o i n t s t h a tu s r e sp r e f e r , b u ti tc a n tf i n dt h ep o t e n t i a lp o i n t s f o re x a m p l e ，ah o t e li n v e s t o r m a yw a n tt of i n ds u c hn o n - s k y l i n eh o t e l st h a th a v et h ep o t e n t i a lt ob es k y l i n eh o t e l s ， b e c a u s et h e yc a nb r i n gh i mm o r ep r o f i t s i nt h i sp a p e r , w ep r o p o s ean e w1 【i n do f t o p - kp o t e n t i a ls k y l i n eq u e r y , w h i c hc a nf i n dt h em o s tp o t e n t i a lkp o i n t st ob es k y l i n e w e 酉v eo u tt h ed e f i n i t i o no f t h ep r o b l e m , a n d p r o p o s e dt w oa l o e o - i h t m sb a s e d o i ld a t e 酣d g r i d - ei st h ef i r s ta l g o r i t h ma c c o r d i n gt os e a r c ha l lt h eg r i di n t e r s e c t i o np o i n t st o h a n d l et h ep r o b l e m a l g o r i t h mg r i d pu s e ss e td i v i d i n ga n ds p a c ep r o j e c t i o nt oh a n d l e i t m o r e o v e r , w ep r o v et h a to u ra l g o r i t h m sc a nf i n dt h eo p t i m i z a t i o nq u e r yr e s u l t s t h ee x p e r i m e n t a lr e s u l t sb a s e do nr e a ld a t a s e t sa n ds y n t h e s i z ed a t e s e ts h o wt h e e f f i c i e n c ya n de f f e c t i v e n e s so fo u ra l g o r i t h m s k e yw o r d s ：s k y l i n e ，p o t e n t i a ls k y l i n e ，c r i t i c a lp o i n t , k e yc r i t i c a lp o i n t , c r i t i c a lc o s t , m i n i m a l c r i t i c a lc o s t 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：赶遮 日期： 学位论文使用授权声明 为 口6 _ 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论支的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：槲j 7 象 日期：如l 口年月 e l 导师签名： m 存 1 日期珈f 牟月乙e l t o p - k 潜力s k y l i n e 查询的研究 第1 章绪论 1 1 研究背景 第1 章绪论 信息化社会的今天，计算机成为了信息的主要管理工具和主要的集中存储 地方。然而人们经常要面临这样一个问题：他们需要从这些海量数据中找出一些 自己感兴趣的数据。显然如果只是人为地去挑选并做出抉择，这是非常低效并且 不现实的。为此s k y l i n e 查询应运而生，一种只返回用户可能感兴趣的数据子集 的查询，它对用户的多维决策有很好的指导作用。 s k y l i n e 查询是找出一个多维集合中所有不被其它点支配的数据点集合。我 们说p 支配点q 当且仅当p 的所有维度的值都不比q 的差，并且至少在某一维上 g 要优于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 查询可根据用户的需求返回的所有的s k y l i n e 点，这些数据点构成了是集 合中最匹配用户需求的子集，并且是大大小于原来整个集合的，因为用户只需考 虑这个子集来进行自己的决策，加快了他的决策效率。例如：旅客可通过s k y l i n e 查询可以找出那些价格低廉且离海边距离较近的酒店，然后他只需从这些酒店中 找到自己中意的即可。 2 0 0 1 年，b o r z s o n y i 等人在文献 3 】中首次将s k y l i n e 查询引入到了数据领域， 并扩展了s q l 语句使得数据库支持该查询。自此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 l o c kn e s t e dl o o p ) 1 3 、分而治之算法( d i v i d ea n d c o n q u e r ) 【3 】、排序过滤算法( s o r tf i l t e rs k y l i n e ) 【5 】、线性缩减排序算法( l i n e a r e l i m i n a t i o ns o r tf o rs k y l i n e ) 【8 1 等；基于索引的有索引算法( i n d e x ) 【9 】、位图算 法( b i t m a p ) 1 1 1 、最近邻居算法( n e a r e s tn e i g h b o r ) 1 6 、分支限界搜索算法( b r a n c h t o p - - k 潜力s k y l i n e 查询的研究 第1 章绪论 a n db o u n ds e a r c h ) 【刀等。除了关注查询的效率，优化s k y l i n e 查询的结果也是一 个重要的研究方向，针对高维数据集会产生大量s k y l i n e 点的情况，给出了代表 性s k y l i n e ( r e p r e s e n t a t i v es k y l i n e ) t 3 4 1 、基于距离的代表性s k y l i n e ( d i s t a n c e b a s e d r e p r e s e n t a t i v es k y l i n e ) 3 7 1 、k 支配s k y l i n e ( k 。d o m i n a t es k y l i n e ) d 6 等s k y l i n e 定 义的变形，用于返回更具有代表性的s k y l i n e 点，减小返回的结果集。同时还出 现了很多其它的s k y l i n e 查询的变形，如d y n a m i cs k y l i n e l 7 1 、r e v e r s es k y l i n e e 3 0 l 等，所有这些完善了s k y l i n e 查询的功能，使得它可以检索出更多其它的有用信 息。 s k y l i n e 查询同时被扩展到了多个不同应用环境中去，有针对数据流【2 4 1 、公 路网【3 3 1 、分布式环境d 引、p 2 p 网络【4 0 1 等的s k y l i n e 查询。除了上面所说的，c h e n 等2 0 0 8 年在文献【4 1 】中讨论了m e t r i cs p a c e 上的s k y l i n e ，p e i 等2 0 0 9 年在文献【2 5 】 中将s k y l i n e 应用到了时间序列上，可以看出这几年关于s k y l i n e 查询在不同应用 环境的应用一直在被研究。 1 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 查 询酒店返回的只是那些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 查询就不能满足他们对 有潜力酒店需要的查询。实际应用中对于有潜力数据的查询还有许多，如n b a 教练查找有潜力的球员、股票市场查找有潜力的股票等，传统的s k y l i n e 查询在 2 t o p - k 潜力s k y l i n e 查询的研究 第l 章绪论 这方面都不适用。 针对该问题，本文提出了t o p k 潜力s k y l i n e 查询，用于返回k 个最有潜力 的数据点。 1 3 本文的主要工作 本文主要做了如下工作： ( 1 ) 系统地综述当前s k y l i n e 的研究现状，通过分类的方式的介绍了s k y l i n e 研究的主要方向，列举了每个方向代表性的研究成果。 ( 2 ) 结合实际应用引入了t o p k 潜力s k y l i n e 查询问题，对该问题的进行 了理论分析和研究，给出了相关的概念和定义，并给出了该问题的精确定义。 ( 3 ) 提出了两种求解t o p k 潜力s k y l i n e 查询问题的算法，详细介绍了每 个算法的设计思路和过程。同时设计了完整的实验对这两个算法在空间、时间等 各方面进行了比较测试。 ( 4 ) 对本文所做的研究进行了总结，指出了本文存在的不足，同时给出了 未来可以继续改进的地方。 1 4 本文的组织结构 本文共分7 章，余下的几个章节安排如下： 第2 章对s k y l i n e 查询领域的研究现状进行概要介绍，给出了s k y l i n e 查询 的定义、应用和到目前为止的研究现状。 第3 章引入了t o p k 潜力s k y l i n e 查询问题，通过实例说明了潜力s k y l i n e 查询问题的意义，随后给出了该问题相关的概念和定义，并给出了该问题的精确 定义。 第4 章提出了求解该问题所需的数据网格，并基于此给出了通过遍历数据 网格交点的方法求解问题的g r i d e 算法，同时给出了该算法的一些剪枝策略。 第5 章给出了本文的第二个算法g r i d p ，详细讲解了该算法的基本思想和 执行过程，同时给出了该算法的正确性证明。本章最后给出了两个算法都通用的 t o p - k 潜力s k y l i n e 查询的研究 第1 童绪论 优化方法。 第6 章对g r i d - e 和g r i d - p 算法进行了实验测试，分别使用了合成和真实数 据集，对实验结果进行了对比和分析，并给出实验总结。 第7 章对本文的工作进行了总结，同时给出了展望。 4 t o p - k 潜力s k y l i n e 查询的研究第2 章s k y l i n e 研究现状 第2 章s k y l ir e 研究现状 2 1 s k y l i n e 查询问题 s k y l i n e 查询类似与以前的最大向量【1 力问题，它是指找出一个多维数据集合 d 中所有不被其它点支配的数据点集。假设p ，q 是集合d 中的任意两个点，如 果p 的每一维都不比g 的对应维差，并且至少在某一维上要优于g ，那么就称p 支配g 。如果p 不被d 中的任意其它点支配，那么p 是d 的s k y l i n e 点t 由d 的 所有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 这个单词( 中文是“轮廓”的意思) ，主要是因为用它 查询出来的所有s k y l i n e 点连接起来会构成了集合d 的一个边缘轮廓，如图2 1 所示的虚线，虚线上的黑点是s k y l i n e 点。在文献【3 】中首次将s k y l i n e 查询引入 到数据库领域，作者扩展了传统的s q l 语句，将s k y l i n e 定义为一个s q l 操作 符，使得传统s q l 支持s k y l i n e 查询，具体扩展后的s e l e c t 语句如下所示： s e l e c t f r o m w h e r e g r o u p by h a n g - s ! k 配，价匹卯口，沏n im a xj 瑚，锄忉n im a x jd f a 其中最后一行的s k y l i n e 就是新添入的操作符，负责返回前面的s e l e c t 查询 结果的s k y l i n e 。a , ，a n 表示s k y l i n e 查询所使用的维度，r a i n 和m a x 表示对应 的维取最小最大值，d f f 表示值不相同。 数据库领域计划通过扩展s q l 语句，定义s k y l i n e 操作符的方式来支持 s k y l i n e 查询。当今世界，特别是随着i n t e m e t 的发展，信息在飞速的膨胀，数据 库中存储的数据一般都是数十百g ，而且还在以飞快的速度增长着。显然传统的 基于内存的求解最大向量问题的算法是不适用的，因为内存不可能装下外存数据 库中存储的所有数据，基于内存不足情况下的s k y l i n e 查询算法就成为了这个方 向的研究重点。数据集合大小和维度一直是影响s k y l i n e 查询效率的主要因素， 特别是随着维度的增加，效率会成指数级别的下降 3 ，5 ，6 ，7 ，8 ，9 】。因此如何高效的 支持s k y l i n e 查询仍然是数据库研究领域的重要研究问题，有很多地方还需要优 t o p - k 潜力s k y l i n e 查询的研究 第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 查询在分布式、 数据流、时间序列等各方面都已有研究。 窗 童 呈 c 黑 旦 。 窖 皇 鲤 2 2s k y l i n e 的应用 肼【$ 】 图2 1 纽约的酒店 s k y l i n e 查询在多维决策中有着非常重要的支持作用。它会根据用户的多维 条件设置只返还一个集合中较优的点，筛选掉那些被支配的点，缩小用户做决策 时参考的范围。一个非常经典的案例是用户a l e x 去纽约旅行，出发之前要先预 定酒店。假设纽约的所有酒店可以从网上获取到，并且a l e x 考虑预定哪个酒店 的主要依据是酒店的价格p r i c e 和它距离海边的距离d i s t a n c e 。他希望酒店的p r i c e 越小越好，离海的距离d i s t a n c e 越小越好。图1 用一个二维坐标系的形式给出了 纽约的所有酒店，坐标系中每一点表示纽约的一个酒店，横轴表示p r i c e 属性， 纵轴表示d i s t a n c e 属性。按照a l e x 的要求，s k y l i n e 查询会返回图1 中虚线上的 黑点表示的酒店。因为这些黑点代表的酒店是所有酒店中较优的，不论你选择了 其它什么酒店，都可以从这些黑点当中找到一个在p r i c e 和d i s t a n c e 上都要小于 它。因此a l e x 就只要在这些黑点代表的酒店中选择一个即可，而不用去比较纽 约所有其它的酒店，提高了他做决策的效率和正确性。在网络带宽受限的情况下， 6 t o p - k 潜力s k y l i n e 查询的研究第2 章s k y l i n e 研究现状 订票网站可以只返回这些酒店的s k y l i n e ，而它一般是远小于整个集合的，所以 可以节省网络带宽的使用。 2 3 相关研究工作 s k y l i n e 查询可看成是多目标优化问题，对它的研究可追溯到1 9 7 5 年k u n g 等在文献 1 l q b 研究的最大向量问题，当时他们针对二维或三维空间提出了时间 复杂度为o ( n l 0 9 2 n ) 的算法，针对大于三维的情况提出了时间复杂度为 o ( n ( 1 0 9 2 n ) a - 2 ) 的算法。文献 1 0 】假定数据各维独立分布情况时，给出了线性查找 算法。但是以上的这些研究都只是针对数据集较小且可全部放入内存的情况。 第一次将s k y l i n e 查询引入到数据库研究领域是从2 0 0 1 年的文献【3 】开始的， b o r z s o n y i 等人提出了扩展s q l 语句使得数据库支持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 3 1 静态数据集上的s k y l i n e 查询 静态数据集是指要查询的多维数据集合d 并不是经常变动的，其中的元素 基本上是稳定的。在这中情况下的s k y l i n e 查询算法主要可以分成两类：无索引 的算法和基于索引的算法。 ( 1 ) 无索引的s k y l i n e 查询 b o r z s o n y i 等人在文献 3 】中第一次研究内存不足情况下的s k y l i n e 查询，当 时考虑的就是静态数据集上的查询，并提出了b n l 和d & c 两个算法。b n l 算 法通过在内存中维持一个窗口，通过多次的迭代，让窗口中的元素与其它的元素 两两比较，最后算出集合的s k y l i n e 。b n l 算法在内存窗口较大时，最优的情况 下只需要比较o ( n 2 ) 次就可算出s k y l i n e ，但是随着数据集d 的增大，算法需要的 迭代次数会成指数级别的增加，效率也随之下降极快。d & c 算法分成两步：开 始是通过维度来划分集合d 为许多较小的集合，直到它们可以放入到内存为止。 然后将这些小的集合载入到内存中，分别算出对应的局部s k y l i n e 。下一步是合 7 t o p - k 潜力s k y l i n e 查询的研究第2 章s k y l i n e 研究现状 的过程，合并小集合的局部s k y l i n e ，去除其中受支配的最终得到d 的s k y l i n e 。 c h o m i c k i 等人对b n l 算法进行了改进，提出了s f s t 5 1 算法。s f s 算法通过 一个单调函数，对集合d 中每个元素求值，并根据这个值来排序集合，使得排 在后面的元素不可能支配排在其前面的元素。然后再基于这个排序去调用b n l 算法，可以使得不用比较d 的所有点，就可以确定s k y l i n e 点，大大提高了算法 的执行效率。l e s s 8 】是对s f s 算法的改进，通过引入一个消除过滤窗口来提前 删除一些不可能的成为s k y l i n e 的数据，基于排序的还有s a l s a 1 2 】。 z h a n g 等在文献【1 4 】中对高维数据的s k y l i n e 查询进行分析时，发现高维数 据的s k y l i n e 查询需要进行大量的点与候选s k y l i n e 之间的比较运算，即c p u 依 赖性很高，而这成为了算法效率的主要瓶颈。因此他们给出空间划分的方法o 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 点，树的叶子节点是候选s k y l i n e 点所处的一个 区域。每次新来的点都是通过遍历这棵树，与中间节点比较，并找到需要比较的 叶子节点，筛选掉不需要比较的区域，从而减少了要比较的候选s k y l i n e 点，即 减少了比较次数。作者随后给出了三个基于o s p 的算法，其中两个是基于内存 的，最后一个是基于外存的。但是这三个基于o s p 技术的算法都存在一个缺陷： 划分区域所用的s k y l i n e 点存在多种选择，而且选择的不同会导致后面的树的平 衡性受很大影响。作者在实验中也说明了存在这样的问题，但是并没有给出解决 方法。 显然之前的提出的这些算法都不能保证算法最坏情况下的执行效率，然而 在实际查询应用中这个是非常重要的。a t i s h 等人在文献【1 5 】中将随机方法引入到 s k y l i n e 查询算法的设计中，提出了r a n d 算法，它可以保证查询在最坏情况下 也能有较好的执行效率。 ( 2 ) 基于索引的s k y l i n e 查询 在无索引的算法中，不可避免的要对整个集合进行扫描，并比较其中的每 一元素才可以计算出s k y l i n e 。无索引算法会导致较大的i o 消耗，而这一般是 计算s k y l i n e 的主要瓶颈，因此基于索引的算法也在一直被研究。它们一般需要 对数据进行预处理，建立索引。 8 t o p - k 潜力s k y l i n e 查询的研究 第2 章s k y l i n e 研究现状 t a n 等给出的b i t m a p t l 】算法通过将每个点表示成一个位图，然后通过位操 作来判断一个点是否为s k y l i n e 点。该算法可以很快的返回前几个s k y l i n e ，满足 渐进行，但是要查询所有的s k y l i n e 则非常的低效，因为它要检索每一个点的位 图，并且不适用于数据集d 的变化。 i n d e x l 9 算法将整个集合划分到多个链表中，每个链表用b 树做索引。通过 b 树找到每个链表的局部s k y l i n e ，再将所有的局部s k y l i n e 合并到一起求出整个 集合的s k y l i n e 。 n n t 6 1 算法对集合d 建立r 树索引，通过迭代的应用最近邻居搜索的方法检 索出的结果来划分集合，渐进的检索出s k y l i n e 点。在应用最近邻居搜索方法检 索的结果划分集合是会差生重叠区域，为了去除这些重叠区域的元素，n n 算法 需要多次的遍历r 树。b b s t t 算法也是基于最近邻居的算法，通过优先访问r 树上的偏序节点，从而避免了多次的遍历r - 树，理论上b b s 算法是i o 最优的， 效率也要高于n n 算法。在文献【1 3 】中提出了一个基于z b t r e e 索引的z s e a r c h 算 法。m o r s e 等在文献 1 6 】中针对属性值的域范围较小的情况，给出了l s 算法， 该算法应用了网格结构来计算s k y l i n e 。l s 算法在属性域范围较大情况小效率不 高。文献 5 3 贝j j 针对数据集会发生任意的添加、修改和删除操作后s k y l i n e 如何 维护给出了研究，通过建立网格索引结构，使得集合的每次更改只需对网格的部 分区域进行计算即可。 2 3 2 子空间上的s k y l i n e 查询 上一小节中介绍的s k y l i n e 查询算法都是针对整个空间进行的s k y l i n e 查询。 考虑到实际应用中，人们可能只关心其中的部分属性。t a o 等在文献【1 7 】首次提 出了子空间上的s k y l i n e 查询，并提出了s k y c u b e 结构，所谓的s k y c u b e 结 构是指一个数据集合的所有非空子空间的s k y l i n e 的全体。基于s k y c u b e 的层 次结构，因为不同子空间上的s k y l i n e 存在关联性，给出了基于信息共享策略的 b u s 和t d s 两个算法。b u s 采用的是自低向上的方式逐层计算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 集合。除了这个信息，还存在着共享排序的策略。t d s 算法采用的是自项向下 的方式计算s k y l i n e ，运用了共享划分、合并和父空间计算结果。s k y c u b e 结 9 t o p - k 潜力s k y l i n e 查询的研究第2 章s k y l i n e 研究现状 构中存在很多的冗余信息，这使得当集合d 发生变化是，对它的维护代价也比 较的高。文献 1 9 】对s k y c u b e 进行了压缩，提出了新的存储模式c s c ，同时给 出了对c s c 的计算、查询和维护算法。 对于一个d 维空间的集合d ，它所具有的子空间就达到了矿1 个，如果存储 所有子空间的s k y l i n e ，将是需要非常多的存储空间。由于有时并不是完全需要 所有子空间上的s k y l i n e ，用户可能只对某个特定的子空间上的s k y l i n e 感兴趣， 这时s k y c u b e 就显的没有那么的太必要。p e i 等在文献【1 8 】中就提出了特定子 空间上的s k y l i n e 查询，并给出了s u b s k y 算法。该算法将多维的数据压缩成一 维的数据，然后用b 树对压缩后的数据建立索引，接着通过搜索b 树来进行子 空间的s k y l i n e 查询。但是该算法对维度比较敏感，不具备渐进性。文献 5 8 给 出了在线计算子空间的算法c s b ，具有渐进性的特点。 p e i 等人在文献 2 0 ，2 1 q b 结合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 查询提供信息。p e i 等同时在文献 2 2 】对这个方向上做了进一步的研究， 提出了基于语义压缩的s k y c u b e ，并给出了s t e l l a r 算法。 2 3 3 数据流上的s k y l i n e 查询 数据流是指数据如流水一样变化，每个数据都有自己的生命周期，从流的 一端进入( 产生) ，从另外一端流出( 失效) 。与之前的静态数据集相比，这里 的数据是经常变动的，随时会有新的数据产生，旧的数据超时失效，因此很多已 经提出的s k y l i n e 算法在这里是不适用的。在数据流中，通常会维护一个窗口， 数据流从其中流过，只要处于窗口中的元素才是有效的，因此数据流上的数据的 最大有效期是窗口的长度。l i n 等人在文献【2 4 】中首次将s k y l i n e 查询引入到了基 于窗口的数据流模型中，用以查询当前窗口s k y l i n e ，并提出了s t a b b i n gt h es k y 算法。算法的不同于以往在于它重点针对数据的添加删除对s k y l i n e 进行维护。 t a o 等在文献【2 3 】提出了l a z y 和e a g e r 两个算法，l a z y 算法的策略是将计算延迟 到有s k y l i n e 点超时失效时才进行，而e a g e r 算法会充分的利用前期的预计算来 尽可能减少内存的消耗。这两个算法都可以非常高效的应对数据的变化。文献【4 3 】 中讨论了如何持续在数据流上维持子空间的s k y l i n e ，文献【4 4 ，4 5 ，5 4 ，5 5 ，5 9 】都对数 据流上的s k y l i n e 查询进行了研究。 l o t o p - k 潜力s k y l i n e 查询的研究第2 章s k y l i n e 研究现状 2 3 4 时间序列上的s k y l i n e 查询 时间序列是由一组数据对( v a l u e ，t i m e s t a m p ) 构成，v a l u e 表示t i m e s t a m p 时刻 的值，所有的数据对按照t i m e s t a m p 排列，并且随时会有新的数据对产生加入到 其中。j i a n g 等在文献 2 5 】中首次对时间序列上的s k y l i n e 查询进行了研究。他们 假定时间序列上的t i m e s t a m p 都是正整数，数据对之间的时间间隔是等间距的， 并且将第f 时刻的值表示成s 【m 从而一个时间序列就可以表示成s 1 】，s 【2 】， s 【3 】。s 【i 羽表示处于时刻i 到j f 之间的数据对，即s q ，s + q ，s 们。时间序 列是动态变化的，随时会有新的数据对产生，而人们一般最关心的最近一段时间 内的数据对。文献 2 5 】对每个时间序列维护了距离当前时刻如最近的w 个数据对， 只有处于时刻+ l 到如中的数据对才有效，因此当前如时刻的每个时间序列就 可以表示成一个w 维的数据点研如w + l 】，s 【乙w + 2 】，纠) 。 设由一组时间序列构成的集合d ，p 和口是d 中的任意两个时间序列。p 支 配g 当且仅当对于任意的时刻f 有p s 网5g s 叼，并且存在一个时刻，使得p s 1 l 及对应的概率函数厂。实例都是确定，它们之间可以定义支配关系， 现在用u i - 的d y n a m i cs k y l i n e 的查询结果。在很多 情况下会假设d ，一么并且令庐忉广q ，l ，其中g 为用户查询时提供的任意一个d 维 的点，这时d y n a r r d cs k y l i n e 查询得到的结果是就是与g 特征相近的s k y l i n e 点， 被称为是g 的d y n a m i cs k y l i n e 点。p a p a d i a s 说明了b b s 算法可以直接应用到 d y n a m i cs k y l i n e 查询上。d e n g 等人在文献 3 3 】中在对公路网情况下有多数据源 的s k y l i n e 查询进行了研究时，也对多个数据源情况下的d y n a m i cs k y l i n e 查询进 行了研究，并给出了基于r 树的算法e d c 。d e l l i s 等人在文献【3 0 】中对d y n a m i c s k y l i n e 查询的逆查询进行了研究，给出了r e v e r s es k y l i n e 查询。如果p 是g 的 一个d y n a m i cs k y l i n e 点，那么g 就称为是p 的r e v e r s es k y l i n e 点。r e v e r s es k y l i n e 查询通过用户设定的一个查询点p ，找到所有的这样的点：它们的d y n a m i c s k y l i n e 中包含了p 。d e l l i s 他们同时给出了改进b b s 之后的算法b b r s 和基于 预粗略计算s k y l i n e 的r s s a 算法。文献 2 8 】中将r e v e r s es k y l i n e 查询应用到了 不确定数据集上，文献 4 5 】将r e v e r s es k y l i n e 应用到了数据流上。 2 3 8 各种应用环境下的s k y l i n e 查询 s k y l i n e 查询同时还被应用到了很多其它的地方：文献【3 8 ，3 9 ，5 1 对分布式数 据库环境下的是s k y l i n e 查询进行了研究。p 2 p 网络中的s k y l i n e 应用则首次是 在文献 4 0 l 中被提出的，文献 5 2 1 中研究了p 2 p 网络中的子空间s k y l i n e 查询。文 献 3 3 】中给出了公路网中的s k y l i n e 查询。文献【4 1 】中讨论了m e t r i cs p a c e 中的 s k y l i n e 查询。文献【4 2 给出了多关系表情况下s k y l i n e 查询。文献 4 6 ，4 7 对s k y l i n e 查询引入了更灵活的机制，允许用户自定义元素维度间的比较规则。限于篇幅的 原因，还有很多相关的s k y l