（计算机软件与理论专业论文）海量点集数据的极大点查找算法及相关应用研究.pdf

硕上学位论文 摘要 在现实应用中存在大量的海量数据，由于其太大而不能完全装入计算机内 存。因此在快速的内存和相对慢速的外存( 比如硬盘) 之间的输入输出( i o ) 通讯就成了制约算法性能的主要瓶颈。特别在以下方面：空间数据库中的海量几 何数据、地理信息系统( g i s ) 、约束逻辑规划、数据库、统计学、虚拟现实系统、 计算机图形学。由此产生了外存储算法与数据结构的设计和分析领域，其主要目 标就是研究算法的局部性以尽量减小程序的输入输出代价。 极大点查找问题是是计算几何的一个重要的基本问题。由于极大点集在一个 点集的边界上存在很多有意义的特性，其与凸包、最近点对等问题均有密切的联 系。同时极大点查找问题也出现了越来越多的各种应用。 本文研究了已有的极大点查找算法。在此基础上提出一种针对海量点集数据 的极大点查找概率算法，并证明了算法的可靠性。通过实验取得了很好的实验效 果。并对其在数据库查询中的应用进行了研究。 本文的研究工作和创新包括以下两个方面： ( 1 ) 针对极大点查找问题，目前还没有线性输入输出次数的外存储算法。本 文根据极大点数目的概率特性，针对独立同分布数据集，设计出了一种针对海量 数据的线性输入输出次数的极大点查找算法。并通过理论和试验证明了算法的可 靠性。 ( 2 ) 随着信息技术的不断发展和应用的不断深入，数据收集手段越来越丰富， 海量存储在数据库中也越来越普遍。本文将设计的算法应用到数据库的s k y l i n e 查询处理中，取得了良好的试验效果。 关键词：外存储算法；输入输出；极大点；s k y l i n e 查询 海量点集数据的极大点查找算法及相关应用研究 a b s t r a c t d a t as e t si nl a r g ea p p l i c a t i o n sa r eo f t e nt o om a s s i v et of i tc o m p l e t e l yi n s i d et h e c o m p u t e r s i n t e r n a lm e m o r y t h er e s u l t i n gi n p u t o u t p u tc o m m u n i c a t i o n ( o ri o ) b e t w e e nf a s ti n t e m a lm e m o r ya n ds l o w e re x t e m a lm e m o 巧( s u c ha sd i s k s ) c a nb ea m 旬o rp e r f o r m a n c eb o t t l e n e c k e s p e c i a l l yi nt h o s ef i e l d sa st h ef 0 1 l o w i n g ：m a s s i v e g e o m e t r i cd a t ai ns p a t i a ld a t a b a s e ，g e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g i s ) ，l o g i c a i c o n s t r a i n t s ，r e l a t i o n a ld a t a b a s e ，s c i e n c eo fs t a t i s t i c s ，v i r t u a lr e a l i t ys y s t e m ，c o m p u t e r g r a p h i c s t h e r e f o r e ，t h ef i e l do fd e s i g na n da n a l y s i so fe x t e r n a lm e m o r y ( o re m ) a l g o r i t h m sa n dd a t as t r u c t u r e sh a sa p p e a r e d ，w h e r et h eg o a li st oe x p l o i tl o c a l i t yi n o r d e rt or e d u c et h ei oc o s t s m a x i m a - f i n d i n gp r o b l e m s a r et h ef u n d a m e n t a l p r o b l e m i n c o m p u t a t i o n a l g e o m e t r y i ti st h o u 曲tt h a lm a x i m ao f f e r sm a n ys i g n i n c a n tc h a r a c t e r i s t i c sa tt h e b o u n d a r yo fap o i n ts e t ，a n dh a sc l o s ec o n n e c t i o nw i t hm a n yp r o b l e m ss u c ha sc o n v e x h u l la n dn e a r e s tn e i g h b o r m o r e o v e rm a x i m a 一6 n d i n gp r o b l e m sh a v ea p p e a r e dag r e a t d e a lo fa p p l i c a t i o ni nm a n ya r e a sr e c e n t l y t h ee x i s t e da l g o r i t h m si nt h en e l d o fm a x i m a f i n d i n gp r o b l e mh a v e b e e n f e s e a r c h e di n t h i sp a p e r i n t h i sf b u n d a t i o n ，an e wm a x i m a f i n d i n gp r o b a b i l i s t i c a l g o r i t h md e a l i n gw i t hm a s s i v ed a t ah a sb e e np r e s e n t e d t h ec o r r e s p o n d i n gr e l i a b 订i t y h a sb e e nv a i i d a t e df r o me x p e r i m e n t sa n dt h e o r y t h ea p p l i c a t i o no ft h ea l g o r i t h mi n t h ef i e l do fd a t a b a s eq u e r yh a sa l s oi n v e s t i g a t e d p r i m a r yr e s e a r c h e sa n dc r e a t i o n si nt h i sp a p e ra r ea sf 0 l l o w ( 1 ) f o rt h em a x i m a f i n d i n gp r o b l e m ，t h e r eh a sn ol i n e a r i oe x t e m a lm e m o r y a l g o r i t h my e t s oal i n e a ri om a x i m a f i n d i n ga l g o r i t h md e a l i n gw i t hm a s s i v ed a t a h a sb e e np r e s e n t e di nt h i sp a p e r ，w h i c hi sb a s e do nt h ep r o b a b i l i t yn a t u r eo fm a x i m a n u m b e r ，a n di nc o n n e c t i o nw i t ht h ei n d e p e n d e n ti d e n t i c a l i yd i s t r i b u t e dd a t as e t t h e c o r r e s p o n d i n gr e l i a b i l i t yh a s b e e nv a l i d a t e df r o me x p e r i m e n t sa n dt h e o r yt o o ( 2 ) w i t ht h er a p i d l yd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n di t sd e e p l y a p p l i c a t i o n s ，m em e t h o do fd a t ac o l l e c t i o n si sb e c o m i n gm o r ea n dm o r ea b u n d a n tn o w ， a n di ti sm o r ea n dm o r ec o m m o nt h a tm a s s i v ed a t ai nd a t a b a s e s i nt h i sp a p e r ，t h e r ei s a na p p l i c a t i o no ft h em a x i m a - f i n d i n gp r o b a b i l i s t i ca l g o r i t h mi nt h ef i e l do fs k y l i n e q u e r yi nd a t a b a s e ，w i t han i c ee x p e r i m e n t a lp e r f 0 m a n c eo ft h i sa p p l i c a t i o n k e y w o r d s ： e x t e r n a lm e m o r ya i g o r i t h m ；i o ；m a x i m a ；s k y l i n eq u e r y i i 硕士学位论文 插图索引 图2 1 一个典型的单处理器系统存储器层级图5 图2 2 一个二维极大点示例。6 图3 1 由定理4 4 确定的点集中点的个数触每页点的个数疗以及办p 怕，- 厂，d 矽 的关系图15 图3 2 由定理3 4 确定的点集中点的个数从参数七以及所阳蹭厂厂口彬的关系图 像：1 ； 图3 3 肛4 时由定理4 4 确定的点集中点的个数和尸厂佃增厂厂d 的关系图像1 6 图3 4 二维实验数据图1 7 图3 5 定理4 8 中溢出概率和七，的函数图像1 9 图3 6 定理3 8 中溢出概率和丘，g 的函数图像一2 0 图3 7 各维上詹值的一个参考值2 l 图3 8 二维数据空间试验结果图2 2 图3 9 三维数据空间试验结果图2 2 图3 1 0 五维数据空间试验结果图。2 3 图3 1 1 八维数据空间试验结果图2 3 图4 1 有关n a s s a u 饭店的s k y li n e 查询问题2 4 图4 2 二维虚拟点的位置示例3 0 图4 3 加入虚拟点后的二维数据空间试验结果图3 l i i i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：贵匐钮 日期：口尸年乡月吕日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服 务。 日期：汐尸年么月吕日 日期：沙彳年厶月7 日 硕士学位论文 第1 章绪论 本章首先简要阐述了海量数据处理及外存储算法的概念，然后介绍了极大点 的定义及研究现状，最后给出了本文的主要研究内容和论文的组织结构。 1 1研究背景 由于海量数据在现实中的应用要求，外存储算法越来越受到研究人员的关注。 特别在以下方面：空间数据库中的海量几何数据、地理信息系统( g i s ) 、约束逻辑 规划、面向对象的数据库、统计学、虚拟现实系统、计算机图形学。例如n a s a 的地球观察系统项目每年产生1 0 1 5b y t e 的光栅数据，微软的t e r r a s e r v e r 卫星图 像在线数据库容量超过1 t b 。单纯借助目前操作系统的虚拟存储技术，许多问题 根本无法解决或者效率非常不理想。如何有效的处理这类海量数据成为目前面临 的一个重要的理论问题，缺少有效的方法这些数据将失去作用。这些数据的处理 需要有效的外存储算法和相应的数据结构，幸运的是有些问题可以转化为一些比 较小的核心的问题来加以解决。例如文献 1 】利用一个2 毒1 0 8 个节点和2 奉1 0 9 条边 的有向图来模拟试验网络段的网页链接，并将其转化为最短路径计算、连通分支 计算等基本问题来分析和研究网页的结构和特点；文献【2 】中同样将a t & t 公司的 2 0 t b 电话数据记录转化成基本的图论问题进行研究和处理。由于这些基本问题 数据量非常大，均无法依靠普通的内存储算法计算完成，研究这些基本问题的外 存储算法，是非常迫切和有意义的。关于海量数据处理算法的详细内容可以参见 j s t t e r 的综述文献 3 】。本课题就是对计算几何中的一个基本问题设计针对海量 数据的外存储算法并对其相关应用进行研究。 在一个点集中，如果点p 的每一维坐标( c o o r d i n a t e ) 都大于点q 的相应维 坐标，则称作点p 支配( d o m i n a t e ) 点q 。如果一个点不被集合中任何另外一个 点支配，这个点就称作极大点( m a x i m a lp o i n t ) 。不被支配的所有点组成的集合就 称作这个点集的极大点集( m a x i m a ) 【引。 由于极大点集在一个点集的边界( b o u n d a r y ) 上存在很多有意义的特性，其 与凸包、最近点对等问题均有密切的联系，所以极大点集问题是计算几何的一个 重要的基本问题。同时极大点集在不同的领域均有广泛的应用，例如b e n t l e y ， k u n g ，s c h k o l n i c k 和t h o m p s o n 在文献【5 】中描述了如何利用极大点集来决定动态 规划算法的运行时间。p r e p a r a t e 和s h a m o s 在文献【6 】中利用极大点集去解决经济 学中的“浮动通货问题 。p a r k e ，i b a n 和j a r e k 在文献【7 】中对极大点集在关系型 数据库中的应用有比较全面的论述。 海量点集数据的极大点芥找算法及相关应用研究 从1 9 6 6 年b a r n d o r f f - n i e l s e n 和s o b e l 在文献【8 】中对极大点集数目的研究开 始，对极大点问题研究已有很多的成果。存在相当多的算法来寻找集合中的极大 点。目前存在的寻找极大点集算法有连续( s e q u e n t i a l ) 算法【4 ，州，分治 ( d i v i d e a n d c o n q u e r ) 算法【9 ，1 0 ，1 1 1 ，桶( b u c k e t ) 算法【1 2 ，1 3 1 ，挑选( s e l e c t i o n ) 算 法【1 4 1 ，筛( s i e v e ) 算法1 4 】等。连续算法中k u n g 等人在文献 9 】中利用平衡搜索树 去维持已搜索到的极大点，而b e n t l y 等人在文献【4 】中利用链表，并且当一个新插 入点被支配时应用移动到开头( m o v e t o f r o n t ) 的启发式策略，从而提高算法的 效率，使得算法平均时间复杂度达到线性，具体证明参见g o l i n 的文献 1 5 】。在分 治算法中，主要考虑算法的分治规则，例如在文献【9 】中，k u n g 等人利用双向分 治策略，在维数和点数上进行双向分治，以提高算法在多维点集中的效率。对于 有序序列上的分治算法自上而下的描述产生了桶选择算法，具体参见【1 2 ，1 3 ，1 6 】。 值得注意的是桶算法不同于连续算法和分治算法，其对输入点集的分布存在更多 的敏感性。挑选算法的预期复杂度是线性的【l 7 1 。但对于2 维以上的点集需要类似 分治算法中的额外的归并过程。c l a r k s o n 在文献【1 4 】中讨论了另外种顺序选择 算法，通过比较每一个不可比( i n c o m p a r a b l e ) 元素来构造极大点集，其过程类似 于选择排序。c l a r k s o n 的算法可以针对任意维的点集，但当极大点比较多的时候 算法效率非常低。其中点p 和点g 不可比是指p 无法支配( d o m i n a t e ) g ，g 也无 法支配( d o m i n a t e ) p 。挑选算法对寻找第一个好的筛点有一些作用。但是当我们 知道更多的输入数据信息时( 除维数以外的，比如输入集的分布) ，可以在不花费 额外代价的情况下很快地确定一个具有强大筛能力的筛点，就是通常所说的筛算 法。 目前已有的算法在输入数据可装入内存时性能各有优劣，目前有很少的部分 算法可以针对海量数据点集，例如文献【18 】中的b n l 算法，文献【1 9 】中的s f s 算 法。但当数据量太大无法装入内存时，由于页面在内外存之间的置换会使得算法 性能严重下降，系统i o 所花费的时间成为制约算法效率的瓶颈。针对这种问题 本课题专门研究针对海量点集数据的极大点查找算法及相关应用。 1 2本文成果 本文研究了已有的极大点查找算法。在此基础上提出一种针对海量点集数据 的极大点查找概率算法，并证明了算法的可靠性。通过实验取得了很好的实验效 果。并对其在数据库查询中的应用进行了研究。 本文的研究工作和创新包括以下两个方面： ( 1 ) 针对极大点查找问题，目前还没有线性输入输出次数的外存储算法。本 文根据极大点数目的概率特性，针对独立同分布数据集，设计出了一种针对海量 数据的线性输入输出次数的极大点查找算法。并证明了算法的可靠性，通过实验 2 硕士学位论文 取得了很好的实验效果。 ( 2 ) 随着信息技术的不断发展和应用的不断深入，数据收集手段越来越丰富， 海量存储在数据库中也越来越普遍。本文将设计的算法应用到数据库的s k y l i n e 查询处理中，取得了良好的实验效果。 1 3本文的研究内容和组织结构 本文共分四章，文章结构及各章主要内容组织如下： 第l 章绪论介绍了研究背景、海量数据处理、外存储算法、极大点的基本概 念及本文所做的工作。最后给出了本文的整体组织结构。 第2 章主要介绍海量数据处理和外存储算法基础，并分析了现有的极大点算 法及研究进展。 第3 章介绍了文本设计的极大点查找概率算法及算法的可靠性分析和试验。 第4 章介绍了文本设计的极大点查找概率算法在数据库s k y l i n e 查询处理中的 应用，及试验分析。 结论总结了本文的研究工作，并对今后的研究做出了展望。 海量点集数据的极大点奔找算法及相关虑用研究 第2 章海量数据处理及极大点研究进展 在现实应用中存在大量的海量数据，由于其太大而不能完全装入计算机内存。 因此在快速的内存和相对慢速的外存( 比如硬盘) 之间的输入输出( i 0 ) 通讯 就成了制约算法性能的主要瓶颈。极大点集问题是计算几何的一个重要的基本问 题。由于极大点集在一个点集的边界上存在很多有意义的特性，其与凸包、最近 点对等问题均有密切的联系，所以极大点集在不同的领域均有广泛的应用。本章 介绍了海量数据处理和相应的外存储算法，以及目前极大点研究的进展，简要介 绍了各种极大点查找算法。 2 1 海量数据处理及外存储算法 近些年我们已经被各领域中大量增加的数据所淹没，这些领域包括数据库、 科学计算、图像、娱乐、多媒体、传感器、w 曲应用、电子邮件等。例如美国国 家航空和航天管理局( n a s a ) 的地球观测系统项目( 是其地球科学事业的核心 部分) ，每年产生千兆字节( 1 0 ”字节) 的光栅数据【2 们。1 千兆字节粗略的相当于 1 0 亿本图表格式书籍的信息总量。微软公司的t e r r a s e r v e r 在线卫星图像数据库 ( m s n 虚拟地球的一部分) 【2 1 】和g o o g l ee a r t h 【2 2 】的数据量以t b ( t e r a b y t e ，1 0 1 2 字节) 为单位。沃尔玛( w a l m a r t ) 的销售库存数据约5 0 0 t b 。所以一个主要的 挑战就是开发出处理这些数据的机制，否则很多数据就会失去它的价值。 出于经济的因素，目前的通用计算机系统通常包括一系列等级的存储器，不 同等级的存储器有其自身的造价和性能特点。在最低层是c p u 寄存器和缓存，其 存储速度最快同时造价也最高。对于内存储器，通常是动态随机访问存储器 ( d r a m ) 。再高一级就是以造价较低同时存储速度较慢的磁盘作为外部的大容量 存储介质，或者利用存储速度更低的大容量设备比如磁带或者光盘作为档案性质 的存储介质。这些设备可以通过光纤网络( 例如光纤通道或者互联网小型计算机 接口i s c s i ) 提供大量的外部存储容量。图2 1 描述了一个典型的存储器层级和 相应特点。 4 硕十学何论文 i - 3 2 g b 1 0 0 g & l p b 图2 1 一个典型的单处理器系统存储器层级图 如图2 1 一个典型的单处理器存储层级包括寄存器( r e g i s t e r ) 、指令高速缓 冲存储器( i n s t r u c t i o nc a c h e ) 、数据高速缓冲存储器也叫一级缓存( d a t ac a c h eo r l e v e l1c a c h e ) ，二级缓存、内存和磁盘。有一些系统会添加3 集缓存，图片里并 没有显示。存储器存取的时间范围从寄存器和高速缓冲存储器的不到1 纳秒( 1 n s ， 1 0 拶秒) 到磁盘的几毫秒( m s ，1 0 3 秒) 。典型的不同层级存储器大小显示在图2 1 的下面。显示在图顶部的b 表示典型的在两个连接存储层之间传递数据块 ( b l o c k ) 的大小。所有的数据以字节( b y t e ) 、k b ( 1 0 3 b ) 、m b ( 1 0 6b ) 、g b ( 1 0 9 b ) 、p b ( 1 0 ”b ) 为单位。在图中，内存与磁盘之间传输块的大小8 k b 仅是一个 指示数值，在一些批处理应用中通常会使用更大的逻辑传输块。 大多数的现代编程语言基于内存被认为是一个统一的地址空间的编程模式。 虚拟存储的概念使得地址空间可以远远大于实际计算机内存的大小。程序员有一 个自然的趋势就是假设所有使用的存储器具有相同的存取速度。在很多情况下， 这种假设是合理的( 至少是无害的) ，特别是当数据集不大的情况。这种编程模式 的实用与优雅在很大程度上是其广泛应用的原因，并且对软件产业产生了很大的 贡献。 但事实上，并不是所有的存储器存储速度都是一样的。大地址空间会跨越多 个级别的存储器层次，在最低层的存储器上存储数据比在高一级的存储器上存取 数据要快几个数量级。例如，一个数据寄存器的存取花费几分之一纳秒( 1 0 。9 秒) ， 内存花费几纳秒；但是磁盘要花费数毫秒( 1 0 3 秒) ，要大约慢1 0 0 万倍! 在实际 应用中处理海量数据时，相应的在存储器不同级之间的输入输出通信( i o c o m m u n i c a t i o n ) 往往成为了瓶颈。 许多计算机程序在其存储模式中会呈现一定程度的局部性( l o c a l i t y ) ，也就 是特定的数据在一段时间内被反复的引用，之后程序的注意力会转移到其他一组 5 海量点集数据的极大点查找算法及相芙应用研究 数据中。现代操作系统通过跟踪程序所谓的“工作集”( w o r k i n gs e t ，一个较模 糊的名词用来粗略的对应在程序中最近频繁引用的数据【2 3 】) 来利用这种存取模式 的特点。如果工作集较小，就可以将其存储在较高速的存储器中以节省存取时间。 缓存和启发式的预载被用来减小“缺失 的发生次数。“缺失 是指引用的数据不 在缓存中，只能从高一级的存储设备中调入。例如，在一个页缺失中，需要通过 1 次i o 通讯将一页数据从磁盘调入内存。 缓存和预载方法针对通用的目标而设计，所以不能够像预想的一样利用到每 一个计算的局部性特点。另外，一些计算本身固有的没有局部性，即使是无所不 知的缓存管理决策技术也注定会存在大量的i o 次数和拙劣的性能。性能提升本 质上或许应该通过将局部化特点直接应用在程序算法的设计上，明确的管理各级 存储器内容，而不是通过虚拟存储系统。 所以明确的管理数据存储和传输就是外存储算法和数据结构( e x t e r n a l m e m o r ya l g o r i t h m sa n dd a t as t r u c t u f e s ) 主要考虑的内容。外存储算法有些文献 也称作i o 算法或者o u t o f - c o r e 算法。这类算法通常关注随机存储器的内存和磁 盘的外存之间的i o 通信，因为他们之间的存取速度差别相对最明显。同时内外 存之间的i o 通信次数作为衡量算法效率和复杂度的主要标准。 2 2极大点定义 在一个点集中，如果点尸的每一维坐标( c o o r d i n a t e ) 都大于点9 的相应维 坐标，则称作点p 支配( d o m i n a t e ) 点q 。如果一个点不被集合中任何另外一个 点支配，这个点就称作极大点( m a x i m a lp o i n t ) 。不被支配的所有点组成的集合就 称作这个点集的极大点集( m a x i m a ) 【4 】。 簿 ， x 轴 图2 2 一个二维极大点示例 6 硕十学位论文 如图2 2 是一个二维极大点的示例，图中p 点的每一维坐标都大于点q 的相 应维坐标，我们称点p 支配点q 。而尸，p j ，p 2 ，p 3 互相不能支配所以p ，p j ， 尸2 ，尸3 构成了这个二维点集的极大点集。 由于极大点集在一个点集的边界上存在很多有意义的特性，其与凸包、最近 点对等问题均有密切的联系，所以极大点集问题是计算几何的一个重要的基本问 题。同时极大点集在不同的领域均有广泛的应用。这些领域有 1 多晶体设计与分析【2 4 2 5 】； 2 多标准最优化中的排列最忧性【2 6 2 7 1 ； 3 进化计算【2 8 2 9 1 ； 4 超大规模集成电路( v l s i ) 设计f 3 叼1 ，翊； 5 网络【3 3 ，3 4 ，3 5 ，3 6 1 6 背包问题【3 7 ，3 8 ，3 9 】： 7 最长公共子序列问题【4 0 4 1 】： 8 数据挖掘【4 2 ，4 3 】： 9 图着色m ，4 5 】： 1 0 人工智能中的启发式搜索m 7 ，4 8 4 9 1 ； 1 1 线性规划分析【5 0 ，5 1 1 ； 1 2 运输问题【5 2 ，5 3 ，5 4 1 ； 1 3 基因分析【5 5 5 6 】： 1 4 统计决策理论【5 7 ，5 8 1 ； 1 5 生态处理模型f 5 9 6 0 1 。 2 3 已有的极大点内存储查找算法 从1 9 6 6 年b a r n d o r f f - n i e l s e n 和s o b e l 在文献【8 】中对极大点集数目的研究开始， 对极大点集问题研究已有很多的成果。存在相当多的算法来查找集合中的极大点。 我们可以总结为有连续( s e q u e n t i a l ) 算法【4 ，9 1 ，分治( d i v i d e a n d c o n q u e r ) 算法 【9 1o ，1 1 1 ，桶( b u c k e t ) 算法【1 2 1 3 1 ，挑选( s e l e c t i o n ) 算法【1 4 1 ，筛( s i e v e ) 算法1 4 】 等。下面将对各类算法进行简单的论述。 连续算法，最直接的极大点查找算法，满足渐进性，在线性。以下是该类算 法的伪代码： a l g o r i t h ms e q u e n t i a l ( d ) i n p u 仁 a 1 ，a 2 ，a n ) ， a j r d ，j = 1 ，n m ：= a l f o ri ：= 2t ond o i fa id o m i n a t e ss o m ep o i n t si nmt h e n 7 海茸= 点集数据的极大点夯找算法及相关席用研究 d e l e t et h e s ep o i n t s ； m ：= m u a i e l s e i fv 6 m ，a ii si n c o m p a r a b l ew i t hbt h e n m ：= m u a i o u t p u tm ：= m a x i m a a 1 ，a 2 a n ) 算法中点p 和点g 不可比较( i n c o m p a r a b l e ) 是拗无法支配( d o m i n a t e ) g ，g 也 无法支配( d o m i n a t e ) p 。k u n g 等人在文献【9 】中利用平衡搜索树去维持以搜索到 的极大点，而b e n t l y 等人在文献【4 】中利用链表，并且当一个新插入点被支配时应 用移动到开头( m o v e t o f r o n t ) 的启发式策略，从而提高算法的效率，使得算法 平均时间复杂度达到线性，具体证明参见g o l i n 的文献【1 5 】。 分治类算法，另外一种简单的极大点查找算法，算法为代码如下： a l g o r i t h md i v i d e - a n d c o n q u e r i n p u t = p ：= a 1 ，a n ，a j r ，j = 1 ，“ m a x i m u m a 1 ，a n ( n = 1 ) i fn = lt h e nr e t u r na n m 1 ：= m a x i m u m a 1 ，a n 2 】 m 2 ：= m a x i m u m a n 2 】+ l ，a n i f m l = m 2t h e nr e t u r nm l e l s er e t u r nm 2 o u t p u tm a x a 1 ，a 2 a n ) 算法中的分治规则可以改变，例如在文献【9 】中，k u n g 等人利用双向分治策略， 在维数和点数上进行双向分治，以提高算法在多维点集中的效率。 桶算法，对于有序序列上的分治算法自上而下的描述产生了桶选择算法，对 于查找给定序列的极大点查找参见m a h m o u d 等的文献 1 6 】。将桶算法进行直接的 普遍化就可以实现对于高维数据的极大点查找1 2 ，13 1 。值得注意的是桶算法不同于 连续算法和分治算法，其对输入点集的分布存在更多的敏感性。 挑选算法，算法伪代码如下： a l g o r i t h ms e l e c t i o n i n p u t = p ：= a 1 ，a n ，a j r 2 ，j = 1 ，n s e l e c t i o n ( p ) i f | p | = lt h e nr e t u r np c h o o s eam a x i m a lp o i n txi np d i s c a r dp o i n t sd o m i n a t e db yx m ：2 x ) f 1 0 re a c hn o n e m p t yq u a d r a n tqo fxd o m ：= mus e l e c t i o n ( q ) r e t u r nm 8 硕士学位论文 o u t p u tm ：= m a x i m a a 1 ，a 2 a n 该算法的预期复杂度是线性的【1 7 】。对于2 维以上的点集也能够产生类似的算 法，但需要类似分治算法中的额外的归并过程。c l a r k s o n 在文献【1 4 】中讨论了另外 一种顺序选择算法，通过如下步骤一个一个的选择极大点构成极大点集。通过比 较每一个不可比( i n c o m p a r a b l e ) 元素p 来构造极大点集( 初始为空) 。如果p 点可 以被支配，删除p 。否则p 仍然属于不可比集合，并通过扫描剩余的元素利用其来 发现其他的极大点。并在p 被支配的时候及时地更新p 。其过程类似于选择排序。 c l a r k s o n 的算法可以针对任意维的点集，但当极大点比较多的时候算法效率非常 低。 筛算法，挑选算法对寻找第一个好的筛点有一些作用。但是当我们知道更多 的输入数据信息时( 除维数以外的，比如输入集的分布) ，可以在不花费额外代价 的情况下很快地确定一个具有强大筛能力的筛点。算法伪代码如下： a 1 9 0 r i t h ms i e v e ( d ) i n p u tp = a 1 ，a n ，a j r d ，j = l ，n ， m ：= 1 2 i c h o o s eas i e v ep o i n t ，s a yx x 甓p f o ri ：= lt 0nd o i f a ii sn o td o m i n a t e db yxt h e nm ：= m u a i i fa l lm a x i m aa r ei n c l u d e di nmt h e n f i n dt h e s em a x i m a e l s e u s eo t h e rm a x i m a f i n d i n ga l g o r i t h m o u t p u tm a x i m a a l ，a n 以上介绍的算法均是针对输入数据可装入内存的情况。对于不同的分布数据 这些算法性能各有优劣，但当数据量太大无法装入内存时，这些算法都不适用。 由于页面在内外存之间的置换会使得算法性能严重下降。在海量数据处理时，系 统i o 所花费的时间成为制约算法效率的瓶颈。下一节将介绍极大点查找的外存储 算法。 2 4 已有的极大点外存储查找算法 这些算法关注的都是在数据量大、无法放入内存的情况下对极大点问题的处 理，主要有b n l 、s f s 、d & c 、b i t m a p 、l e s s 算法。 b n l ( b l o c k n e s t e d 1 0 0 p s ) 算法1 1 8 】：该算法是对待测元组建立临时表丁，r 由一 个个的临时表乃组成，要读取的第1 组输入放在临时表乃中。然后在主存中维持 一个窗口队列，以收集相互间不存在支配关系的点，窗口队列初始化为空。算法 开始时，第1 个读取的点自然地被放进窗口队列中。然后，每当从当前临时表队列 乃中读入一个点p 时，就用该点和窗口队列中已有的所有点依次进行比较，可能出 9 海量点集数据的极大点查找算法及相关廊用研冤 现以下的3 种情况： 1 ) 窗口中存在点支配点p ：p 被删除，以后的迭代中也不再考虑p 。 2 ) 窗口中存在点被点p 支配：从窗口队列中删除被p 控制的点，以后的迭代 中也不再考虑这些点，p 插入窗口队列中。 3 ) 点p 和窗口中所有点都不存在控制关系：若窗口中有足够空间，则物插 入窗口队列中；若空间不够，则将p 写入下一个临时队列乃+ j 中。 每当算法扫描到乃队列的末尾时，就有一些极大点被确定了。若乃+ j 队列为 空，则算法终止，此时，所有窗口队列中的点都是极大点；否则，重复这个比较 的过程，新的当前处理队列是乃+ j 队列。每次迭代结束，都输出窗口队列中已和 临时表中的所有点比较过的点。这些点既不受控于其他点，也不会控制还在考虑 中的任何点。其他的点若在下一次迭代过程中没有被删除，则被输出。易知，一 个点越早被插入到窗口队列中，在下一次迭代中就越可能早地被输出。为了跟踪 一个窗口队列中可能被输出的点，算法为每个窗口队列中的点和写入临时文件中 的点都设置了一个时间戳。这个时间戳实际上就是一个记录点顺序的计数器，因 此，若从临时文件中读入的点的时间戳是t ，则可输出窗口队列中所有时间戳小于 f 的点。算法利用时间戳保证了不会出现两个点重复比较的现象和算法能够有效 地及时终止的条件。 该算法的改进思想是将窗口队列变成一个能自动组织队列，替换窗口中的点， 替换策略是保证窗口队列中的点尽可能控制更多的点。例如当一个点被发现支配 其它点时，将它移动到窗口最前面，因为按经验这个点更能支配剩余得点，以减 少比较次数。 b n l 算法最大的优点是它的简单性和普遍性，对于各种数据分布、各种大小 的数据集，b n l 算法都可以直接应用而不需要对数据进行任何索引或预处理。虽 然b n l 算法在数据集较小的情况下效率较高，但当数据集较大或内存很小的时候 就需要多个循环才能计算出所有的结果。导致多次文件输入输出存取，影响算法 的效率。 s f s ( s o r t f i l t e r s k y l i n e ) 算法【1 9 】：该算法是在b n l 算法的基础上对数据集进行 了预排序。b n l 算法的i o 开销依赖于迭代的次数和每次迭代要处理的数据集 的大小。因为内存中窗口大小有限，不一定能装下所有的极大点，所以对要处理 的点先排序，过滤掉一些受支配点，因此，便有了s f s 算法。s f s 算法的思想 是，对临时表中的点按照极大点的选取规则先做一个拓扑排序，然后用b n l 算 法处理这些点。故一旦有一个临时表乃中的点被加入窗口中，它就一定是极大 点了。因为乃有序，所以它后面的点不可能控制它，这样就不需要做替换的检 查，减少了开销。因此，s f s 算法在保持了b n l 算法优点的基础上，较大程度的 提高了计算的效率和渐进性。 d & c ( d i v i d e a n d c o n q u e r ) 算法【1 8 1 ：该算法将数据集划分为几部分，使得每部 分都可以放入内存，然后使用内存算法分别计算每一部分的极大点，最后通过合 l o 硕士学位论文 并每部分的极大点去除其中受控的数据点来得到最终的极大点集。该算法的具体 流程是： 1 ) 计算输入的点在某维却上的中值( 这里的中值可以指精确中值，也可以 指模糊中值) m p ，并按这个中值把输入的点集划分为两部分p j ，p 2 。其中，尸j 集 合包含所有在劫上的属性值优于m p 的点，p 2 集合包含其他剩余的点。 2 ) 分别计算p j 的极大点集合s j 和p 2 中的极大点集合舳。计算时，p j 和 尸2 不断地迭代划分，直到每个部分只包含一个或没有点为止。 3 ) 通过合并全部的集合肼和艘，得到最终的极大点集合。具体地说，就是 删去黝中被s j f 中的点控制的点。 算法的改进： ( 1 ) 划分的界限不一定必须是中值； ( 2 ) 将2 一路划分改进为朋路划分； ( 3 ) 第3 步的最初划分中的归并函数可以用一个b u s h y 路归并 d & c 算法对于能完全写入内存的小数据集效率很高。但当数据集很大，不能 完全放入内存中时，d & c 算法不仅要从硬盘中读取数据，还至少要将数据写入硬 盘一次，导致较大的输入输出开销。 b i t m a p 算法【6 1 】：该算法是采用位图结构来判断一个点是否是极大点，算法 满足渐进性，无须遍历整个数据集，找到一个极大点便可以及时返回，因为按位 操作计算速度很快，故可以很快地判断出一个点是否是极大点。下面是对这一算 法的描述及一些定义的说明： ( 1 ) 待测数据集为d ，包含的都是d 维空间的点； ( 2 ) 在第f 维上有岛个不同的属性值( j 固功； ( 3 ) p ，代表第f 维上的第歹个不同的属性值，不失一般性，不妨设p l j 印口 p 砌，所有维上属性值的范围都映射到 o 1 】； ( 4 ) 本算法考虑取大操作为优( m a x ) 。 算法基于的规则： _ 个点x = 伍j ，砣，x 用一个朋位的向量表示，其中，x j 用岛位表示， 则m 为所有岛的总和，即为点x 在所有维上不同属性值的个数