（计算机软件与理论专业论文）分布式概率skyline查询研究.pdf

d i s s e r t a t i o nf o rm a s t e r sd e g r e eo ft h e2 01 1s e s s i o n s c h o o lc o d e ：l0 2 6 9 s t u d e n ti d ：5 1 0 8 1 5 0 0 0 0 6 eastch i nan0r ma l u n i v e r s i t y r e s e a r c ho nd i s t r i b u t e d p r o ba b i l i s t i cs k y l i n e d e p 硪m e n t ： s o 胁a r ee n g i n e e r i n gi n s t i t u t e s p e c i a l i t y ： c o m p u t e rs o r w a r ea n dt h e o 巧 r e s e a r c ha r e a ：m a s s i v ed a 协m a n a g e m e n ta n dd a t as t r e a m a n a l y s i s s u p e i s o r ： a p r o fj i i lc h e q i n g 2 0 1 1 4 哪9 肌3舢9洲309 川川im y 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文 分布式概率s k y l i n e 查询研究 ， 是在华东师范大学攻读硕够博士( 请勾选) 学位期间，在导师的指导下进行的研究工作 v 及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名：业 日期：矽- 7 铲月叼日 华东师范大学学位论文著作权使用声明 分布式概率s k y l i i l e 查询研究 系本人在华东师范大学攻读 学位期间在导师指导下完成的硕彰博士( 请勾选) 学位论文，本论文的研究成果归华东 师范大学所有。本人同意华东9 币范大学根据相关规定保留和使用此学位论文，并向主管 部门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允 许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入 全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文， 于年 月日解密，解密后适用上述授权。 ( 、歹2 不保密，适用上述授权。 导师签名本人签名客司咒 秒，年厂月1 7 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批衷方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 鍪明江硕士学位论文答辩委员会成员名单 姓名职称单位备注 周水庚教授复旦大学主席 王晓玲教授华东师范大学 钱卫宁副教授华东师范大学 论文摘要 近年来，有关s k y l i n e 查询的研究工作主要集中在对查询处理过程中计算代 价的优化，而对其中涉及到的通信代价优化却很少涉及。考虑一个“客户机 服务器”( c s ) 构架的分布式系统，客户机通过自身的传感器等装置记录数据， 再将记录更新到服务器；服务器保存记录在磁盘上并对这些动态数据进行连续 s k y l i i l e 查询处理。由于频繁的数据传递会耗费大量的能源和带宽，客户机与服 务器之间过多的通信不但会造成大量的能源浪费，而且也在时间上严重制约了 连续s k y l i l l e 查询的效率。在假定服务器具有充足资源进行计算的前提条件下， 客户机与服务器之间的通信代价将成为影响能源消耗和算法执行效率的最主要 因素。 不仅如此，在大多数现实环境中，数据的不确定性普遍存在，这导致s k v l i l l e 查询处理变得更加的复杂和困难。本文研究了基于c s 构架的不确定性数据环 境下的连续分布式概率s k y l i n e 查询。首先，本文在不确定性数据环境下定义了 一种特殊的概率阂值s k y l i n e 查询。在此基础上，本文提出了f i l t e r 方法，该方 法通过对每一个记录构建合法过滤器并在计算s k y l i i l e 过程中不断对其进行维 护，使得客户机向服务器传输数据时能够避免不必要的更新操作( 在s k v l i i l e 不受到影响的情况下) ，以此达到优化通信代价的目的。本文在模拟数据上的实 验证明f i l t e r 方法相对传统方法能够有效降低分布式概率s k v l i n e 查询过程中的 通信代价，提高了分布式概率s l ( 、，l i n e 查询的效率。 关键词：不确定性数据，概率s k y l i n e ，通信代价 第i 页 a b s t r a c t r e c e n t l y m o s tw o r ka b o u ts k y l i n eq u e 叮f o c u so no p t i i i l i z i n gc o m p u t i n gc o s t ， w m l ef e wp 印e r sd i s c u s st h ep m b l e mo fo p t 访1 i z i n gt h ec o m m u i l i c a t i o nc o s ti n s k y l i n eq u e r y g i v e nad i s t r i b u t e ds y s t e mb a s e do nt 1 1 ea r c h i t e c t u r eo fc l i e n t s e r v e r ， c l i e n t sm a k er e c o r d so f ( 1 a t aw i t hd e v i c e sl i k es e n s o rd e v i c e s ，a n dm es e r v e r c o n t 讪o u s i ym a i l l t a i n ss k y l i n eo fd y n a m i cr e c o r d st m n s m i t t e db yc l i e n t s b e c a u s e 五k q u e n td a t a 昀i l s m i s s i o n sc o n s u m eam a s so fe n e 唱ya n db a n d w i d m ，t o om u c h c o m m u n i c a t i o nb e t 、) l ，e e nc l i e n t sa n dt h es e e rw o u l dw a s t ee n o 肌o u sr e s o u r c e s m o r e o v i tc o i l s t r a i l l st h ee f j f i c i e n c yo fc o m i i l u o 岫s k y l i n eq u e 够t h es e r v e ra l w a y s h a sa b u n d a n tr e s o u r c e sf o rm a s s i v ec o m p u t a t i o n ，s oc o m m u l l i c a t i o nc o s tb e c o m et h e m a i l lf - a c t o rt h a ti i l n u e n c e st l i ed i s t r i b u t e ds k y l i n ea l g o r i t l l m b e s i d e s ，d a t au n c e n a i l l 够w i d e l ys p r e a d si nm o s tr e a l - 、o d ds c 髓a r i o s w h i c h m a k e ss 蚴i n eq u e r ye v e nm o r ec o m p l e xa n dd i 伍c u l t i i lm i sp a p e w es t u d y c o n t i n u o u sd i s t r i b u t e dp r o b a b i l i s t i cs k y l i n eq u e 巧o v e ru n c e 渤i i ld a t a f i r s t l y w e d e f i n eak i i l do fs p e c i a lp r o b a b i l i s t i c 吐l i 。e s h o l ds k y l i l l eo v e ru n c e n a i l ld a t a s e c o n d l y w ep r o p o s eaf i l t e ra p p r o a c hw h e r e l es e v e rc o n s 仉l c t sf i l t e r sf o re a c hr e c o r da n d c l i e n t so n l y 吣m i tu p d a t e st h a te x c e e dm ec o r r e s p o n d i n g6 l t e r i i l 血i sw a y ， 岫n e c e s 刘可d a 惚饷n s m i s s i o ni sa v o i d e d t h 砷l y e x p e 血n e i l t so ns y n t l l e t i cd a t as e t a tt h e 锄ds h o wt h a to u ra p p m a c hc a ne 彘c t i v e l yi e d u c ec o m m l l l l i c a t i o nc o s ti nt h e p r o c e s so f 如劬u t e dp r o b a b i l i s t i cs 蚴m em a i l l t a i l l i n g k e yw o r d ：u n c 咖i i ld a t a ，p r o b a b i l i s t i cs k y l 硫，c o 蛐吼i c a t i o nc o s t 第i i 页 目录 论文摘 要i a b s t r a c t i i 第1 章绪论1 1 1 研究背景1 1 1 1 s i ( y | n e 查询的定义l 1 1 2 s k y i n e 查询的应用2 1 2 s k y l n e 查询现状3 1 3 s k y i n e 查询挑战4 1 4 研究内容s 1 5 本文组织结构8 第2 章s m i n e 查询算法分析9 2 1 集中式s j ( y i i n e 查询9 2 1 1 现有主要算法9 2 1 2 算法比较小结1 2 2 2 分布式s k y l _ n e 查询1 3 2 2 1 分布式数据库1 3 2 2 2 移动自组织网络1 4 2 2 3 p 2 p 网络1 5 2 3 衍生s l ( y | n e 查询1 6 2 4 本章小结1 7 第3 章基础知识与问题定义1 8 3 1 基础知识。1 8 3 2 问题定义。2 0 3 2 1 问题准备2 0 3 2 2 问题提出2 3 3 3 方法准备2 3 3 4 本章小结2 6 第4 章f i l t e r 方法2 7 4 1f i i t e r 方法架构2 7 4 2 计算工p 巧妙砌e 查询2 9 4 3 生成过滤器。3 0 4 3 1 设定边界3 0 4 3 2 构建过滤器3 4 第5 章算法实验验证3 6 5 1 实验准备3 6 s 1 1 实验设施3 6 5 1 2 数据生成3 6 5 1 3 实验参数3 6 s 2 实验评估3 7 s 2 1 数据集的维度不同3 7 5 2 2 三种分布3 8 5 2 3 不确定性程度相关4 0 5 2 4 数据集大小不同4 1 第6 章总结与展望4 3 附录4 4 参考文献4 5 致谢4 9 分布式慨率s k y l i n e 查询研究 第l 章绪沦 1 1 研究背景 第1 章绪论 近年来，随着存储技术的不断进步和w 曲数据的大爆发，海量数据管理成 为数据库技术必须面对的一个核心问题。其中一个重要的课题就是如何从海量 数据中挖掘出有用的信息，以便人们能够在各种环境下做出相应的决策。s k y l i n e 查询最早由s b o r z s o n ) ，i 【l 】于2 0 0 1 年作为一个算子引入数据库当中，是多目标 决策的一个重要工具，已经广泛引起了越来越多数据库研究工作者的重视。 1 1 1 s k y l i n e 查询的定义 一个多维数据库的s k y l i n e ，是指该数据库上不被其他任何数据对象支配 ( d o m i n a t e ) 的数据对象所组成的集合。数据对象口支配数据对象6 ，当且仅当 口在所有维度上的取值都不差于6 ，且至少在某一个维度上的取值优于6 。 s k y l i i l e 查询算法就是从数据库中迅速找出所有的s k y l i n e 数据对象集合的方法。 图i 1 二维空间的s k y l i 北 图l l 是二维空间中一个简单s k 弭i i l e 实例，约定各维度上数据值更小为更 优，则根据前一段中关于支配关系的定义可知：数据点p 支配数据点g ，点p 与 第l 页 分布代概率s k y l i n e 查询研究 第l 章绪论 点g 互相间不支配对方。另外，图上所有实心的点均不被其他数据点所支配， 组成了该数据集的s k y l i n e ，空心点则至少被一个其他数据点所支配，称作非 s k y l i i l e 点。 1 1 2s k y i i n e 查询的应用 s k v l i n e 查询最重要的应用场景就是多目标决策。一个经典的例子就是旅客 选择宾馆入住问题。假定旅客“甲”来到某海滨城市“乙”旅游，他希望能够 在大量的宾馆信息中找到一个既离海边近，同时又价格实惠的宾馆入住。在现 实中，更靠近海边的宾馆往往房价相对较高，而价格便宜的宾馆又往往离海滩 较远。“甲”最后究竟会选择入住更便宜的宾馆、还是更近的宾馆、又或者是两 者折衷进行考虑，这完全取决于“甲”的个人偏好。从旅行社的角度来看，他 们无法得知所有旅客的个人偏好，从而也就不能为他们分别做出最佳选择。不 过旅行社能够从这些宾馆信息中找出任何旅客都可能感兴趣的信息提供给旅 客，让其自行根据个人偏好进行相应选择。方法就是找出和其他宾馆相比，至 少在其中一个条件上更优的宾馆，也即是“乙”城市所有宾馆数据库的s k v l i n e 集合。基于宾馆数据库的s k y l i i l e ，“甲”就能够根据自己的喜好，轻松做出选 择。根据s k y l i i l e 定义可知，无论旅客对这两个目标条件的偏好是怎样的，最符 合要求的宾馆必然在s k 、，l i l l e 集合里。 如图l - 2 ， 彳，b ，c ，d ，e 只g ) 为“乙”城市的宾馆数据集。其中宾馆e 距 离海边1 0 k m ，房价为1 8 8 元，宾馆g 距离海边3 4 k m ，但房价更便宜，为8 8 元。根据s k y l i n e 的定义，图中不存在任何其他宾馆优于两者，且e 和g 相互 之间不存在支配关系，因此e 和g 都在s k y l i n e 上。仅考虑e 和g 的话，如果 旅客“甲”倾向于价格实惠，则会选择宾馆g 入住，若倾向于距离海边较近， 则会相应选择宾馆e 入住。 第2 页 分仍式概率s k y l i n e 查询研究 第l 章绪论 房价 3 0 0 2 0 0 1 0 0 o 1 02 03 04 05 0 图1 2 旅客选择宾馆的s k y l i n e 实例 事实上，由s k y l i n e 的定义不难看出，s k y l i l l e 上的数据对象实际上是数据 库中带偏向性的具有特殊价值的数据。以旅客选择宾馆入住问题为例，即为那 些离海边距离偏近且房价偏低的宾馆。如图1 1 中虚线所示，s k y l i n e 本身在从 形态上看就是该数据库所有数据对象的边界，这很类似于城市以天空为背景的 轮廓线，s 州i n e 的叫法也正源于此。 1 2 s k y n e 查询现状 s k y l i 鹏查询的出现最早可以追溯到2 0 世纪7 0 年代，当时它以最大向量问 题( m x i n l a lv e c t o r ) 的形式出现。h k l l n g 【4 4 】在数据集低于3 维和高于3 维 情况下分别给出了复杂度为o ( 刀l o g ：刀) 和伙刀( 1 0 9 ：疗) 柏) 的基础算法。2 0 0 1 年， s b o f z s o n y i 【l 】将最大向量问题引入数据库( 以s k y l i n e 算子的形式出现) 。从 此之后，s k v l i n e 查询逐渐受到数据库研究工作者越来越多的重视，尤其是在最 近十来年，国内外关于s k y l i n c 查询在传统的数据库和数据流领域应用的文献与 日俱增，最近几年更是基本保持每年在三大数据库会议( s i g m o d ，i c d e ， v l d b ) 上占有一席之地。经过最近十年多的蓬勃发展，各种s k y l i n e 查询算法 第3 页 分布式概率s k y i j n e 查 ；f | j 研究 第l 章绪论 可谓层出不穷，应用场景也日渐宽泛。根据查询环境的不同，可以将s k y l i n e 查询算法大体分为以下三类： 1 ) 集中式s k y l i n e 查询。主要算法包括：块嵌套环算法( b l o c kn e s t e dl o o p ， b n l ) 1 】、分治算法( d i v i d ea n dc o n q u e r ，d & c ) 【1 】、排序过滤算法( s o r t f i l t e rs k y l i n e ，s f s ) 【2 】、位图算法( b i t m a p ) 【3 】、索引算法( i n d e x ) 【3 】、 最近邻算法( n e a r e s tn e i g h b o r ) 【4 】、分枝界限算法( b r a n c ha i l db o u n d s k y l i n e ，b b s ) 5 】等。 2 ) 分布式s k y l i i l e 查询。包括有：基于分布式数据的s k y l i n e 查询【6 】 1 5 】、 移动自组织网络( m o b i l ea d h o cn e 似o r k ，m a n e t ) 上的s k y l i n e 查询【7 】、 p 2 p 网络( p 2 p ) 上的s k y l i n e 查询 8 】 9 】等。 3 ) 衍生s k y l i n e 查询。主要有：s k y l i n e 对象集的势和相应代价估算 1 0 】、 在任意子空间上的s k y l i n e 查询【l l 】、在所有子空间上的s k y l i n e 查询 ( s k y c u b e ) 【1 2 】 1 3 】、在数据流上的s k y l i n e 查询【1 4 】等。 1 3 s k y l i n e 查询挑战 集中式s k y l i n e 查询是早期s 蚴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 2 p 网络三个方面，在 分布式环境多样化的今天，并不能够满足很多实际应用场景的需求。和传统集 中式环境不同，分布式环境对s k v l i n e 查询算法提出了更高的要求。在大容量硬 件的发展和w 曲数据大爆发的现状下，分布式环境所涉及的数据往往是海量数 据，这对s k y l i m 查询算法的效率要求很高。因为数据量一旦超过某个范围， s 蝴i n e 查询的响应时间将会变得很长，这将严重不利于对数据库中有价值数据 的提取和输出，从而大幅降低查询效率和质量。目前的一个解决办法是提高 第4 丽 分布式慨率s k ) ，l i n e 查询研究 第l 章绪论 s k y l i n e 查询算法的逐步输出能力，即在算法执行过程中能够成批量的生成 s k v l i n e 对象并及时返回给用户，而不需要等全部结果都计算出来再输出。这样 做的好处在于用户不需要等到所有结果都出来就能获得一定量的有用信息，从 而有效降低了查询等待时间，同时也提高了s k v l i n e 查询的渐进性。 不仅如此，通信代价也是分布式环境下s k y l i n e 查询不得不面对的一个问 题。一方面，在国际上节能减排的大趋势下，我们要降低网络中数据有线或无 线传递所造成的带宽消耗；另一方面，从用户的角度，我们要减少算法因为通 信而增加的查询等待时间。这就要求分布式s k m i i l e 查询算法能够优化数据传递 过程中的通信代价，从而达到节约能源和提高效率的目的。 更进一步的，随着人们对不确定性数据的认识不断加深，多数实际应用场 景中数据的不确定性也对s k v l i n e 查询提出了严峻挑战。由于原始数据本身可能 不准确( 如区间数据) 或者数据在传输过程中发生丢失，大多数实际应用场景 中的s k y l i n e 查询的数据集往往具有一定的不确定性。如何改进传统确定性数据 环境下的s l 刚i n e 查询算法，使之能够在新的不确定性数据环境下使用，已经成 为目前亟须解决的重要课题。 1 4 研究内容 图1 3c l i 蛐t s e r v e r 系统构架图 第5 页 雄 譬遵 分布式概率s k y i i n e 查询研究 第1 章绪论 近年来，关于s k y l i l l e 查询的研究绝大多数考虑的都是s k y l i n e 查询过程中 的计算代价。然而在很多分布式环境中，通信代价才是制约s k y l i n e 查询效率的 主要因素。 如图1 3 中所示是一个以“客户机服务器”( c l i e n t s s e r v e r ，c s ) 为构架 的分布式系统，该系统中包含一个服务器以及若干数量的客户机。每个客户机 上都装备有一个无线传感器，它们能够按照一定的时间间隔记录客户机所处位 置的实时数据，并通过发送上行消息( u p l i n km e s s a g e ) 至服务器以更新服务器 端保存的历史检测记录。与此同时，服务器也可以发送下行消息( d o w l l l i n k m e s s a g e ) 到相应的客户机以随时主动获取记录更新。服务器保存每个时间戳 ( t i m e s t 锄p ) 下的记录数据，并在该数据集上进行s k y l i i l e 查询处理，以此发 现潜在的问题或有趣的信息。 比如某个监测河流各段水质情况的系统，它由一个无线传感器网络 ( w i r e l e s ss e n s o rn e 似o r kw s n ) 组成，该系统在河床的各位置上部署无线传 感器。传感器测量并记录水温，含氧量，水流速度，p h 值等数据，然后发送到 主服务器保存更新。通过在整个数据集进行连续s 娜i i l e 查询，该系统能够及时 发现哪里的水质出现了极端情况，以便相关部门紧急反应并进行相应处理。 在现实情况中，服务器往往拥有充足的资源( 存储空间和计算能力) 来进 行s k y l i n e 查询处理，这使得服务器端s k y l 硫查询的计算代价在分布式环境中 对全局的影响较小。然而，客户机上的无线传感器等装置都是电池供电，并且 每发送一个上行消息都会造成一定量的能源消耗。从节能的角度来看【1 6 】，对 于一个拥有庞大无线传感器网络的系统而言，如果所有客户机在每一个时刻都 发送上行消息至服务器更新数据，不仅极大的增加了查询处理的等待时间，同 时为分布式系统本身带来严重的能源负担。在这种情况下，客户机与服务器之 间的通信代价成为制约s k 姐i n e 查询处理效率的关键因素【1 7 】。更进一步的，考 虑到环境的影响和设备本身的精度( 受网络带宽和电池电量影响) ，传感器装置 获得的数据在大多应用场景下是不准确的【1 8 】。举个例子，某些传感器装置在 测量水温时并不能获得其精确值，只能给出一个区间值，如l l 1 3 。在此条 第6 页 分伽式慨率s k y l i n e 查询研究笫l 章绪沦 件下，传统确定性环境下s k y l i n e 查询处理算法 1 9 】【2 0 】无法直接应用，同时这 也使得优化分布式系统( 基于“客户机朋艮务器”构架) 上s k v l i n e 查询处理的 通信代价更加困难。 本文将针对以上问题进行研究，探讨不确定性数据环境下的分布式概率 s k v l i i l e 查询问题的初步解决方案。 在本文中，我们首先会定义一种基于不确定性数据环境下的特殊概率阈值 s k y l i n e 2 1 】。进一步的，本文提出了一种分布式系统下的f i l t e r 2 2 】 2 3 】方法( f i l t e r m e t l l o d ) ，以优化客户机与服务器之间的通信代价为目的。f i l t e r 方法通过为每 一个客户机建立合法过滤器，减少系统中上行消息数量，从而使得降低客户机 和服务器之间的通信代价成为可能。基本原理如下：假定当前时刻某客户机上 记录r 的数据发生了变化，并且新的状态没有超出相应的过滤器范围，此时该 客户机不发送上行消息至服务器更新，这是由于该记录在其合法过滤器范围内 的变化不会对原s k y l i n e 产生影响。相反的，如果新的数据记录超出了合法过滤 器范围，则该记录必须提交至服务器进行更新。与此同时，服务器有必要为发 生过滤器溢出事件的客户机设定新的合法过滤器，以保证过滤器始终有效。 本文第一部分对现有s l ( ) r l i l l e 查询算法进行了综述，根据数据库的分布环境 不同分别对集中式s k y l i l l e 查询算法、分布式s k y l m e 查询算法、衍生s k y l i n e 查询算法作了简单的介绍，并结合各个算法的特征对其优缺点进行了比较分析。 通过这一部分的分析和归纳，为本文后续研究分布式概率s k v l i n e 查询算法起到 很好的参考和借鉴作用。 第二部分工作则具体为不确定性数据环境下的概率s 枷i 舱查询建立模型， 在具体的“客户机服务器”构架下提出新的支配概念和相应的概率阈值s k v l i n e 查询，为进一步研究相应的分布式概率s k y l i n e 查询算法做好铺垫。 第三部分是本文的主体算法部分。针对阈值等于l 的概率s k y l i n e 查询，提 出了新的f i l t e r 方法，以优化降低分布式概率s k v l i i l e 查询的通信代价为目的。 进一步的，本文通过基于合成数据库的实验验证了该算法的有效性，并与传统 n a ：| v e 算法针对不同指标进行了对比。 第7 页 分布式概率s k y l i n e 查询研究 第l 章绪论 1 5 本文组织结构 本文共分为六个章节，按如下组织结构逐步展开： 第一章为绪论，主要介绍s k v l i i l e 查询的定义和相关实例应用场景，同时描 述s k y l i n e 计算的现状和面临的挑战，并包含本文主要内容提要。 第二章介绍s k y l i l 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 i l e ，同时针对不确定性环境作了详细而明确的定义，为后文提 出具体解决算法做好准备工作。 第四章基于阈值等于l 的概率s k v l i n e 定义，提出了“客户机月艮务器”构 架下的分布式系统上的f i n e r 方法，通过为客户机建立并维护合法过滤器，以 达到降低分布式概率s k y l 硫查询处理过程中的通信代价为目的。 第五章在合成数据集上设计了四个实验。通过将f i l t e r 方法与传统n a ：j v e 方法在各个实验指标下进行比较，验证了本文所提出算法的有效性，同时分析 归纳了f i l t e r 方法优缺点，进一步明确了该方法适用的场景。 第六章对全文做出总结，归纳了现阶段分布式s k y l i n e 查询仍待解决的问 题，并由此展望分布式s k y l i n e 查询未来的研究方向。 第8 页 分布式概率s k y l i n e 查询研究第2 章s k y l i n e 查询算法分析 第2 章s k y l i n e 查询算法分析 近些年，s k v 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 集中式s k y l i n e 查询 在集中式环境中，s k y l i n e 查询的性能指标主要包括有以下几点： 1 ) 正确性：结果返回正确的s k y l i i l e 集； 2 1 公平性：算法不偏向取值好的数据； 3 1 渐进性：将结果逐步返回给用户； 4 1 可扩展性：可广泛应用于不同维度、分布和大小的数据集； 5 1 高效性：算法时间复杂度低。 2 1 1 现有主要算法 现有s l 刚i l l e 查询算法按照使用索引情况可以分为两类：一类在查询过程中 不使用索引，包括有b n l 算法，d c 算法，s f s 算法， b i n i l a p 算法等；另一 类则使用索引，包括有m e x 算法，最近邻算法，b b s 算法等。 2 1 1 1b n l 算法 b n l 算法【l 】：在外存中建立窗口保存暂时不被任何其他点所支配的数据 点。当算法读取到一个新点p 时，将点p 与临时表中的其他点一一进行比较， 此时将会发生以下三种可能情况： 1 ) 窗口中存在其他点支配点p ，根据s k y l i i l e 定义，点p 不可能出现在 s k v l i n e 上，丢弃； 2 ) 点p 支配窗口中的若干个点。则将这些被支配点剔除出窗口，并将点p 作为新点插入窗口中； 第9 页 分布代概率s k y l j n e 查询研究第2 章s k y l i n e 查询算法分析 3 ) 点p 与窗口中的所有数据点均不存在绝对的支配关系，此时若窗口中有 足够空间剩余，则插入点p ，否则将其写入到另一个临时文件中，并 将此临时文件作为下一个循环过程的输入。 为了缩减各点之间的相互比较次数，尽快去除那些不在s k y l i n e 上的点， b n l 算法使用一个临时表作为窗口。当某点被发现支配其它点时，优先将其移 至窗口的最前端。每一轮循环结束后，只输出那些临时文件产生之前就被插入 窗口的点，其它点则有必要经过进一步处理。 b n l 算法具有高可扩展性，对于各种不同数据分布和大小的数据集，b n l 算法不需对数据进行索引和预处理就能够直接发挥作用。b n l 算法满足正确性、 公平性，但仅在s k y l i i l e 集较小的情况下效率才较高，在s k y l i n e 数据集较大或 内存较小的情况下，则需要大量循环才能输出所有的查询结果，这将产生大量 的i o 操作，同时也增加了响应时间。此外，b n l 算法的输出条件较为恶劣， 这使得它在渐进性方面较差。 2 1 2 2d & c 算法 d & c 算法【l 】将数据集划分成两个或多个分块，然后分别在各个分块上进行 s k y l i i l e 查询( 递归调用直到所有子分块小到能够快速进行s k y l i l l e 查询为止) ， 再将各部分的s k y l i n e 归并到一起，同时去除其中的奇异点，由此输出整个数据 集的s k y l i n e 。 d & c 算法具有良好的正确性和公平性。当数据集小到能够完整写入内存中 时，d & c 算法的执行效率很高；当数据集较大时，由于数据不能完全放入内存， 而d c 算法又需要不断从硬盘中读取和写入数据，由此产生了大量的i o 操作。 因此，d & c 算法在数据量较大时的扩展性并不是很好。而且d & c 算法的最终 s k v l i i l e 查询结果必须在所有划分全部完成之后才能输出，这导致它在渐进性方 面表现很差。 2 1 2 3s f s 算法 s f s 算法【2 】在b n l 算法的基础上进行了预排序。它通过对临时表中的数据 对象按照单调函数进行排序，然后调用b n l 算法处理这些数据。由于做了预排 第l o 页 分m 一慨牢s k y l i n e 查询研宄 第2 章s k y l i n e 查询铬法分析 序工作，根据s k v l i n e 在单调函数上的保序性，先加入到窗口中的数据对象必然 不会被后加入的数据对象支配，也就必然在s k y l i n e 上，可以直接输出给用户， 这样就降低了b n l 算法的不必要开销。 s f s 算法相对于b n l 算法提高了查询的效率，增强了渐进性。继而提出的 l e s s ( 1 i n e a re l i i i l i m t i o ns o r tf o rs k y l i n e ) 算法【2 4 则在s f s 算法基础上做出了改 进，它通过在预处理过程中加入消除过滤窗口再做外部排序，提前剪除了某些 非s k v l i i l e 对象，由此进一步提高了s f s 算法的性能。 2 1 2 4b i t m a p 算法、i n d e x 算法 b i t m 印和础e x 两种算法均由k l t a n 【3 】提出。b i 衄a p 算法用映射的办 法将每一个点对应一个位串，然后通过位运算来计算s k y l i l l e 。虽然b i t r i l a p 算 法在某些情况下能够快速得出s k y i i n e ，但计算每个数据对象时都需要将该数据 对象与所有其他数据对象进行比较操作，故不具备高效性。此外，b i t i l l a p 算法 会导致位串长度随各维度上差异取值数目的增多而迅速膨胀，空间消耗非常大。 i i l d e x 算法同样使用了映射的方法，它将每一个点对应令它取到最小值的维 度所对应的链表，在b + 树的索引条件下，批量处理数据对象并输出s k y l i n e ， 渐进性较好。值得注意的是，砌e x 偏向于优先求出在某一维度上取值相对较好 的s k v l i n e 对象，因此不具有公平性。 2 1 2 5n n 算法 n n 算法【4 】依据用户自定义距离公式，以r 树作为数据索引。它每次寻找 离原点距离最近的数据对象，通过该数据对象将数据空间划分成若干个子空间。 根据s 蛳定义，该数据对象必然在s k y l i n e 上，因此可以立即输出给用户。 接着n n 算法继续在每一个子空间上递归调用直到子空间只含有一个数据对 象，最后输出全部s k y l i l l e 对象集合。 n n 算法具有很好的公平性，而且能够在低于五维的数据库上，比前面所 述s k y l 毗查询算法更快输出查询结果。然而，子空间上的连续划分操作会导致 大量重复搜索的产生，耗费了大量的时间和空间，故渐进性较差。 第l l 页 分布弋概；筝s k y l i n e 查订0 研究 第2 章s k y l i n e 查询馋法分析 2 1 2 6b b s 算法 b b s 算法【5 也使用r 树索引数据。r 树的每个上层节点对应下层的一个最 小边界矩形( m i n i m u mb o 吼d i n gr e c t a i l g l e ，m b r ) ，叶子节点则对应一个数据对 象。b b s 算法从r 树的根节点开始，计算其到原点的最小距离，并逐步把r 树 根节点上的所有子m b r 按照距离大小顺序插入到一个堆( h e a p ) 中。每次从堆 中取出距离最小的根节点进行扩展，得到其子m b r 后，继续按照距离大小顺 序插入堆中，直到堆中距离最小的根节点是叶子节点为止，此时扩展出该节点 里所包含的数据，得到位于s k v l i i l e 上的对象。 b b s 算法具有良好的公平性和正确性。而且当数据库的维度低于6 维时， b b s 算法在各个方面均具有高效性和高可扩展性；维度高于6 维时，由于受r 树高维空间上性能的限制，b b s 算法的性能也随之下降。由于能够将每次扩展 节点子m b r 所得的s k y l i n e 对象立即返回用户，b b s 算法的渐进性很好。在前 文提及的各个指标上，b b s 算法都远优于前面所有算法，被公认为当前最优 的集中式s i ( y l i n e 查询算法。在此基础上，l e e 2 5 通过使用z - o r d e r i n g 的r 树 索引，进一步提高了b b s 算法的效率。 2 1 2 算法比较小结 在正确性和公平性两方面，只有砌e x 算法是不公平的，它偏向于求某一 维度上取值较好的是s k y l i n e 对象。 在高效性方面，n n 算法花费的计算时间比i i l d e x 算法要少，故优于i n d e x 算法；s f s 通过预排序操作，大幅提高了b n l 算法的效率；b i t n l a p 算法由于计 算每一个数据对象时都要将该对象与其它所有数据对象进行比较，大幅降低了 效率；d & c 只在内存能够完全写入待求数据时才能保证一定的高效性；而b b s 算法的运行时间和i o 开销均远小于其它算法，故在所有算法中相对高效。 在可扩展性方面，b n l 算法，d & c 算法和s f s 算法由于对内存的依赖性， 在数据量过大时会导致数据的反复读写而严重降低效率；n n 算法由于要生成 大量子空间，扩展性能一般，但在低维情况下的表现要比砌e x 算法