（计算机应用技术专业论文）高维数据集skyline计算研究.pdf

摘要 摘要 随着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 计算面临以下挑战：( 1 ) 维度灾难即随 着数据集规模增大维数增多，s k y l i n e 查询的结果数目将随数据集大小和维数( d ) 呈指数增长。 得到的s k y l i n e 查询结果集巨大，不能提供有效信息。( 2 ) 计算代价高s k y l i n e 算法的开销本来 就比较大，其中b n l ，s f s 和l e s s 算法最坏情况复杂度均达到了o ( 1 ( n 2 ) ， k 是查询空间的维数， n 是数据对象个数。( 3 ) 算法要求高算法不仅需要正确得出s k y l i n e 结果，还应具有渐进性 ( p r o g r e s s i v e ) 和偏好性( p r e f e r a b l 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 点输出数目过多的问题。深入分 析了高维空f 司s k y l i n e 计算的特点及难点，在此基础上提出了一种基于排序的高维数据集s k y l i n e 算法。 算法采用一种新颖的预排序结构，并结合已有算法的优点，能够较好地达到算法要求。与现有同类 算法相比，具有以下优点：( 1 ) 可以根据用户的需求，顺序输出结果，减少用户后期筛选数据点的 计算量。( 2 ) 根据预处理结构的特点，可以保证优先扫描较好的点，能够快速渐进地返回s k y l i n e 结 果。( 3 ) 采用优化启发式规则减少访问的数据点数目，无需访问整个数据集就能得到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 相关度的概念，进一步改进了本文提出 的算法，精简了 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 s k y l i n eq u e r yp r o c e s s i n gh a sr e c e n t l yr e c e i v e dal o to fa t t e n t i o ni nd a t a b a s ec o m m u n i t y t h i si s m a i n l yd u et ot h ei m p o r t a n c eo fs k y l i n er e s u l t si nm a n ya p p l i c a t i o n s s u c h 鹊m u l t i - c r i t e r i ad e c i s i o n m a k i n g ，d a t am i n i n g ，u s e rp r e f e r e n c ea n dv i s u a l i z a t i o no fd a t a b a s e m a n ya l g o r i t h m sh a v eb e e np r o p o s e d ， h o w e v e r ，t h ep r e v i o u sw o r ko fs k y l i n ec o m p u t i n go nh i g hd i m e n s i o n a ld a t a s e ti ss t i l ll i m i t e db e c a u s et h e d i f f i c u l t yo f d i m e n s i o n sa n dd a t as i z e f i r s t ，d i m e n s i o n a l i t yp r o b l e m - - a sd a t as e t sw i t hm a n yd i m e n s i o n s ， t h en u m b e ro fs k y l i n ep o i n t sb e c o m e sl a r g ea n dn ol o n g e ro f f e ra n yi n t e r e s t i n gi n s i g h t s 。s e c o n d ，s k y l i n e c o m p u t a t i o n sa r en o tc h e a pa n dt h ew o r s tc a s eo fb n l ，s f s ，l e s sw i t ho ( k n 2 ) i su n a c c e p t a b l e t h i r d ， a c c o r d i n gt ot h ec r i t e r i a , a l g o r i t h ms h o u l db ep r o g r e s s i v ea n dp r e f e r a b l e ，w h i c hr e q u i r es h o r tr e s p o n d i n g t i m ea n df r i e n d l i n e s st ot h eu s e r s c o n s i d e rt h et w i nd i f f i c u l t yo fh i g hd i m e n s i o n a ld a t a s e t ，w ef o c u so nt h es k y l i n ec o m p u t i n go n p r o b l e mo ft o om a n ys k y l i n ep o i n t si nl a r g e s i z e r e s u l ts e t a ne f f i c i e n th i g hd i m e n s i o n a ls k y l i n e c o m p u t i n gm e t h o db a s e do np r e s o r t i n gt h a tc o m b i n i n gs e v e r a la l g o r i t h m ss t r e n g t hi sp r o p o s e d ，w eu s ea n o v e ld a t as t r u c t u r et os o r tt h ea t t r i b u t ev a l u e si ne a c hd i m e n s i o na n dp u t st h em o s tp o s s i b l es k y l i n ep o i n t s t ot h ef o r e s i d e ，t h u sa s s u r i n gt h a ta l g o r i t h mc a l lr e t u r nt h es k y l i n ep o i n t sp r o g r e s s i v e l ya n de f f e c t i v e l y i t c a na l s oo u t p u tt h er e s u l t so r d e r l ya n dr e d u c eu s e r s w o r k l o a dg r e a t l y m o r e o v e r o p t i m i z i n gh e u r i s t i c si s p r e s e n t e dt os p e e du pt h e s ep r o c e s s e s t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t sd e m o n s t r a t et h a tt h ep r o p o s e d a l g o r i t h mh a sg o o dp r o g r e s s i v e n e s sa n dt h em e t h o di se f f i c i e n t o nt h eo t h e rh a n d ，w ef i r s tf o c u so nt h e f i l t r a t i o ns t r a t e g i e sw h e nt h e r ei st o om u c hs k y l i n ep o i n t s t of i n dm o r ei m p o r t a n ta n dm e a n i n g f u ls k y l i n e p o i n t si nh i g hd i m e n s i o n a ls p a c e ，w ea n a l y z es e v e r a ln e wc o n c e p tc a l l e dk - d o m i n a n ts k y l i n e ，s k y l i n e f f e q u e n c ea n ds a m p l i n ga l g o r i t h m sw h i c he i t h e rr e l a x e st h ed e f i n t i o no fs k y l i n eo rt h ea l g o r i t h m sp r e c i s i o n w ei n t r o d u c et w om e a s u r e m e n t so fd i m e n s i o nw e i g h ta n ds k y l i n ec o r r e l a t i v i t yt of u r t h e ri m p r o v eo u r a l g o g r i t h mf o rd o w n s i z i n gt h es k y l i n er e s u l t sa n db e r e ru s e re x p e r i e n c e k e yw o r d s ：s k y l i n ec o m p u t i n g ，h i g hd i m e n s i o n a ld a t a s e t , p r o g r e s s i v ea l g o r i t h m ，f i l t r a t i o ns t r a t e g i e s 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：二垃日期：土气乒址 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 以电子信息形式刊登) 论文的全部内容或中、英文摘要等部分内容。论文的公布( 包括以电 子信息形式刊登) 授权东南大学研究生院办理。 躲婢名辞期：毕，垆 第一章绪论 1 1 研究背景 第一章绪论 随着信息技术的不断深入，越来越多的数据被收集并保存在数据库中，所收集数据的属性和所 隐藏的内容知识也愈加丰富，应用需求也越来越高。如何利用这些数据并按照用户的要求，从数据 库中高效获取信息已成为新一代数据库应用系统发展的目标。s k y l i n e 查询“引是指找出数据集中所 有不被任何其他点“支配”的对象集合。简单的说，支配是指给定两个d 维空间中的点x 和y ， 如果x 在任意一维上的评价值都不比y 差，且至少在某一维上的评价值优于y ，则称x “支配” y 。s k y l i n e 查询技术已经成为数据库领域的研究热点，它的应用范围很广，如多标准决策系统心1 ， 城市导航系统，数据挖掘和可视化“，用户偏好查询旧训，以及地理信息系统等领域。 下面来看一个经典的例子：如何选择景区酒店? 憧1 假设要去旅游胜地巴哈马首都拿骚( n a s s a u ) 度假，自然希望寻找一个价格便宜尽量靠近海边的酒店。不幸的是，这两方面考量是鱼和熊掌不可 得兼的关系。通常，越靠近海边的酒店价格越高，而价格便宜的酒店有可能距离很远。旅行社的数 据库管理系统也不能决定哪个是最好的酒店。这时，我们希望能够得知一些感兴趣的酒店以帮助做 出选择。实际上，如果不是两方面都很差的酒店，这样的酒店都是可以考虑的，我们称这样的酒店 组成的集合为s k y l i n e ，每个可以感兴趣的酒店为s p ( s k y l i n ep o i n t ) 点。 酒店编号距离( 公里)价格( 元) a6 33 0 b5 85 0 c5 21 0 0 d51 8 0 e4 1 1 5 0 f 4 7 0 g 21 7 0 h22 0 0 l2 9 8 kl1 6 5 p 6 5 1 0 0 q 3 2 1 2 5 r1 82 0 0 s3 1 5 0 表1 酒店距离与价格表 从表1 可以看出，a 点的价格是最低的，但是距离比较远；k 点是最近的酒店，但价格相对较高， 而f 的价格比c ，d ，e ，g ，h ，i ，k ，p ，q ，r ，s 都低，而离景区路途又比c ，d ，e ，p 更近，对于 旅游者来说，明显f 较好( 然而其他情况未必) 。同理，b ，i ，k 点情况同f 点。这样在旅游者偏好的 情况下得出了s k y l i n e 点a ，b ，f ，i ，k ( 表中灰色标记的行) 。有了这些感兴趣的数据点，就可以 综合考虑距离和价格作出选择了。 从酒店的例子可以看出s k y l i n e 计算是一个典型的多目标优化的问题引。当然，还有更多的领 东南大学硕士学位论文 域可以应用s k y l i n e 查询技术，例如多标准决策系统，城市导航系统，数据挖掘和可视化，智能防 御系统，以及地理信息系统等领域。 总结这些新应用产生的数据特点，集中表现为以下几个方面：一是数据量巨大；二是组成复杂， 维度多，并且数据可能随时间变化而变化；三是不同用户偏好不同。随着技术的不断发展，人们对 数据库查询的要求变得越来越高，不仅要求传统数据库查询结果的准确高效，而且还将探索s k y l i n e 与不同应用的结合，不仅要得到原始数据的结果，而且还要查询更加智能化。但现有的最大向量算 法【1 1 无法完全适应新的应用要求，一些新提出的s k y l i n e 算法也存在着诸多不足之处，因此，分析综 合现在的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 查询处理技术已经成为数据 库技术领域的一个研究热点。严格的说，它并不是一种新的技术，早在1 9 7 5 年就有文献以最大向量 问题( m a x i m a lv e c t o r ) 1 1 1 的形式讨论了其计算问题。最大向量算法的目标就是在所有多维矢量中，过 滤那些在各个维度上都不具有优势的矢量。对于过滤之后而剩下的那些矢量，它至少使得一个单调 函数取得最优值。随着数据库以及相关领域的成熟和壮大，人们又从数据库领域的自身特点出发来 重新研究最大矢量查询问题。文献【1 】针对2 维或3 维数据提出了一个查询复杂度为o ( n l o n ) 的算法， 针对大于3 维的数据，提出了查询复杂度o ( n ( 1 0 9 2 n ) 州) 的算法。文献【2 】首次提出把s k y l i n e 查询计算 整合至u s q l 3 数据库查询标准中的思想，并扩充了s q l 3 的语义。此后，众多学者将s k y l i n e 查询问 题从传统集中式数据库扩展到多种不同的应用环境中，逐渐涌现出更多的理论和成果1 4 lo 悼1 6 , 2 9 - 3 1 1 0 虽然经过了3 0 多年的发展，但直到最近1 0 年，国内外才出现了一些相关领域的研究成果。 s k y l i n e 计算的应用前景非常广阔，但理论，算法，模型仍然不够完善。从国际权威学者k u n ght ， l u c c i of 和p r e p a r a t af 合著的提出了最大向量计算问题的成果论文到国内学者的多篇相关论文的 发表，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 ，i c d e ，e d b t 等都 将s k y l i n e 查询研究作为其主题内容之一，0 7 年的v l d b 和i c d e 分别有6 篇和9 篇有关s k y l i n e 查 询问题的论文，为该领域的广大专家学者提供了广泛的交流机会。最近三年，每年有多篇s k y l i n e 相 关的论文发表在国内外各级期刊上，下面简要介绍国内外的研究现状及成果。 2 0 0 1 年i c d e ( i n t e m a t i o n a lc o n f e r e n c eo nd a t ae n g i n e e r i n g ) 会议上，b o r z s o n y i 等人1 2 j 首次将s k y l i n e 操作引入数据库系统，提出- j b n l ( b l o c kn e s t e dl o o p s ) 和d & c ( d i v i d ea n dc o n q u e r ) t 2 j 两种计算方法。 b n l 的优点是无需建立索引或把数据文件排序，就可以应用到任意维空间；缺点是依赖内存。当候 选列表比内存还大时，需要将列表中的部分数据保存到临时文件中，导致b n l 算法的多遍执行。d & c 方法是将数据集划分成多个分区，然后利用主存算法来分别计算每个分区内的局部s k y l i n e 点，再将 局部s k y l i n e 点筛选合并以得到最终的s k y l i n e 集。d & c 算法在数据规模较小时具有较高的效率，但对 于大数据集，划分合并过程会产生大量的i o 代价。这种方法不适合在线处理，因为它不能在分区阶 段完成之前返回任何s k y l i n e 点。 2 0 01 盔i z v l d b ( v e r yl a r g ed a t ab a s e s ) 龇，k l t a n 提出了位图法( b i t i n a p ) 和索引法( i n d e x ) 两种算法【3 1 。b i t m a p 将每一个点映射为一个位串，仅使用位运算来计算s k y l i n e 。虽然b i t m a p 能较 快计算出一些s k y i i n e 点， 但由于它每计算一个点都需要将这个点与其它所有点相比较，效率较低。 此外，b i t m a p 所采用的映射方式会导致位串的长度随各维上不同取值数的增大而急剧增加，耗费大 量的空间。索引轮廓查询方法( i n d e x ) 将每个点索引到它取值最小的维所对应的链表上，用b + 树做 2 第一章绪论 索引，分批处理数据点，具有较好的渐进性。但i n d e x 算法不具有良好的用户友好性，不支持用户定 义的优先选择标准。 2 0 0 2 年v d l b 会议上，d o n a l dk o s s m a n n 等人提出最近邻s k y l i n e 查询方法n n 【4 l ( n e a r e s t n e i g h b o r ) ，它根据用户自定义的距离公式，将所有数据用r 树索引。最近邻方法是一个公平的算法， 能够根据用户规定的顺序返回s k y l i n e 点，查询速度比前几种方法都快，但是对于高维数据来说，数 据空间的不断递归划分，存在严重的空间重合问题。 2 0 0 3 年的s i g m o d ( s p e c i a li n t e r e s tg r o u po nm a n a g e m e n to fd a t a b a s e ) 会议上，p a p a d i a s 提出了 分枝界定算法b b s ( b r a n c ha n db o u n ds k y l i n e ) p j 。b b s 也是基于最近邻搜索策略，且同样采用了r 树对数据索引，它为r 树的每个节点，或称为最小包容矩形( m i n i m u mb o u n d i n gr e c t a n g l e ，m b r ) 计算其最小距离。一个m b r 的最小距离等于这个矩形的左下角的点在各维上属性值的坐标之和。 利用最小堆结构，扩展节点数据，求出新的s k y l i n e 点。当数据库维数小于6 维时，b b s 展示出很高 的效率和很好的扩展性。但是当维数达到6 维以上时，性能也受到影响，但从渐进性，用户友好性综 合来看，被认为是比较优秀i 拘s k y l i n e 算法。 2 0 0 3 年i c d e ( i n t e r n a t i o n a lc o n f e r e n c eo nd a t ae n g i n e e r i n g ) 会议上，c h o m i c k i 等人提出了b n l 的改 进方法一排序过滤轮廓查询方法s f s ( s o r t f i l t e rs k y l i n e ) 1 6 1 。它基于一个重要定理：按照任何单调函 数对数据点所作的全序排序，都是按s k y l i n e 偏序支配关系所做的拓扑排序。算法先根据一个优先选 择函数首先对整个数据集进行排序，候选点按照分值以升序插入到列表中，因为具有低分值的点可 能支配大量的点，这样使得修剪更有效。2 0 0 5 年的v l d b 会议上，g o d f r e y 等人提出的l e s s ( 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 ) 算法i 7j 在预处理的过程中提前去除一些不可能属于s k y l i n e 的点，进一步 提高了s f s 算法的性能。 2 0 0 4 年i 拘e d b t ( e x t e n d i n gd a t a b a s et e c l m o l 0 9 3 0 z ，b a l k e 等人为分布式网络数据库设计了第一 个分布式s k y l i n e 算法引，它按每个记录在各维的属性值降序分别建立有序队列，再用轮训的方式一 次访问各个划分上的数据，通过按序存取和随机存取两阶段的检测，直到某一个点通过此按序访问 在所有划分上都被访问过为止。这个算法正确，公平，具有较好渐进性，但是，由于算法在数据划 分间频繁传递很小数据包，通信开销较大。 2 0 0 5 年v ld b 会议上，y i d o n gy u a n 等人提出s k y l i n ec u b e 查询方法1 9 1 ，它将单个s k y l i n e f u - 题延伸 为多个s k y l i n e 查询的复杂问题，首次提出了s k y l i n ec u b e 的概念，并提出t s k y l i n ec u b e 的求解方法， 但是没有提出数据集更新时s k y l i n ec u b e 更新的解决方法。 2 0 0 6 年，“h j ，t a n q z 等人研究t p 2 p 暖j 络环境下的s k y l i n e 查询处理问题i lo j ，提出了基于p 2 p 网络的s k y l i n e 算法。首先算法找到源簇，并记录最优值为界限值v b o 。d ，然后采取i n t e r - c l u s t e r 剪枝 和i n t r a c l u s t e r 剪枝方法来缩小范围，最后合并簇s p 得到结果集。算法利用了语义网的本质特征，在 不影响查询结果精确性的前提下，有效地限制了执行查询的网络范围。 2 0 0 7 年，面向不确定性数据的s k y l i n e 查询处理问题也得到了关注。不确定性数据的特点是各 个元组的值并不确定，以概率密度函数描述。p e i 等人根据可能世界模型定义了概率s k y l i n e 查询i l l j 。 不确定性数据库会衍生出很多可能世界实例，各元组在各可能世界实例中可能是s k y l i n e 点，也可 能不是s k y l i n e 点。由此，p - s k y l i n e 查询( o 印5 1 ) 被定义为返回所有成为s k y l i n e 点的概率超过p 的 数据点。文献i l l 】同时提出了两种解决方法：自下而上方法( b o t t o m u pm e t h o d ) 和自上而下方法 ( t o p d o w nm e t h o d ) ，分别采用不同的定界、剪枝、精化等启发式规则进行迭代处理。 2 0 0 7 年，l i a n 与c h e n 等人则考虑了如何在不确定数据集合上处理r e v e r s es k y l i n e 查询【1 2 i 的问 题i l 引。确定性r e v e r s es k y l i n e 查询返回在数据库中所有的动态s k y l i n e 包含给定查询点的数据点。 相应的，概率r e v e r s es k y l i n e 查询( p r o b a b i l i s t i cr e v e r s es k y l i n e ，p r s ) 被定义为：给定一个概率阈 值p ( 0 印曼1 ) 和一个查询对象g ，返回所有对象v ，使得对象g 为v 的动态s k y l i n e 点的概率不低 3 东南大学硕士学位论文 于闽值p 。文献【1 3 】将每一个数据对象看作是一个不确定区域，应用确定情形下的b b s 算法进行空 间剪枝，应用用户定义的概率阂值p 进行概率剪枝，得到候选的p r s 点进行精化，晟后输出查询结 果。 国内相应的研究起步较晚，目前关于s k y l i n e 计算的技术发展、分布式数据的算法的研究论文 正在逐渐增多。何红玲，冯维杰给出了对最近邻法的s k y l i n e 查询研究i l4 。，这种方法采用了基于r 树的索引结构，在内存中采用堆结构来存储需要检查的数据，通过分枝界定算法，不必对所有的数 据点进行检索，大大减少查询数据点的数量，减小查询代价。刘莉等将移动a g e n t 在构建分布式计 算环境的优势和已有的s k y l i n e 查询算法结合起来，提出了一种基于移动a g e n t 的分布式s k y l i n e 查 询算法【1 5 】，该算法可以在分布式环境下求解全局的s k y l i n e 点。孙圣力，黄震华等将数据流与子空 间s k y l i n e 的计算结合起来，提出了在滑动窗口中计算任意子空间上s k y l i n e 的问题l l 州，并给出了 一个高效的增量式的解决方案，进行了大量严格细致的实验。从公开发表的文献资料来看，复旦大 学已有5 篇相关论文在0 7 ，0 8 年的计算机学报、软件学报、计算机研究与发展等期刊上发表。国 防科技大学，昆明大学的学者也发表了数篇相关论文。但总的来说，这方面的研究还远远不够，尚 有很多不足和缺陷有待进一步改进和创新。 s k y l i n e 计算在数据库领域逐渐变为最大热点之一后，吸引了不同方面的学者对其进行研究，衍 生出很多新的研究课题，也扩展了其发展方向。为了更好地适应不同环境下的应用，最近几年，对 s k y l i n e 问题的研究逐渐地趋于在具体应用环境下进行d 9 i 。下面分别介绍几个在不同的应用环境下 s k y l i n e 问题的查询处理策略。这些新的应用环境包括分布式数据流、p 2 p 对等网络、无线传感器网 络。 1 2 1 分布式数据流上的s k y l i n e 计算 分布式s k y l i n e 查询要解决的问题是在一个大的分布式数据环境中通过有效算法以及最小通信 代价和i o 代价找出全局的s k y l i n e 点。当今的很多网络应用中都存在多数据中心的情况，例如总公 司与分公司的数据库，跨地区的多个服务器等。一个查询可能需要求出整个数据库上的s k y l i n e ，这 就需要高效的支持分布式数据库i 拘s k y l i n e 算法。分布式s k y l i n e 计算除了应满足集中式s k y l i n e 计算的 所有要求外，还应该尽可能减小网络通信开销。因为在分布式系统中，c p u 时间和i 0 时间与通信 时间相比几乎是微不足道的，通信开销被作为算法衡量的普遍标准，它不仅决定了网络带宽占用量， 还很大程度上决定了查询的响应时间。此外，算法的渐进性在分布式系统上显得尤为重要，因为分 布式系统上的查询往往耗费比集中式数据库上更长的时间。 流数据具有数据量大且速度快、无限连续到达、随时间具有不可预测性等特点，从而给数据流 环境下的s k y l i n e 查询处理带来了严峻的挑战。它要求s k y l i n e 查询处理具有实时性和较强的可管理 性，便于快速捕获流数据的特，征i 驰j u ”j5 1 。数据流应用一般运行在存储容量有限( 相对于数据流的大 小) 的环境下，因此，为了减少s k y l i n e 查询结果集，改善其可管理性，文献【3 0 】考虑对数据流中最近 的n 个元素计算其s k y l i n e 结果集1 1 o f - ns k y l i n e 查询，即在一个数据流的最近n 个元素中，查 询任意最近n 个元素( n n ) 的s p 集合，以支持快速的数据流上的s k y l i n e 在线查询。文献【3 0 】处理的 流数据是基于滑动窗口模式的，存在插入、删除和新到来数据等情况的待测数据集。针对这种数据 流上的s k y l i n e 查询处理，提出t s t a b b i n gt h es k y 算法。该算法主要考虑数据插入和删除时如何对 全空间上的s k y l i n e 进行维护。算法的缺陷在于，没有考虑如何计算子空间上l 拘s k y l i n e ，而且算法的 维护代价较高。另外，文献【3 0 】还对这个算法做了扩展，给出了计算( n 1 ，n 2 ) o f - ns k y l i n e 查询问题的 算法。( n l ，n 2 ) 一o f - ns k y l i n e 查询问题即在一个数据流的最近n 个元素中，查询任意最近n 1 个元素到最 近n 2 个元素( n l n 2 n ) 中的s p 。 为了降低分布式数据流上的连续s k y l i n e 计算过程中的通信开销，文献【3 l 】提出了远程过滤的 4 第二章s k y l i n e 计算技术与模型 思想，描述了v - m a x 和d i s t a n c e 两个过滤模型。分布式数据流环境下的连续s k y l i n e 计算概图如图2 - 3 所示。物理上分布的k 个监控节点n o d e ( i xi l ，k ) ) 将各自监控获得的数据子集n i 源源不断 地传递到一个集中式节点c 中；用户对集中式节点c 进行查询，获得全局i 拘s k y l i n e 集合 ，七、 s k iu fl o 图2 - 3 分布式s k y l i n e 查询框图 vm a x 算法的主要思想是首先定义一个虚拟数据点o ，其属性值为当前所有s k y l i n e 点在对应 维上的属性值的最大值。当某节点检测到有不被o 支配的点时，集中节点c 判断节点是否是新的 s k y l i n e 点，并更新o 点，广播给所有节点，远程节点用新的虚拟数据点继续执行后续过滤丢弃工 作。而d i s t a n c e 算法思想与此相同，采用距离过滤的思想，用单调的距离函数f 来表示数据点与原 点的距离，定义一个阈值距离t = m a x ( f ( p ) ) l p s k ( n ) 。两种方法在节点处都增加了存储开销以保 存虚拟数据，但有效地减少了通信开销。 移动a g e n t 是由分布式人工智能发展而来的一种新型计算模型，具有独立的智能性，在构造分布 式系统方面具有独特的优势。解决分布式数据s k y l i n e 问题的方法还可以用移动计算的方式，即将多 个a g e n t 复制到局部数据集上工作，并_ r a g e n t 之间通过相互交流和协作，最终返回全局s k y l i n e 点。 文献 1 5 】提出了基于移动a g e n t 的分布式s k y l i n e 查询算法，在各计算节点和计算中心都采用b n l 算 法，同时每个计算节点使用了一次全局n n 点过滤。 1 2 2p 2 p 对等网络 随着数据规模的急剧增大和网络技术的发展，对等网络( p e e r t op e e r ) 作为一种分布式信息共享 与搜索的平台吸引了越来越多人的注意。设计适用于对等网络上s k y l i n e 计算算法也成为一个重要的 研究方向。考虑对等网络高度动态、高度分散、扩展性强等特点，p 2 p1 - i 拘s k y l i n e 计算算法不仅需 要满足集中式s k y l i n e 计算算法的各种要求，还需要考虑减小网络通讯量、减少平均节点访问数、保 持负载平衡等重要衡量标准【3 7 1 。 文献 3 5 】提出了对等网络上的第一个s k y l i n e _ i , - t - 算算法。网络中的每个节点对应数据空间中的一 个矩形区域，并存储所有位于这个矩形区域中的数据点。数据区域与区域之间有着一定的支配依赖 性，算法通过动态地为区域编号标识出区域间的依赖关系，并按此依赖关系访问各个相关节点，并 行地传递和执行s k y l i n e 查询，逐步得出全部的s k y l i n e 。文章还提出一种动态的区域复制方法，用 以平衡节点间的负载。 5 东南大学硕士学位论文 文献【3 6 】在结构化对等网络上提出了包括s k y l i n e 查询在内的多维数据查询整体化解决方案。其 解决方案基于一个现有的一维平衡树结构的对等网络，在这个基础网络层上建立了适合多维数据查 询的分布式索引结构。在查询过程中，根据数据存取模式动态地切分搜索空间，缓解了区间查询和 s k y l i n e 查询处理中潜在的查询传播热点问题。通过估算、定位查询子区间里的目标节点，能有效地 控制查询转发数量，减少重复的节点访问，同时避免冗余消息在网络中传播。除此之外，在节点加 入、退出时通过平均分割查询负载的方法来划分数据空间，并在系统平稳运行态时定期进行动态负 载调整，达到了查询负载均衡。 文献【3 8 】提出了基于树型对等网络b a t i 州( b a l a n c e d t r e e o v e r l a y n e t w o r k ) 的s k y l i n e 计算算法。 它将整个数据空间适应性地划分为对应于网络节点的各个区域，s k y l i n e 查询被按照区域依赖关系发 送到可能包含s k y l i n e 点的节点上，以减少访问的节点数和传递的信息量。而文献【4 0 】对支配的概念 作了扩展，提出了扩充的s k y l i n e 集来定义所有可能在任一个子空f 日q s k y l i n e 查询中有用的点所组成 的集合，并设计出一个基于阈值和超级节点i 拘s k y l i n e 计算新算法，着力减小节点与节点间的数据传 输量。 1 2 3 无线传感器网络 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 是由大量的具有感知、计算和通信能力的微 型传感器节点以a dh o c 方式构成的无线网络。这些传感器节点协同工作，实时地监测、感知和采集 网络部署区域内的各种有用的信息，如温度、湿度、压力和声音等。它为人们随时随地地获取现场 信息提供了方便，因而被广泛地应用到了国防和国民经济各个领域，如地震监测、生活环境监测、 农业监测、矿井环境监测等h “。 对于传感器网络来说，负载较高且剩余能量较低的节点是传感器网络中的关键点，它们的寿命 直接决定着传感器网络的寿命，因此在应用中网络的管理者应该时刻关注这些节点，以便根据情况 进行相应地调整来延长网络寿命。这些节点就构成了传感器网络中的s k y l i n e ，如图2 4 所示。 o r i g i ne n e r g y 图2 4 传感器网络s k y li n e 示例 近年来，传感器网络中感知数据的杏询处理技术得到了广泛研究，而作为多目标决策重要依据 的s k y i i n e 查询也逐渐得到重视。在传感器网络中，数据是由传感器节点上的传感部件周期性采集 而来的，每个采样周期每个节点采集一个元组。每个采集的元组t 都有一个属性t a r r 来表明数据 的采集时间。出于节能的考虑，所有的感知数据在一定时间内都分散地存储在各个传感器节点上。 所以，要在所有的数据都采集后再计算传感器网络中的s k y l i n e 是不实际的。文献 2 9 主要研究m a n e t ( m o b i l ea d - h o cn e t w o r k s ) q b s k y l i n e 的计算方法，并利用一种混合的存储模型来提高移动设备上 s k y l i n e 的计算速度。利用过滤手段来减少m a n e t 中的通信代价。文献 3 9 研究了无线传感器网络上 的s k y l i n e 算法，通过时间戳考虑最新采集数据的s k y l i n e ，提出了一种基于过滤的滑动窗e i s k y l i n e 查 询算法( f i l t e rb a s e da l g o r i t h m ，f b a ) ，研究了利用元组过滤器和格过滤器来减少网络中数据传输 6 第二章s k y l i n e 计算技术与模型 量的两种方法，并给出了一系列的优化策略来提高过滤效率和减少数据的传输量，进而提高算法的 效率。f b a 算法极大地减少了传感器网络中的数据传输量，有效地节约了能量，进而有效地延长了 传感器网络的使用寿命。 总而言之，s k y l i n e 计算领域的研究态势呈现出从集中到分布，从静态到动态，从精确到近似， 从全空间到子空间的发展趋势，而且与实际应用结合越加紧密。随着s k y l i n e 研究的成熟与深化， s k y l i n e s t 算必将对信息科学的发展带来巨大利益。 1 3 研究内容及意义 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 计算本身发展时间并不长，只有短短2 0 多年的时间。经过众多学者的研究，学术 界的理论，模型，算法逐渐涌现，尽管针对集中式和分布式数据库提出了不少s k y l i n e 算法，但 相关领域的知识体系还没成形，有关s k y l i n e 计算的理论层面研究远远不够。 2 ，经过最近1 0 年的发展，出现了一些成果和进步，但s k y l i n e 计算的空白领域仍然很多，已有的 参考资料少。例如怎样改进现有算法以便更加高效的得出s l ( 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 ，数据维度和数据量的增多和变化给s k y l i n e 计算提出了新的挑战，各种新的应用领域具有 不同的特点和要求，目前尚不存在一种良好的普适算法。数据流环境，无线传感器网络，高维数 据集等不同领域要求有不同的算法，必须建立在对现在的s k y l i n e 查询的算法一定的了解之上， 探讨研究出适合特定情况下的高效算法。 本文的研究成果在于从一个新的角度分析现有高维数据空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 结果集数 目过多的问题，本文首次集中研究t s k y l i n e 结果集的优选策略，进一步改进了本文算法，克服维度 灾难的问题，缩小结果集，提高准确度。