（计算机软件与理论专业论文）时间序列中的k支配skyline算法研究.pdf

中山大学硕士学位论文 时间序列巾的i 卜支配s k y l i n e 算法研究 时间序列中的k 一支配s k yi 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 查询就是要快速地求出这 些对象在最近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 的点数过大的情况。为了解决这个问题，本文将k - 支配的概念和时间序 列s k y l i n e 的概念相结合，引入了时间序列中k 一支配s k y l i n e 的概念，然后提出了 查找时间序列中k 支配s k y l i n e 的两个新算法。具体来说，本文考虑到在时间序 列中对象和对象支配关系的变化情况，提出了利用点的最大被支配维数 m a x k d o m 来排序和剪枝的方法，进而提出了i b a t s 算法。另外，为了适应高维 数据的情况，又考虑到时间序列的特点，本文提出了一种增量计算最优k 个维度 和最差k 个维度的方法，从而提出了i b a t s h d 算法。实验表明，本文提出的算 法比现在的算法有更好的性能。 关键词：s k y l i n e ，时间序列，k 支配s k y l i n e 中山大学硕十学位论文时间序列中的k - 支配s l 刚i n e 算法研究 r e s e a r c ho i lk - d o m i n a n ts k y l i n ea l g o r i t h m s m a j o r ： n a m e ： rln1 l nl l m e3 e r l e s c o m p u t e rs o f t w a r ea n dt h e o r y w uz h u o j u n s u p e r v i s o r ：p r o f e s s o ry i nj i a n a b s t r a c t s k y l i n eq u e r i e sa r ev e r yi m p o r t a n ti nm u l t i - c r i t e r i ad e c i s i o nm a k i n ga p p l i c a t i o n s t h es k y l i n eo fad a t as e ti st h es e to fp o i n t sw h i c ha r en o td o m i n a t e db yo t h e r s s k y l i n eq u e r i e sc a na l s ob eu s e di nt i m es e r i e s c o n s i d e rt h eo b j e c t sh a v i n gav a l u e a s s o c i a t e dt oi ta te a c ht i m e s t a m p ，e g ：t h ep o w e rc o n s u m p t i o no far e g i o n w er e g a r d t h ev a l u eo ft h eo b j e c to fat i m e s t a m pa sa na t t r i b u t e ，a n du s et h ec o n c e p to fs k y l i n e ， t h e nw eg e tt h ec o n c e p to ft i m es e r i e ss k y l i n e t h ep r o b l e mo ft i m es e r i e ss k y l i n e q u e r i e si st oc a l c u l a t et h es k y l i n eo ft h em o s tr e c e n tdt i m e s t a m p se f f i c i e n t l y s i m i l a rt ot r a d i t i o n a ls k y l i n e s ，a sd i m e n s i o ni n c r e a s e s ，t h e r ew i l lb eal a r g e n u m b e ro fs k y l i n ep o i n t si nt i m es e r i e ss k y l i n e s t os o l v et h i sp r o b l e m , w ec o m b i n e t h ec o n c e p to fk d o m i n a n ts k y l i n ew i t ht i m es e r i e ss k y l i n e ，t h e np r o p o s et h ec o n c e p t o fk - d o m i n a n ts k y l i n ei nt i m es e r i e s ，a n dp r o p o s et w on e wa l g o r i t h m st of e n d k d o m i n a n ts k y l i n ei nt i m es e r i e s s p e c i f i c a l l y , w eo b s e r v et h ec h a n g eo fo b j e c t d o m i n a n tr e l a t i o n s h i p si nt i m es e r i e s ，p r o p o s eas o r t i n ga n dp r u n i n gm e t h o du s i n gt h e m a x i m u mn u m b e ro fd o m i n a t e dd i m e n s i o n a l i t i e s ，m a x k d o m , a n dp r o p o s et h ei b a t s a l g o r i t h m i na d d i t i o n , i no r d e rt oa d a p tt ot h es i t u a t i o no fh i g hd i m e n s i o n a l i t yi nt i m e s e r i e s ，w ep r o p o s ea ni n c r e m e n t a lm e t h o dt oc o m p u t et h eb e s tka n dw o r s tk d i m e n s i o n s ，a n dp r o p o s et h ei b a t s h da l g o r i t h m e x p e r i m e n t ss h o wt h a to u rn e w a l g o r i t h m sa r es u p e r i o rt oe x i s t i n go n e s k e yw o r d s ：s k y l i n e ，t i m es e r i e s ，k d o m i n a n ts k y l i n e i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：墨主塑 日期：羔堡 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：吴车钧 日期：砷年f 月f 日 导师繇矽警 闩期：垆7 年罗月哆同 中山大学硕士学位论文时间序列中的k 一支配s k y l i n e 算法研究 第1 章绪论 1 1 s k y l i n e 的相关查询 数据挖掘( d a t am i n i n g ) 是指从大量数据中提取或“挖掘 知识的一个过程 【1 】。而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 查询引入到数据库 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 的点，当且仅当它不被其它任何的点支配。一个d 维空间上的点p 支配 ( d o m i n a t e ) 点q ，当且仅当在每一个维度上p 的取值都不比q 差，并且存在一 个维度，在这个维度上p 的取值比q 好。 可以通过一个例子来说明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 的点，c yc h a r t 等人提出了k 一支配s k y l i n e 的概念 3 】。一个点pk - 支配 ( k d o m i n a t e ) 点q ，当且仅当存在k 个维度，p 在这k 个维度中的每一个维度上 的取值都不比q 差，并且在这k 个维度中存在一个维度，在这个维度上p 的取值 比q 好。一个点集中所有不被其它点k - 支配的点的集合就组成了这个点集的k - 支配s k y l i n e 。c h a n 等人还提出了查找一个点集的k 支配s k y l i n e 的三种算法，即 o n e s c a n 算法，t w o s c a n 算法和s o r t e dr e t r i e v a l 算法。另外，姚树宇也在他的 硕士论文中提出了一种基于索引的算法来解决k 一支配s k y l i n e 查询的问题【4 】。 中山大学硕士学位论文时间序列巾的k 支配s k y l i n e 算法研究 另外，由于我们通常需要处理多个时间序列的数据。我们可以将一个时刻看 成一个属性( 或者维度) ，将一个时间序列在最近d 个时刻的取值看成是一个d 维的点，那么我们就可以查找这些时间序列( 下文有时也会将时间序列称为点) 集合的s k y l i n e 5 】。查找时间序列的s k y l i n e 是有其应用价值的，因为可以查找出 令人感兴趣的时间序列。例如，网站中的一个网页在每一天的点击量就组成了一 个时间序列，我们会对最近的d 天内，不在每天都比其它网页点击量少的网页感 兴趣，因为这些网页会在某些偏好下是热门的网页，也是我们潜在的兴趣所在。 在时间序列中，随着时间的推移，最近的d 个时刻在不断地发生变化，这些时间 序列的数据也在跟着发生变化。时间序列s k y l i n e 的查询就是要在不断变化的时 间序列中不断地找出最近的d 个时刻的时间序列的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 的解决方法，将k - 支配 s k y l i n e 的概念和时间序列s k y l i n e 的概念相结合，提出了时间序列中k 支配 s k y l i n e 的概念，然后又提出了查找时间序列中k - 支配s k y l i n e 的两个新算法。 在算法的设计中，本文考虑到在时间序列中点和点的支配关系的变化情况， 并利用点的最大被支配维数m a x k d o m 来反应这种变化的情况。然后考虑到维护 m a x k d o m 需要比较大的开销，所以利用了m a x k d o m 的下界m a x k d o m l b 来近似地 表示m a x k d o m ，并提出了利用m a x k d o m l b 来排序和剪枝的新算法，i b a t s 算法。 另外，由于时间序列通常都有很高的维度，又由于不考虑时间序列的时候计算最 优k 个维度和最差k 个维度的开销比较大，为了适应高维数据的情况，以及考虑 到时间序列的特点，本文提出了一种增量计算最优k 个维度和最差k 个维度的新 方法，并提出了i b a t s h d 算法。 实验表明，在多数情况下本文提出的算法在处理时间序列的数据上比现在的 算法有更好的性能。 本文一共6 章，余下章节的组织结构如下： 第2 章介绍了s k y l i n e 查询的定义，各种经典的算法，和最新的查询算法。 2 中山大学硕士学位论文 时间序列中的k 支配s k y l i n e 算法研究 第3 章介绍了k - 支配s k y l i n e 的定义、性质，又详细介绍了三种基本算法和 一种基于索引的算法。 第4 章主要阐述了时间序列中的k 支配s k y l i n e 查询所要解决的问题，分析 了现有算法的不足，然后提出了时间序列中k 支配s k y l i n e 查询的两个新算法， i b a t s 算法和i b a t s h d 算法，并对算法时间和空间复杂度进行了分析。 第5 章是实验和结果，包括实验环境和对两个合成数据集进行实验所得到的 结果，以及相应的分析。 第6 章是对全文工作的总结和对未来工作的展望。 中山大学硕士学位论文时问序列i | i 的k 支配s k y l i n e 算法研究 第2 章s k yi in 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 的定义 假设我们要到海滩度假，要寻找一间酒店来住宿。并且假定我们只考虑酒店 的两个因素，价格和离海岸线的距离。通常，这两者之间是成反相关关系的，离 海岸线的距离越近，价格就会越高，离海岸线的距离越远，价格就会越低。我们 通常会根据自己的实际情况在这两个因素之间选择一个平衡点，选择一个自己认 为的价格和距离都比较不错的酒店来住宿。但是不同的消费者的实际情况是不同 的，他们会有不同的偏好，所以他们会选择不同的酒店。但是，有一些酒店是我 们不需要考虑的，这就是那些价格又高、距离又远的酒店。我们可以利用计算机 软件来排除掉这部分的酒店，只留下那些我们有可能感兴趣的酒店供我们选择。 那么这些供我们选择的酒店就是所有酒店的s k y l i n e 。具体来说，酒店的s k y l i n e 就是那些不会在距离和价格上都比其它酒店差的那些酒店。举例来说，如果酒店 a 的价格是5 0 元，距离是0 8 公里，酒店b 的价格是1 0 0 元，距离是1 0 公里。 那么显然酒店a 在价格和距离两个维度上都比酒店b 好，计算机软件就应该排 除掉酒店b ，只留下酒店a 。 图2 1 显示了酒店s k y l i n e 的一个例子 2 】。图中的每一个点表示一间酒店， 横坐标表示的是酒店的价格，纵坐标表示的是酒店离海滩的距离。图中左下角用 线连起来的点组成了酒店的s k y l i n e 。 下面给出s k y l i n e 的定义【3 】： 给定一个d 维空间s = s l ，s 2 ，s o ，点集d = p l ，p 2 ，p 。) 被称为是s 上数据 集，如果d 中的每一个点p i 都是s 中的数据点。我们用p i s j 来表示点p i 的第j 个维度。我们假设对于每一个维度s i 都存在一个全序的关系 ”关系。 蝴1 0 01 5 d揶 图2 1 酒店的s k y l i n e 定义2 1 支配 s 中的点p i 支配点p j ，当且仅当v s k s ，p i s k 一 p j s k ，并k 3 s t s ，p i s t p j s t 。 定义2 2s k y l i n e ，s p ( d ，s ) 一个点p i 是s 的s k y l i n e 的点，当且仅当不存在一个点p j ，使得p j 支配p i 。 我们用s p ( d ，s ) 表示数据集d 上、空间s 上的s k y l i n e 的点的集合。 s k y l i n e 具有如下一些性质： ( 1 ) 如果点p 支配点q ，那么对于所有单调的评分函数f 有坟p ) 坟q ) 。 例如酒店a 支配酒店b ，那么无论用户对距离和价格两个维度的偏好( 权 重) 是怎样的，他都会选择酒店a ，而不选择酒店b 。 ( 2 ) 对于s k y l i n e 中的每一个点p ，存在一个单调的评分函数f ，使得对于s 中任意的点q ，有如) f 【q ) 。 即，对于s k y l i n e 中的每一个点p ，存在一种用户的偏好，使得p 是在这种 偏好下，用户希望找到的点。 ( 3 ) 对于任意一个单调的评分函数f ，如果s 中的点p 使得对于s 中的任 意点q ，有f ( p ) f ( q ) ，那么p 一定是s k y l i n e 点。 也就是说，对于任意一种用户偏好，总能在s k y l i n e 中找到他所希望的点。 s k y l i n e 可以被广泛应用在各种多准则的决策支持之中。其中最经典的例子 就是上面的海滩度假的例子。它也可以应用在n b a 的球员挖掘上面。n b a 的球 2 孓 t 5 ， t o o 中山大学硕士学位论文 时问序y u q , 的k - 支配s k y l i n e 算法研究 员有得分、篮板、助攻、盖帽等数据，球队的老板或者教练要根据这些维度的不 同权重来选择不同位置( 如前锋、中锋) 的球员，而无论是赋予一个怎样的权重， 他们总能在s k y l i n e 中找到他所需要的出色的球员。 2 2 经典算法介绍 这一节主要介绍s k y l i n e 查询的经典算法，包括：( 1 ) 块嵌套循环算法 ( b l o c k - n e s t e d 1 0 0 pa l g o r i t h m ) ，( 2 ) 分而治之算法( d i v i d ea n dc o n q u e r a l g o r i t h m ) ，( 3 ) 位图算法( b i t m a p ) ，( 4 ) 索引算法( i n d e x ) ，( 5 ) 最近邻算法 ( n e a r e s tn e i g h b o r ) ，和( 6 ) 分支限界s k y l i n e 算法( b r a n c ha n db o u n ds k y l i n e ) 。 2 2 1 块嵌套循环算法( b l o c k - n e s t e d l o o pa l g o r i t h m ) 块嵌套循环算法【2 】简称b n l 。它是基于一个最简单方法，就是将数据集中 的每一个点和所有的其它点进行比较，最终得到全部s k y l i n e 的点。算法具体是 这样做的：b n l 算法保存一个临时的窗口，用这个窗口来保存候选的s k y l i n e 的 点。输入的第一个点会被放到这个窗口里面。然后读取下一个点p ，这时候会遇 到下面三种情况的一种： 1 、p 被窗口中的一个点支配。这时候p 就可以被安全地舍弃掉，因为p 不 可能再成为s k y l i n e 的点。 2 、p 支配了窗口中的一个或多个的点。这时候应该把这些被支配的舍弃掉， 然后把p 加入到窗口里面。 3 、p 和窗口中的点互不支配。这时候如果窗口还有空余的位置就把p 加入 到窗口中，否则，就把p 写入一个临时文件中。这些被写入临时文件中的点会在 下一次循环的时候再次被读入和进行比较。 在一次循环结束的时候，在窗1 3 中的点可以输出为s k y l i n e 的点，然后把临 时文件的内容重新作为输入，并重复上面的过程，直到临时文件为空。 b n l 的一种优化的方法是将临时窗口组织成为一个自组织的链表，这个链 表把那些经常支配其它点的点移到链表的开头，这样能够减少一个点被支配时所 需要的比较次数。 b n l 算法的优点是容易编程实现，能被广泛地应用。因为它没有维度上的 6 中山大学硕士学位论文 时问序列中的k 支配s k y l i n e 算法研究 限制，也不需要对数据文件进行索引或者预排序。它的最大问题在于它对内存的 要求比较大，如果数据放不进内存，就需要进行多次的磁盘读写。另外，它也不 能支持在线的处理，因为它必须读完了全部的输入才能开始进行输出。 2 2 2分而治之算法( d i v i d ea n dc o n q u e ra i g o r i t h m ) 分而治之算法 2 】简称d & c 。它的基本想是在某一个维度( 例如价格) 上面 选一个中间值i i l p ，把整个数据集按照这个维度的值是比1 1 1 p 大还是比m p 小划分 成两部分p l 和p 2 。然后分别递归调用d & c 算法分别计算p i 和p 2 的s k y l i n e 。最 后把这两部分的s k y l i n e 合并成为原来数据集的s k y l i n e 。 在划分的时候可以是按照多个维度来进行划分，例如按照两个维度把数据集 划分成为s 1 1 ，8 1 2 ，s 2 l 和s 2 2 ，那么在合并的时候可以直接把s 2 2 的s k y l i n e 舍弃掉， 将s l l 的s k y l i n e 直接输出到最后的s k y l i n e 中，将s 1 2 ，s 2 l 的s k y l i n e 分别和s 1 l 的 s k y l i n e 进行比较，去除掉那些被支配的点后再作为最终的输出返回给用户。 d & c 算法对于小的数据集有不错的效果，但是对于大的数据集因为在划分 阶段需要读取整个数据集，所以导致了比较大的i o 开销。另外，d & c 算法也 不能适应在线的处理，它不能在划分阶段完成以前开始输出。 2 2 3 位图算法( b i t m a p ) 位图算法由k 一l t a n 等人在 6 】上提出。这个算法可以在预处理完以后快速 地回答一个点是否属于s k y l i n e 。它的快速是基于计算机能够对位操作进行高效 的处理。 对于一个d 维的数据集d ，我们假设在第i 个维度上有k i 中可能的取值，那 么对于d 中一个数据点x = x x ，x 2 90 1 1 凝) ，可以用l n _ j - 1 4 k j 位来表示，其中第i 个维度用k i 位来表示。假设x i 是在第i 个维度上第j i 小的值，那么就将x i 就编码 成k i - j 0 - 1 个1 后面接着j i - 1 个o 。把x i ，x 2 ，x d 的编码连在一起就组成了x 的编 码。将每一个数据点的编码排成一行，那么所有数据点就编码成为一个n 幸m 的 矩阵，其中n - - i d i 。 在判断一个点x 是否为s k y l i n e 的点的时候，对于每一个x i 找出它的编码的 最后一个1 所在的位置，然后将这些位置所在列的编码全部取出来，组成一个列 7 中山大学硕士学位论文 时问序列巾的k - 支配s k y l i n e 算法研究 向量c i ，然后再对所有的c i 做位的与操作。如果得到的结果只有一个1 ，那么x 就是s k y l i n e 的点，否则x 就不是s k y l i n e 的点。 这个算法的一个明显的缺点是要得到s k y l i n e 就必须对所有的点都进行一遍 上述的计算。而且位图算法也不能适应不同的用户偏好。另外，它的空间开销也 是很大的，而且也不能适应动态数据集的计算，因为一旦数据集发生了变化就必 须重新计算位图的值。 2 2 4索引算法( i n d e x ) 索引算法【6 】的基本思想是这样的：对于一个d 维的数据集d ，它维护d 个 索引表，算法对d 中的每一个点x ，计算x 在d 个维度中的最大值所在的维度i ， 然后把x 插入到第i 个索引表里面。第i 个索引表里面的点是按照第i 个维度的 值从大到小进行排列的。算法然后开始循环，对于所有的i ，找出第i 个索引表 的第一个元素的第i 个维度值的最大值。假设这个最大值出现在第j 个索引表， 那么算法就对第i 个索引表找出第j 维的值最大的那些点，然后求出这些点的 s k y l i n e ，并进行输出。这样一直循环下去，直到所有索引表的全部数据都被考察 出 兀。 索引算法利用到一个剪枝的条件是：对于一个已经处理过的点x ，假设x 在 它的d 个维度中的最小值是m ，如果m 已经大于第i 个索引表的第一个点的第i 个维度的值，那么就可以将第i 个索引表后面的点全部舍去。 虽然索引算法可以快速地返回部分的s k y l i n e 的点，但是和位图算法一样， 它不能支持不同的用户偏好。另外，这d 个索引表不能被用于d 的子集的s k y l i n e 搜索，要进行子集计算就必须计算指数数量的索引表。 2 2 5最近邻算法( n e a r e s tn e i g h b o r ) 最近邻算法【7 】( 简称n n ) 提供了一种渐进的可以快速得到s k y l i n e 的大概 分布的高效的算法。n n 算法是基于这样一个观察：离原点最近的点一定是属于 s k y l i n e 。 假设对于一个二维的数据集，n n 算法的过程是这样的：首先把全空间【o ， o o ) 0 ，) 加入到待处理的列表t 中，然后每次从t 中取出一个区间a - o ，a x ) 0 ，a y ) ， 2 中山大学硕+ 学位论文时间序列中的k 支配s k y l i n e 算法研究 找出这个居间中离原点最近的点m ，把m 输出为s k y l i n e ，然后把a 分别在各个 维度上按照m 在这个维度的值进行划分，一共划分成为d 个矩形。假设 m = ( m x ，m y ) ，那么就把a 划分成为 o ，m x ) 0 ，a y ) 和 o ，a x ) 0 ，m y ) 。然后把这些矩形加入 到t 中，并迭代地处理t ，直到t 为空。 n n 算法在维度小于4 的时候效果都比索引算法 6 】好。但是当维度大于3 的 时候，由于空间的重复划分和计算以及r 树效率的下降，n n 算法的性能也在明 显地下降，而且也需要很大的存储空间。 2 2 6 分支限界s k y l i n e 算法( b r a n c ha n db o u n ds k y l i n e ) 和n n 一样，分支限界s k y l i n e 算法【8 】( 简称b b s 算法) 是一个基于最近邻 搜索的渐进s k y l i n e 查询算法。但是它有最优的i o 性能，即它所需要访问的r 树的结点数是最少的，每个结点只需要访问一次。 下面介绍b b s 算法的基本思想。b b s 算法将数据点组织成r 树来存储。对 于r 树的每个最小包围矩形( r ) ，用它的左下角的坐标来计算它的m i n d i s t 。 对于叶子结点，则直接通过它的坐标来计算m i n d i s t 。这里，m i n d i s t 用l l 范数来 计算，即各个维度的坐标之和。 算法一开始的时候将r 树的根结点插入到一个最小堆中，这个堆是按照 m i n d i s t 值来排列的。然后算法每一次从堆中取出一个元素，并且判断它有没有 被已经找到的s k y l i n e 的点所支配，如果已经被支配则直接删除。否则，如果它 是叶子结点，则加入到s k y l i n e 中，如果它是中间结点，则判断它的各个孩子结 点有没有被已经找到的s k y l i n e 的点所支配，并把那些没有被支配的结点插入到 这个最小堆中。一直重复上述过程，直到最小堆为空。 8 】还说明了b b s 算法满足下面6 个评价准则：1 、渐进性，2 、不会遗漏s k y l i n e 的点，3 、不会有错误的临时s k y l i n e 的点，4 、对各个维度是公平的，5 、可以结 合用户偏好，6 、具有通用性，即可以用于任何的数据集的分布和维度，使用任 何的标准的索引结构。 2 3 最新算法介绍 前面一节介绍的是s k y l i n e 查询的经典算法，这些算法解决的问题都是如何 9 中山大学硕士学位论文时间序列中的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 查询的算法。 2 3 1 子空间s k y l i n e 查询 s k y l i n e 查询通常包含有很多属性，但是不是所有的用户都对所有的属性感 兴趣的，子空间的s k y l i n e 查询就是用来解决这个问题的 9 - 1 4 】。 和数据立方体类似的，不同的属性组合可以组成不同的方体，所有这些方体 的集合就是s k y c u b e 。 1 2 提出了计算s k y c u b e 的两种算法：b o t t o m - u p s k y c u b e 和t o p d o w ns k y c u b e 算法。 由于不同的用户会对不同的子空间感兴趣，所以我们需要查询不同子空间的 s k y l i n e 。如果只对一个特定的子空间做索引，就会影响对其它子空间的查询效率。 1 3 提出了一种对全空间的数据预处理和剪枝方法，这个方法使得对于不同的子 空间上的查询也有不错的运行效率。 f 1 4 解决的问题是在哪些子空间中，一个点能够成为这个子空间的s k y l i n e ， 它提出了s k y l i n eg r o u p 和d e c i s i v es u b s p a c e s 的概念和s k y e y 算法来解决这个问 题。 2 3 2 数据流的s k y l i n e 查询 数据流的s k y l i n e 查询考虑的是，在不断有新的数据点产生、旧的数据点过 期的情况下，如何有效地进行s k y l i n e 查询的问题。 【1 5 考虑的是用户可能会对最近n 次交易的s k y l i n e 感兴趣，而不同的用户会 对不同的n 感兴趣，于是提出了n - o f - n 查询来查找最近n 个点的s k y l i n e 。同时， 作者也提出了( n l ，n 2 ) o f - n 查询。并提出了支持这两种查询的新算法。 1 6 考虑的问题是每个数据点都有一个有效的时间段( i n t e r v a l ) ，并提出了 l o o k o u t 算法来连续地求出每一个时刻的s k y l i n e 。 1 7 1 提出了两种增量维护s k y l i n e 的框架：l a z y 和e a g e r 框架。 1 0 中山大学硕士学位论文 时间序列巾的k - 支配s k y l i n e 算法研究 2 3 3 k - 支配s k y l i n e 查询 由于随着维数的增加，一个点支配另外一个点的机会越来越少，所以导致 s k y l i n e 的数量也变得很大，从而减d , ts k y l i n e 对决策支持的作用。 3 】将支配的 概念放松成为k - 支配的概念来解决这个问题。 4 】介绍了另外一种k - 支配s k y l i n e 的查询算法。关于k - 支配s k y l i n e 的内容会在第3 章详细介绍。 2 3 4 时间序列s k y l i n e 查询 时间序列的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 考 虑的是不断有新的数据点到来和老的数据点的过期，每个数据点都包含有d 个属 性值。而时间序列的s k y l i n e 在一个新的时刻对所有的时间序列( 数据点) 都有 更新，而不是只有一个时间序列产生了变化，并且更新的是这些时间序列的最新 一个维度的值。 5 】考虑的是求时间序列的区间( i n t e r v a l ) s k y l i n e 的问题，也就是在最新的 d 个时刻内，要求出在区间 i j 这个时间段内的s k y l i n e ，这里支持的是对不同的 i 和j 的都有很好的查询效率。 2 3 5 分布式的s k y l i n e 查询 分布式s k y l i n e 查询要解决如何在分布式的网络环境下有效地计算s k y l i n e 的 问题 1 8 2 3 。 2 3 认为这时候主要要考虑两种访问的开销，即排序访问和随机访问的开 销。它提出了一种基本算法和两种优化的算法来解决这个查询问题。 2 3 6 偏序集的s k y l i n e 查询 因为在有一些属性上面不存在全序的关系，而只存在偏序的关系。例如：上 中山大学硕士学位论文 时间序列中的k - 支配s k y l i n e 算法研究 司和下属的领导关系。在这时候，已有的算法不能很好地解决这个问题， 2 4 提 出了求偏序集中s k y l i n e 的方法。它的基本思想是将偏序集的元素转换成为用两 个整数表示的一个区间，并且尽量使这种转换保持原来集合上的偏序关系。基于 这一点，文章提出了b b s + 算法，s d c 算法和s d c + 算法来解决这个查询问题。 2 3 7 用户偏好的s k y l i n e 查询 在一些属性上，不同的用户会有不同的偏好，例如在颜色、款式、地点、航 班上的选择等等。因为有的用户会喜欢蓝色，而有的用户会喜欢红色。这种不同 的用户偏好给s k y l i n e 查询提出了一个新的挑战。 2 5 将这种属性称为名义属性，它考虑的是对于一个点p ，要求出名义属性 满足怎样的偏序关系，才能是p 成为s k y l i n e 的点。 【2 6 2 7 也是解决带有用户偏好的s k y l i n e 查询问题。 2 3 8 其它相关的s k y l i n e 查询 r 宰树 2 8 】是一种高效的高维空间索引结构，在s k y l i n e 查询中经常起着重要 作用，已经在很多文章中被广泛使用。【2 9 提出了求运动物体的s k y l i n e 的方法。 【3 0 介绍了基于概率的s k y l i n e 查询。 3 1 介绍了近似的s k y l i n e 计算。 另外，其它相关工作还包括 3 2 3 8 。 同时，国内的相关研究包括有 3 9 - 4 6 。 1 2 中山大学硕士学位论文 时问序列中的k 支配s k y l i n e 算法研究 第3 章k 一支配s k y iin 6 查询 上一章介绍了s k y l i n e 查询的经典算法和最新的研究方向，这一章详细介绍 k - 支配s k y l i n e 查询的定义和算法。首先是它的定义和性质，然后是三种基本的 查询算法，即一次扫描算法( o n e - s c a na l g o r i t h m ) ，两次扫描算法( t w o - s c a n a l g o r i t h m ) ，排序索引算法( s o r t e dr e t r i e v a la l g o r i t h m ) ，和另外一种基于索引的 算法( i n d e x - b a s e da l g o r i t h m ) ，以及对它们优缺点的分析。 3 1 k - 支配s k y li n e 查询的定义和性质 考虑一个电影评分的系统，里面有很多电影，也有很多观众，每一位观众都 可以对这些电影进行评分。我们用一个二维的表格( 表3 1 ) 来表示这个系统 的数据，每一行表示一部电影，每一列( 每一个属性) 表示一个用户，表格中的 内容表示某个用户对某部电影的评分。 表3 1 电影评分系统 用户1用户2用户3用户4 电影1 电影2 电影3 我们可以查找这些电影的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 。而现在出现的 问题是这样的电影的数量太大， 3 的作者认为其中的原因就是因为需要所有的 中山大学硕士学位论文n , t f j 序列中的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 的点的数量。例如我们假设一共 有1 0 0 个用户，只需要其中有9 8 个用户认为另外一部电影比这部电影好，就说 明这部电影不够另外的那部电影好，所以就应该把这部电影从原来的s k y l i n e 中 去除掉。这样就能够解决原来s k y l i n e 点数过多的问题。这里作者就使用了k 一支 配的概念，在这个例子中k 就等于9 8 。 下面形式化地给出k _ 支配和k - 支配s k y l i n e 的定义 3 】。 定义3 1k 一支配 d 维空间s 中的点p i k 一支配点p j ，当且仅当存在s s s ，i s l = k ，满足v s ，e s ， p i s r p j s r ，并r 3 s t s ，p i s t p j s t 。 其中当k = d 的时候k 一支配的定义就是原来支配的定义。 定义3 2k 一支配s k y l i n e ，d s p ( k ，d ，s ) 一个点p i 是s 的k - 支配s k y l i n e 点，当且仅当不存在点p j ，使得p jk 一支配支 配p i 。 我们用d s p ( k ，d ，s ) 表示数据集d 上、空间s 上的k 支配s k y l i n e 点的集合。 有时也简称为d s p 。并用i d s p 表示d s p 中点的数量。 表3 2 一个数据集的例子 点维度 s is 2s 3s 4s 5s 6 p l 44422 2 p 2 22244 4 p 3 33 3133 p 4 1 1151l p 5 22233 3 例3 1 假设有表3 2 这样的数据集d 。d 有6 个维度s l ，s 6 ，5 个数据点 p l ，p s 。其中p l ，p 2 ，p 3 ，p 4 是s k y l i n e 的点，因为p 4 被p 25 - 支配了，所以只有p l ，p 2 ，p 3 是5 - 支配s k y l i n e 的点。 1 4 巾山大学硕十学位论文 时问序列中的k 支配s k y l i n e 算法研究 下面给出k - 支配的一些性质： 引理3 3 如果p i ( k + 1 ) - 支配p ! j ，那么p i 一定k - 支配p j 。 定理3 4 如果一个点p i e d s p ( k ，d ，s ) ，那么p i d s p ( k + i ，d ，s ) 。 推论3 5l d s p ( k , d ，s ) i i d s p ( k + i ，d ，s ) l 。 推论3 5 告诉我们，k 支配s k y l i n e 的点数随着k 的下降在不断下降，所以当 k 取