（计算机应用技术专业论文）基于数据流的skyline计算及应用研究.pdf

学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀蹲硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密口。 学位论文作者签名：王靼土 枷l | 年6r | ；r 指导教师签 如| | 年茸胂 - r r l 一 ：月名伊 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 集体已经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：王犯未 妒年多月f 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 查询算法，在保证近似精度的 同时降低网络的通信代价。本文的主要工作如下： ( 1 ) 对与本文问题相关的基于数据流的s k y l i n e 计算进行剖析，指出数据流上 的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 查询时形成一条查询路径，查询结束后就可以按此路径反向收 集数据，从而减少网络开销。同时，这种簇结构可以达到负载平衡，从而有效地 进行查询处理。 江苏大学硕士学位论文 ( 4 ) 针对无线传感器网络，提出一种基于簇结构的近似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 t r e a md a t am i n i n ga n dm a n a g e m e n th a sb e e nc o n c e r n e dc o m m o n l yb yb o t h a c a d e m i aa n di n d u s t r yi nr e c e n ty e a r s i ti sah o tr e s e a r c ht o p i ci nt h ef i e l do fd a t a m i n i n g t oa c h i e v e s k y l i n eq u e r ye f f e c t i v e l y o nd a t as t r e a mb e c a u s es k y l i n e c o m p u t a t i o ni sw i d e l yu s e di nm a n yf i e l d ss u c ha sm 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 s y s t e m ，u r b a nn a v i g a t i o ns y s t e m s ，d a t am i n i n ga n dv i s u a l i z a t i o n ，i n t e l l i g e n td e f e n s e s y s t e m s ，a n dg e o g r a p h i ci n f o r m a t i o ns y s t e m s d a t as t r e a mi sc o n t i n u o u s ，r e a l t i m ea n do r d e r e ds e q u e n c ed a t ai t e m s t h e c h a r a c t e r i s t i co fd a t as t r e a mi st h a td a t aa r r i v ei nr e a l t i m e ，l a r g e s c a l e ，s e q u e n c e i n d e p e n d e n ta n dd a t a a r er e a d e d o n l yo n e ，w h i c hr e q u i r e s t h a t s k y l i n eq u e r y p r o c e s s i n ga l g o r i t h mm u s td e a l w i t ht h ee a c ha r r i v a lo b je c to ft h ed a t as t r e a m e f f i c i e n t l ya n dh a v el o w e rt i m ec o m p l e x i t y h o w e v e r ，t h ee x i s t i n ga l g o r i t h m sh a v e f o l l o w i n gp r o b l e m s ：t h ei r r a t i o n a lu s eo fd a t aw h e nal a r g en u m b e ro fc a l c u l a t i o n s r e s u l t st h ew a s t eo ft i m ea n ds p a c e ；t h ed i s a d v a n t a g eo fi n a d e q u a t er e m o v a lo fd a t a l e a d st h er e p e a t i n gc o m p u t i n gw h i l eq u e r y i n g ；t h eg e n e r a t e ds k y l i n es e t sd u r i n gt h e e x e c u t i o no fa l g o r i t h m sa r en o tf u l lu s e d ，w h i c hr e s u l t sl o w e rp e r f o r m a n c eo ft h e a l g o r i t h m t os o l v et h ea b o v ep r o b l e m ，w es t u d yaq u i c ks k y l i n ea l g o r i t h mb a s e do n n e a r e s tn e i g h b o rf i l t e r t h ea l g o r i t h ma ss o o na sp o s s i b l ee l i m i n a t e st h eo b j e c t st h a t n ol o n g e rh a v et h eo p p o r t u n i t yt oj o i ns k y l i n e ，w h i c hi m p r o v e st h eq u e r ye f f i c i e n c y a n dw ea p p l ys k y l i n ec o m p u t a t i o nt ow i r e l e s ss e n s o rn e t w o r ka n ds t u d ya n a p p r o x i m a t i o ns k y l i n ea l g o r i t h mb a s e do nc l u s t e ra r c h i t e c t u r e i tr e d u c e st h en e t w o r k c o m m u n i c a t i o nc o s ta sw e l la se n s u r i n ga p p r o x i m a t ea c c u r a c y t h em a i nc o n t r i b u t i o n o ft h ep a p e ri sa sf o l l o w s ： ( 1 ) a n a l y z et h es k y l i n ec o m p u t a t i o nb a s e do nd a t as t r e a ma s s o c i a t e dw i t ht h i s p r o b l e m ，p o i n to u tt h a tt h es k y l i n er e s u l t so nd a t as t r e a mi se v o l v i n g ，w h i c hc o n t a i n sa l o to fd i f f i c u l t i e sa n dc h a l l e n g e s a n da n a l y z et h ep r o b l e mt ob es o l v e d ，l e a d i n gt ot h e w o r ko ft h i sa r t i c l e ( 2 ) p r o p o s eaq u i c ks k y l i n ea l g o r i t h mb a s e do nn e a r e s tn e i g h b o rf i l t e rt oc o n q u e r t h ed i s a d v a n t a g eo fi n a d e q u a t er e m o v a lo fd a t a u s i n gt h ei d e ao fn e a r e s tn e i g h b o r f i l t e r , t h i sa l g o r i t h md e f i n e sat h r e s h o l di np r e p r o c e s s i n gm o d u l eu s i n ge u c l i d e a n d i s t a n c e t h et h r e s h o l di st h em a x i m u ma m o n go fa l lt h ed i s t a n c e sf r o mt h ec u r r e n t i ! i 江苏大学硕士学位论文 s k y l i n ep o i n tt ot h ec o o r d i n a t eo r i g i n a n da c c o r d i n g t ot h ed e f i n i t i o no fd o m i n a n c e ，i f t h ee u c l i d e a nd i s t a n c eo ft h en e w l yi n s e r t e do b j e c t sa r eg r e a t e rt h a nw h i c ho ft h e t h r e s h o l d ，t h e yw i l lb ep r o c e s s e da h e a do ft i m et or e d u c er e s o u r c ec o n s u m p t i o na n d t h et i m ea n ds p a c ec o m p l e x i t y ( 3 ) d e s i g nac l u s t e ra r c h i t e c t u r et oo r g a n i z et h es e n s o rn o d e si nw i r e l e s ss e n s o r n e t w o r k t h i sc l u s t e rs t r u c t u r ec a nf o r maq u e r yp a t hd u r i n gt h es k y l i n eq u e r y , a n d c o l l e c td a t af o l l o w i n gt h er e v e r s ep a t ha f t e rq u e r yt or e d u c et h en e t w o r ko v e r h e a d a l s o ，t h i ss t r u c t u r ec a na c h i e v el o a db a l a n c ea n dr o b u s t n e s so ft h es e n s o rn e t w o r k w h i l ep r o c e s s i n gs k y l i n eq u e r i e s ( 4 ) f o rw i r e l e s ss e n s o rn e t w o r k ，p r o p o s ea na p p r o x i m a t es k y l i n ea l g o r i t h mb a s e d o nc l u s t e rs t r u c t u r e w ei d e n t i f yaf i l t e rt h r e s h o l da c c o r d i n gt ot h ea p p r o x i m a t el e v e l s p e c i f i e db yt h eu s e r e a c hn o d ei nt h ec l u s t e rc a l c u l a t e st h ep r o b a b i l i t yw h i c hi t so w n d a t ab e l o n g st ot h es k y l i n eq u e r yr e s u l ts e t an o d ei sa c c e s s e di fa n do n l yi ft h e p r o b a b i l i t yi sg r e a t e rt h a nt h et h r e s h o l d b e c a u s ee a c hs e n s o rn o d ec a l c u l a t e si t so w n p r o b a b i l i t yw i t h o u tt h ec o m p a r i s o nw i t ho t h e rd a t a ，c o m m u n i c a t i o nc o s ti sg r e a t l y r e d u c e d e x p e r i m e n t a lr e s u l t ss h o w t h a tt h ea l g o r i t h mc a ns a v em o r en e t w o r ke n e r g y ， r e d u c et h en e t w o r kc o m m u n i c a t i o nc o s ta n de x t e n dt h el i f eo ft h ew i r e l e s ss e n s o ra s w e l la se n s u r i n ga p p r o x i m a t ea c c u r a c y k e yw o r d s ：s k y l i n eq u e r ya l g o r i t h m ，d a t as t r e a m ，w i r e l e s ss e n s o rn e t w o r k s ， t h r e s h o l d ，c l u s t e rs t r u c t u r e i v 江苏大学硕士学位论文 目录 第一章绪论1 1 1 研究背景和意义一1 1 2 研究现状：一2 1 3 主要研究内容5 1 4 论文的组织结构6 1 5 本章小结7 第二章相关理论技术8 2 1 数据流特点及处理技术8 2 1 1 数据流特点一8 2 1 2 数据流模型一9 2 1 3 数据流处理技术1 1 2 2s k y l i n e 1 4 2 2 1s k y l i n e 的定义与性质1 4 2 2 2s k y l i n e 操作与s q l 。15 2 3 数据流上的s k y l i n e 查询及计算1 6 2 4 无线传感器网络中的近似s k y l i n e 2 0 2 5 本章小结2 l 第三章基于最近邻过滤的s k y l i n e 快速查询算法。2 3 3 1 滑动窗口模型一2 3 3 2 数据流上s k y l i n e 查询模型2 4 3 3 基于最近邻过滤的s k y l i n e 算法n n s c 2 5 3 3 1n n s c 算法思想2 5 3 3 2 阈值的确定2 8 3 3 3n n s c 算法描述2 8 3 3 4n n s c 算法性能分析3 0 3 4 实验结果及分析3 0 3 4 1 对三组数据集的实验3 l v 江苏大学硕士学位论文 3 4 2 验证算法的c p u 耗时3 2 3 4 3 验证算法的内存使用情况3 3 3 5 本章小结3 4 第四章s k y l i n e 计算在w s n 中的应用。3 5 4 1 问题描述3 6 4 2 簇结构3 7 4 2 1 簇环的构造3 7 4 2 2 数据的插入3 8 4 3e a s 算法3 9 4 3 1 计算数据不被支配的概率3 9 4 3 2 确定数据过滤的阈值4 0 4 3 3 存储节点的剪枝与收集4 2 4 3 4e a s 算法描述4 2 4 4 实验结果及分析一4 3 4 5 本章小结4 7 第五章总结与展望4 8 5 1 工作总结4 8 5 2 进一步工作一4 9 致谢5 ( 1 参考文献。5 1 攻读硕士学位期间发表的学术论文5 6 v i 江苏大学硕士学位论文 1 1 研究背景和意义 第一章绪论弟一早珀了匕 自上世纪7 0 年代以来，数据库技术发展迅速，在与人们息息相关的生产和 生活等领域中得到了广泛应用，并取得了巨大成功。但是，在2 0 世纪末，随着 硬件、网络与通信技术的飞速发展和计算机应用领域的不断扩大，众多领域( 如 金融、电信、网络、航天和医疗等) 都产生大量、连续、快速的数据，学术上 将具有上述特征的数据序列称为数据流( d a t as t r e a m ) t 。与传统数据库应用环境 不同，这种数据具有高速动态性、处理需要近实时性和结果要求近似性的特点。 传统的数据库管理系统在于处理持久保存、相对静态的数据，其设计目标是维 护数据的a c i d 特性、提供较高的系统吞吐量和友好的用户接口等。研究能够 适应新的数据流环境下的数据模型成为一项迫切的需求。在这种情况下，数据 流查询的研究逐步兴起，并迅速成为引起关注的热点问题。 s k y l i n e 计算作为一种重要的数据挖掘与数据分析手段，近年来得到了学术 界和工业界的广泛关注。一个多维数据库的s k y l i n e ，是该数据库上不被其它任 何数据点支配的点所组成的集合。数据点p 支配点g ，当且仅当p 在任一维上 的取值都不比q 差，且至少在一个维度上比q 更好。s k y l i n e 查询最早由b o r z s o n y 等1 2 j 提出，并给出一个常见的例子，假设你要去旅游胜地巴哈马首都拿骚度假 并且正在寻找既便宜又离海边近的酒店。不幸的是，这两方面考量是鱼和熊掌 不可兼得的关系。通常，越靠近海边的酒店价格越高。旅行社的数据库管理系 统也不能为你决定哪个是最好的，但是，它至少可以告诉你一些你感兴趣的酒 店。实际上，如果不是两方面都不好于其他酒店，这样的酒店是可以感兴趣的， 我们称这样的酒店组成的集合为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 查询算 法，在保证近似精度的同时减少网络的能量消耗。 1 2 研究现状 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 t 等相关的高水平国际会议上发 表了许多高质量的论文，展示出大量的研究成果，在t k d e ，t o d s 等期刊中 也发表了大量成果。 早在2 0 世纪7 0 年代，s k y l i n e 计算就以最大向量问题的形式出现，文献【3 】 等文章最早探索了s k y l i n e 计算的简单方法和复杂度。最近1 0 年，国内外对 s k y l i n e 计算及其相关问题进行了广泛深入的研究，主要包括3 个方面： ( 1 ) 集中式数据库上的s k y l i n e 计算。2 0 0 1 年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 e o nd a t ae n g i n e e r i n g ) 会议上，b o r z s o n y i 等提出分治轮廓查询方法 d & c ( d i v i d e a n d c o n q u e r ) 1 2 1 ，在v l d b 会议上，k i a n l e et a n 等提出位图轮廓 查询方法( b i t m a p ) 【4 1 和索引轮廓查询7 嗽( i n d e x ) 4 ，2 0 0 2 年在v l d b 会议上， d o n a l dk o s s m a n n 等提出最近邻轮廓查询方法n n i ”，2 0 0 3 年在i c d e 会议上， c h o m i c k i 等提出了b n l 的改进方法排序过滤轮廓查询方法s f s t 们，2 0 0 5 年在t o d s 上，d i m i t f i sp a p a d i a s 等提出分支界限轮廓查询方法b b s i r l 。 ( 2 ) 分布式数据库上的s k y l i n e 计算。2 0 0 4 年在e d b t 会议上，b a l k ew t 等首次设计了分布式数据库上的第一个s k y l i n e 查询算法【8 】，它基于f a g i n l 9 1 提出 的t a 算法，将每个数据划分上的数据排序，再用轮循的方式依次访问各个划 2 江苏大学硕士学位论文 分上的数据，直到某一个点通过此按序访问在所有划分上都被访问过为止。2 0 0 6 年在i c d e 会议上，h u a n gz 等提出了m a n e t 上的第一个s k y l i n e 查询算法i l o j ， 将所有移动设备组织成一个树状结构，并以发出查询的设备作为树的根节点。 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 5 年在e d b t 会议上，w up 等提出了对等网络上的第一 个s k y l i n e 算法【1 1 1 ，它是基于对等网络的一种重要拓扑结构一c a n 网络的。网 络中的每个节点对应数据空间中的一个矩形区域，并存储所有位于这个矩形区 域中的数据点。数据区域与区域之间有着一定的支配依赖性，算法通过动态地 为区域编号标识出区域间的依赖关系，并按此依赖关系访问各个相关节点，并 行地传递和执行s k y l i n e 查询，逐步得出全部的s k y l i n e 。文章还提出一种动态的 区域复制方法，用以平衡节点问的负载。2 0 0 7 年i c d e 会议上，w a n gs 等提出 了基于树型对等网络b a t o n 的s k y l i n e 算法【l2 1 ，它将整个数据空间适应性地划 分为对应于网络节点的各个区域，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 计算成为了一个热门话题。文献【1 3 】讨论了在任意 子空间上的s k y l i n e 查询，将多维数据映射为一维值并利用b 树加以索引，仅通 过一遍数据访问即有效地去除了大量非s k y l i n e 点，高效地求出子空间上的 s k y l i n e 。之后文献【1 4 】和文献【1 5 】则不约而同地对所有子空间上的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 l i n e 因 其太大而变得没有意义。文献【l6 】提出了s k y l i n e 频率的概念，并设计出近似算 法找到那些在不同子空间查询被执行时返回频率最高的k 个s k y l i n e 点，认为它 们更有价值。文献【1 7 提出了肛支配的s k y l i n e 这个新概念，一个点p 是肛支配 点q 的，当且仅当p 至少在k 维上不比g 差，且至少在这其中的j 维上比q 好。 驴支配的s k y l i n e 即是那些不被任何点卜支配的点所组成的集合，既减小了 s k y l i n e 集合的大小，又提供了有价值的数据点。 3 江苏大学硕士学位论文 s k y l i n e 计算的其它许多方面也得到研究。文献【1 8 ，1 9 ，2 0 对s k y l i n e 集的大 小和计算代价进行了研究，以利于s k y l i n e 计算算法的设计和s q l 查询优化器 的改善。文献 2 1 1 考虑数据库并非每维数据均呈全序关系，而在一些维度上取 值是偏序关系时的s k y l i n e 计算，提出了一种分层的算法。文献【2 2 】则提出了空 间s k y l i n e 计算算法，处理包含空问属性的数据库上的s k y l i n e 查询。除此以外， c o m p r e s s e ds k y c u b e l 2 3 】对子空间s k y l i n e 的编码、d a d ac u b e t 2 4 1 对支配关系的分析 等等，都吸引了大量研究者的注意。 近来，国内在s k y l i n e 查询处理技术方面的研究工作也取得了较为丰硕的成 果。x u 和w a n g l 2 5 j 论述了p 2 p 网络环境下的s k y l i n e 查询处理方法。h u a n g 和 w a n g 2 6 , 2 7 1 分别研究了s k y c u b e 增量维护问题和s k y l i n e 大小控制问题。刘欣等 2 8 - 2 9 提出了一种基于窗e l 查询的全s k y l i n e 查询算法。“等【3 0 】提出了一个用于 支配关系分析的数据立方体，即d a d a 。l i 等【3 l 】引入并解决了一个独特的查询 类型。此查询类型不仅考虑了最d , 最大属性，而且也考虑了空间属性和不同属 性之间的关系。周红福等【3 2 】探讨了高维子空间上的查询问题，并提出了一种在 线的子空间查询算法s k y 。黄震华和汪卫【3 3 j 首次研究了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 计算研究，在数据流上，该方面的研究不算丰 富。y f t a o 等1 3 4 l 首次考虑在数据流上维护s k y l i n e 对象，并以r 一树索引为基础， 给出两个基于区域查询技术的有效维护方法：i - e a g e r 和i - l a z y 算法。对于新到 达的对象p ，i - e a g e r 算法搜索p 受支配区域中的所有对象来标识p 成为s k y l i n e 的时间点，并删除p 支配区域中的所有对象：而i - l a z y 算法搜索p 受支配区域， 如果遇到有一个点支配p 就退出搜索，并将p 加入到非s k y l i n e 集合中。对于过 期的对象，i - e a g e r 算法删除，- ，同时将在该时刻成为s k y l i n e 的所有对象加入 到s k y l i n e 集合中；而i - l a z y 算法先判断，是否为s k y l i n e 对象，如果是则删除 它，否则推迟到下一个s k y l i n e 对象过期时再删除它。文献中实验表明i - l a z y 算法的性能相对优于i - e a g e r 算法。x l i n 等f 3 5 】考虑在数据流环境上有效维护最 4 江苏大学硕士学位论文 近个s k y l i n e 对象的问题，并进一步研究了刀一o f - n 的s k y l i n e 查询问题，即返 回最近刀个s k y l i n e 对象问题。提出了一种剪枝技术来减少需要保存的数据量， 同时提出了一种编码技术来减少使用的内存空间，以及一种触发机制来连续地 计算最新的个数据中的最新的刀个数据( 门 忉的s k y l i n e 结果。m o r s e 等【3 6 1 采 用l o o k o u t 算法来维护s k y l i n e 结果。z h a n g 等【3 7 1 研究了滑动窗口下的概率s k y l i n e 查洵。 鉴于s k y l i n e 计算在多规则决策上的广阔前景，近几年国内研究人员也开始 了对数据流上的s k y l i n e 计算展开了研究。孙圣力等【3 8 】讨论了数据流上的子空间 s k y l i n e 查洵问题，并提出了一种基于网格索引的子空问s k y l i n e 查询算法。r 1 李 等【3 9 】针对更新的数据流提出了一种b u s h 算法，该算法将更新过程看作是旧的 位置点失效且增加一个新的位置点，并分别独立处理。但是，由于它将一个更 新元组引起的数据更新看作是旧点失效和新点增加分别进行独立处理，因此会 引入一些无谓的运算，加大了s k y l i n e 查询的计算量。王爱掣4 0 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 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 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 查询研究的内容，这些问题对动态环境下 的多约束决策，用户偏好查询以及数据挖掘可视化具有重要意义。本文的主要 内容体现在如下几个方面： ( 1 ) 首先介绍数据流的特点及处理技术，然后给出s k y l i n e 的定义与性质， 5 江苏大学硕士学位论文 s k y l i n e 操作与s q l 的关系，最后引出数据流上的s k y l i n e 查询，为本文的研究 提供全面的技术背景。 ( 2 ) 针对已有算法对数据对象去除率不足的缺点，提出一个数据流上的 s k y l i n e 查询算法，该算法利用最近邻过滤的思想，在预处理模块利用欧氏距离 定义一个阈值，根据支配的定义，从新插入的数据对象中，将欧氏距离大于阂 值的对象提前处理，以有效减少资源的消耗。实验表明该算法在一定程度上降 低了时空复杂度，尤其对于正相关数据，效果明显。 ( 3 ) 针对无线传感器网络中能量稀缺的情况，提出一种基于簇结构的近似 s k y l i n e 算法。该算法采用簇结构组织传感器节点，簇中每个存储节点计算自己 的感知数据属于s k y l i n e 查询结果集的概率，以决定是否处理其数据，而无须与 其它节点的数据进行比较，从而可避免大量的网内通信开销，节省网络能源。 同时，这种簇结构可以达到负载平衡，从而有效地进行查询处理。实验结果表 明，本算法在处理近似s k y l i n e 查询时，可以在保证近似精度的同时节省更多的 网络能量，延长无线传感器的使用寿命。 1 4 论文的组织结构 根据以上描述，本文组织如下： 第一章绪论：主要介绍本文研究背景及意义，所研究问题的研究现状，并 对本文的主要研究内容进行简要介绍，最后给出文章的组织结构。 第二章相关理论技术：介绍数据流及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 数 据区，从而有效减少资源的消耗。实验表明该算法在一定程度上降低了时空复 杂度，尤其对于正相关数据。 6 江苏大学硕士学位论文 第四章s k y l i n e 计算在w s n 中的应用：首先构建一种簇结构，利用簇结构 来组织传感器节点。然后阐述数据不被支配的概率的计算及数据过滤阈值的确 定，进而提出无线传感器中的近似s k y l i n e 查询算法，以节省网络资源。实验结 果表明，本算法在处理近似s k y l i n e 查询时，可以在保汪近似精度的同时，节省 更多的网络能量，延长无线传感器的使用寿命。 第五章总结与展望：对以上各章工作进行总结，分析不足并拓展未来的研 究方向。 1 5 本章小结 本章简单介绍了基于数据流的s k y l i n e 查询的研究背景和意义，及其研究现 状，给出了本文的主要研究内容，最后给出了论文的内容组织和结构安排。 7 江苏大学硕士学位论文 第二章相关理论技术 2 - 1 数据流特点及处理技术 随着大量数据流应用需求的持续推动，数据产生方式和收集手段越来越丰 富，数据流已逐渐成为一种同趋主流且使用广泛的新型数据存在方式，数据流 相关研究已经成为目前国内外数据库及相关研究领域的热点之一。传统的数据 库管理系统旨在处理持久保存、相对静态的数据，而针对无限、快速、连续的 数据流应用而言，传统的数据库管理系统与数据分析处理技术已很难适应该类 应用的需求。本节将简要介绍数据流特点、模型及处理技术，为本文的研究作 铺垫。 2 1 1 数据流特点 数据流相对于传统数据库中存储的数据，概括起来主要有如下五个特点 i , 4 1 - 4 3 】： ( 1 ) 无限快速性。数据流通常是源源不断地快速