（计算机软件与理论专业论文）轮廓聚合查询算法的研究.pdf

j 1 1 ，_r a t h e s i sf o r t h ed s t u d y b y c h e nh u a n s u p e r v i s o r ：a s s o c i a t e p r o f e s s o ry a n gx i a o c h u n n o r t h e a s t e r nu n i v e r s i t y j a n u a r y 2 0 0 8 。1 飞 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名： 辱卜乏 签字日期： 学位论文版权使用授权书 彳 2 、卅 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：互、，堤导师签名：榭睬 飙砒广嗍贼7 70，j、引1 东北大学硕士学位论文 轮廓聚合查询算法的研究 摘要 轮廓查询在涉及多标准决策的空间数据库、数据挖掘、测试观察、用户偏好查询、 可视化等领域起着非常重要的作用，是一种典型的复杂查询。目前的研究主要涉及简单 的轮廓查询，而不能满足实际应用的需求，基于此，本文提出了轮廓聚合查询，以满足 复杂查询应用需求，并提出相应的查询处理方法。 本文通过对不同聚合函数的分析，提出了在一般聚合情况下的基本算法一聚合优 先算法a a c n ( a g g r e g a t e a l l ，c o m p u t en e x t ) 。a a c n 算法的基本思想就是先对数据集 按着数据点进行聚合操作，然后再对得到的数据列表进行轮廓查询。在此基础上对算法 进行了分析与改进，提出了在特殊聚合函数下的时刻优先算法c e t a n ( c o m p u t eo n e v e r yt i m e ，a g g r e g a t en e x t ) 和基于过滤策略的动态优化a b t ( a g g r e g a t i o nb a s e do n t i m e ) 算法。其中c e t a n 算法就是先对每一个时刻的数据进行轮廓查询，再对得到的 结果进行聚合操作；a b t 算法的基本思想就是采用过滤策略不断地对数据集进行过滤更 新，最终得到想要的结果，这种算法支持数据集动态的更新。 最后通过实验，模拟出3 种数据集：正相关数据集、反相关数据集、不相关数据集， 来分别对算法进行测试。实验结果表明了算法是有效的，对于历史数据的查询，算法可 以极大地改善查询的精确性和多样性。 关键词：轮廓查询，聚合，历史数据，过滤，空间数据库 一i i tlif，l， _ k -khj 、ifiij 、，j0j b a s e do nt h ec o m m o ns i t u a t i o nt h i sp a p e rp r o p o s e st h eb a s i ca l g o r i t h m ，w h i c hc a l l e d a g g r e g a t i o nf i r s ta l g o r i t h ma a c n ( a g g r e g a t ea l l ，c o m p u t en e x t ) a sw ea n a l y z et h ed i f f e r e n t a g g r e g a t i o nf u n c t i o n t h eb a s i ci d e ao fa a c na l g o r i t h mi s t h a tf i r s t l ya g g r e g a t ea l lt h e d a t a s e tb a s e do nt i m e ，s e c o n d l yd ot h es k y l i n eq u e r yo nt h e m b a s e do ni tw ea n a l y z et h e a l g o r i t h ma n db r i n gf o r w a r d sa n o t h e rt w oa l g o r i t h m s ，w h i c hc a l l e dt i m ef i r s ta l g o r i t h m c e t a n ( c o m p u t eo ne v e r yt i m e ，a g g r e g a t en e x oa n da l g o r i t h mb a s e do nf i l t e rs t r a t e g y a b t ( a g g r e g a t i o nb a s e do nt i m e ) a m o n gt h e mc e t a na l g o r i t h mi s t h a t f i r s t l yd ot h e s k y l i n eq u e r yo ne v e r yt i m e ，s e c o n d l ya g g r e g a t et h er e s u l tl i s t ；w h i l et h ek e yi d e ao fa b t a l g o r i t h mi st h a tu s i n gf i l t e rt of i l t r a t ea n du p d a t et h ed a t a s e tc o n s t a n t l y , g e to u r r e s u l t si nt h e e n d ，a n dt h i sa l g o r i t h ma l l o w st h ed y n a m i cu p d a t i n go nd a t a s e t a tl a s tu s i n gt h r e et y p e so fd a t a s e t s ，w h i c hc a l l e dc o r r e l a t e dd a t a , a n t i - c o r r e l a t e dd a t a a n di n d e p e n d e n td a t ar e s p e c t ，e x p e r i m e n ts i m u l a t e sa n dt e s t st h et h r e ea l g o r i t h m s a n dt h e e x p e r i m e n t a lr e s u l t sv a l i d a t et h a to u ra p p r o a c h e sa r ef e a s i b l ea n di m p r o v eo u rq u e r yo n p r e c i s i o na n dv a r i e t y k e yw o r d s ：s k y l i n eq u e r y , a g g r e g a t i o n ，h i s t o r i c a ld a t a , f i l t r a t e ，s p e c i a ld a t a b a s e i i i l l l i f l，1， lfli! 、|ij 东北大学硕士学位论文 目录 独创声明 摘要 a b s t r a c t 第一章引言。 1 1 研究背景 1 2 问题的提出 1 3 研究意义 1 4 组织结构 第二章相关工作7 2 1 轮廓查询相关工作7 2 1 1 轮廓查询操作符7 2 1 2 块嵌套循环方法8 2 1 3 分而自治的轮廓查询1 0 2 1 4 位图轮廓查询1 1 2 1 5b t r e e 索引轮廓查询。1 2 2 1 6r - t r e e 索引轮廓查询1 3 2 1 7 边界区域轮廓查询1 4 2 1 8 基于排序过滤的轮廓查询1 5 2 2 相关问题1 5 2 2 1k n n 问题15 2 2 2t o p k 问题1 6 2 2 3c o n v e xh u l l 问题17 2 3 轮廓查询最新研究1 9 2 3 1 基于流上的轮廓查询1 9 2 3 2 基于时间序列的多维轮廓查询2 0 2 3 3 在多维空间上的k d o m i n a n t 轮廓查询2 0 2 3 4 分布式环境下的轮廓问题2 1 2 4 本章小结2 2 第三章轮廓聚合查询问题2 3 3 1 基本概念2 3 一i v 东北大学硕士学位论文目 录 3 1 1 轮廓查询相关定义2 4 3 1 2 轮廓查询相关性质2 7 3 2 轮廓聚合查询2 7 3 3 本章小结2 8 第四章轮廓聚合查询基本算法2 9 4 1 相关定理2 9 4 2 基本算法描述3 0 4 2 1 聚合操作模块3 3 4 2 2 轮廓查询模块3 5 4 3 算法分析。3 6 4 4 本章小结3 6 第五章轮廓聚合查询的改进算法3 7 5 1 轮廓优先算法3 7 5 1 1 框架介绍3 9 5 2 基于过滤策略的动态优化算法4 0 5 2 1 聚合过滤模块算法。4 2 5 2 2 轮廓查询模块4 5 5 3 算法分析4 6 5 4 本章小结4 7 第六章实验测试与分析4 9 6 1 测试维度对算法效率的影响一5 0 6 2 测试时刻个数对算法效率的影响一51 6 3 测试数据集大小对算法效率的影响。5 2 6 4 本章小结5 4 第七章结束语5 5 7 1 本文总结5 5 7 2 工作展望5 6 参考文献5 7 致i 射61 攻硕期间参与的项目及发表的论文6 3 一v 一 1 j 东北大学硕士学位论 随着信息技术 集手段越来越丰富 化、更高效的要求 由此被引出来，而 1 1 研究背景 轮廓查询技术 个世纪的时间里， 来越多的研究者加入1 3 1 。数据库的诞生和发展给计算机信息管理带来了一场巨大的革命。 三十多年来，国内外已经开发建设了成千上万种数据库，它已成为企业、部门乃至个人 日常工作、生产和生活的基础设施。同时，随着应用的扩展与深入，数据库的数量和规 模越来越大，数据库的研究领域也已经大大地拓广和深化了。3 0 年间数据库领域获得了 三次计算机图灵奖( c w b a c h m a n ，e f c o d d ，j g l a y ) ，更加充分地说明了数据库是一个 充满活力和创新精神的领域【4 巧】。 随着信息技术的发展，采用二维表结构的数据库，已经无法保存大量的多媒体等非 结构化的复杂数据以及各类数据之间的关系，关系型数据库亟待突破。信息技术平台的 选择常常是建立或重新建立应用系统时的关键问题，而数据库正是其中需要做出选择的 关键平台。关系数据库管理系统曾处于技术主流而独领风骚，但是这种传统的数据库管 理系统因为采用二维数据模型，而存在本身固有的约束和限制，从而难以适应当今迅速 变化的业务需求，以及新技术的发展。首先，数据处理不仅在数量上要求越来越大，而 且在质量上也要求越来越高，数据库所管理的数据已经发生了根本的变化。这一变化给 数据库技术带来了巨大挑战，数据库管理的对象已不再仅限于文本数据等简单的数据类 型【6 1 ，而需要描述和保存大量多媒体非结构化的复杂数据以及数据间的关系。此外，随 着热门网站访问数量的激增，对数据库本身的存储机制、大量并发用户的使用需求、存 储空间的使用效率、以及数据的完整性和安全性等方面都提出了更高要求。而这些都不 是在传统关系数据库中，使用二维表的简单结构就可以满足的。其次，关系型数据库依 据的是把数据表示为简单的二维模型，即表示为行与列的记录来进行存储处理。显然由 于受到当时条件的限制，只是一种适合于对简单数据存储处理的技术，存在难以克服的 一1一 东北大学硕士学位论文 第一章引言 局限性。 空间数据库在这样的背景下产生了，而所谓空间数据是指与空间位置和空间关系相 联系的数据。归纳起来它具有以下几个基本特征： ( 1 ) 空间特征。每个空间对象都具有空间坐标，即空间对象隐含了空间分布特征。 这意味着在空间数据组织方面，要考虑它的空间分布特征。除了通用性数据库管理系统 或文件系统关键字的索引和辅关键字索引以外，一般需要建立空间索引。 ( 2 ) 非结构化特征。在当前通用的关系数据库管理系统中，数据记录一般是结构 化的。即它满足关系数据模型的第一范式要求，每一条记录是定长的，数据项表达的只 能是原子数据，不允许嵌套记录。而空间数据则不能满足这种结构化要求。若将一条记 录表达一个空间对象，它的数据项可能是变长的，例如，一条弧段的坐标，其长度是不 可限定的，它可能是两对坐标，也可能是十万对坐标；其二，一个对象可能包含另外的 一个或多个对象，例如，一个多边形，它可能含有多条弧段。若一条记录表示一条弧段， 在这种情况下，一条多边形的记录就可能嵌套多条弧段的记录，所以它不满足关系数据 模型的范式要求，这也就是为什么空间图形数据难以直接采用通用的关系数据管理系统 的主要原因。 ( 3 ) 空间关系特征。空间数据除了前面所述的空间坐标隐含了空间分布关系外， 空间数据中记录的拓扑信息表达了多种空间关系。这种拓扑数据结构一方面方便了空间 数据的查询和空间分析【7 1 ，另一方面也给空间数据的一致性和完整性维护增加了复杂性。 特别是有些几何对象，没有直接记录空间坐标的信息，如拓扑的面状目标，仅记录组成 它的弧段的标识，因而进行查找、显示和分析操作时都要操纵和检索多个数据文件方能 得以实现。 ( 4 ) 分类编码特征。一般而言，每一个空间对象都有一个分类编码，而这种分类 编码往往属于国家标准，或行业标准，或地区标准，每一种地物的类型在某个g i s ( g e o g r a g h i ei n f o r m a t i o ns y s t e r m ，地理信息系统) 中的属性项个数是相同的。因而在许 多情况下，一种地物类型对应于一个属性数据表文件。当然，如果几种地物类型的属性 项相同，那也可以多种地物类型共用一个属性数据表文件。 ( 5 ) 海量数据特征。空间数据量是巨大的，通常称海量数据。之所以称为海量数 据，是指它的数据量比一般的通用数据库要大得多。一个城市地理信息系统的数据量可 能达几十g b ，如果考虑影像数据的存贮，可能达几百个g b 。这样的数据量在城市管理 的其他数据库中是很少见的。正因为空间数据量大，所以需要在二维空间上划分块或者 一一一一 、 ； j 东北大学硕士学位论文第一章引言 图幅，在垂直方向上划分层来进行组织。 基于空间数据库的发展背景，产生了轮廓查询技术。轮廓这个名词最初是在像等高 线、最大向量和突出的外壳这样的古老研究中提出的，而形成最初的算法是在文献【8 】 中提出的轮廓操作符。它是在数据库环境下，由s q l ( s t r u c t u r e dq u e r yl a n g u a g e ， 结构化查询语言) 语句演变而来的。这个操作符可以过滤出一系列用户所关心的点，即 开始时定义的轮廓查询结果集【9 1 。 1 2 问题的提出 轮廓计算【lo 】可以用来处理很多不同领域的数据集，如传统集中式数据库、数据流 1 1 , 1 2 】、时空数据库、甚至类别属性数据集【1 3 1 等。轮廓查询算法面临着很多要求和挑战， 如数据集的分布对于轮廓查询计算的效率影响很大。 近些年来，越来越多的数据表现出历史性，同时由于数据量的增加，数据的查询效 率已经成为更多人士关心的问题。也就是说，历史数据的大量存在使得数据的查询效率 变得越来越低，因此，如何提高数据的查询效率并实现数据查询的多样性，以便使查询 结果可以更好地为用户服务，已经成为国内外学者关注的焦点。本文正是基于该思想， 提出了历史数据的轮廓聚合查询，即采用聚合的方法对历史数据的轮廓查询进行计算， 以实现查询的准确性和多样性。 轮廓计算是数据库领域的一个最新研究热点，但是传统的轮廓技术有些时候并不能 满足现在多元化、人性化的查询需求。由于每个用户的需求不同，而且传统的轮廓查询 并没有针对整体的查询，针对这些，曾经有人提出过基于时间序列的轮廓查询，但该基 于时间序列的轮廓查询只考虑到元组的过期情况，这显然是一种不太精确的查询方法。 如果需要对于历史数据进行存储，并且用户需要综合这些历史数据进行轮廓查询，从而 对数据进行筛选，那以前的轮廓查询方法就无法满足用户需求，因此引入了一种新的历 史数据的轮廓查询方法，即用聚合的方法来实现对历史数据的轮廓查询。 在该新的历史数据的轮廓查询算法中，将引入对历史数据进行的轮廓查询，并介绍 如何去定义一个历史数据的轮廓。通过实验不难证明，使用这种算法可以极大地节省在 空间上和时间上的消耗。查询处理技术【”1 的主旨在于解决如何对历史数据进行处理，如 何对历史数据进行有效的查询，使得系统能够达到最小的调用系统i 0 ，并且在空间上 得到大大的节省，做到资源利用率的最优化。本文针对以上几个问题进行了初步的研究， 并做出了如下几点贡献： 一3 一 东北大学硕士学位论文 第一章引言 ( 1 ) 通过对数据的历史性进行分析，从而引进了一个新的查询，即历史数据的轮 廓聚合查询，并且第一次提出了在轮廓查询的框架下做聚合查询，从而实现了查询的多 样化。 ( 2 ) 通过对历史数据的轮廓聚合查询的分析，采用不同的策略，提出三种算法一 一时刻优先算法c e t a n ( c o m p u t eo i le v e r yt i m e ，a g g r e g a t en e x t ) 、聚合优先算法 a a c n ( a g g r e g a t ea l l ，c o m p u t en e x t ) 和基于过滤原理的a b t ( a g g r e g a t i o nb a s e do nt i m e ) 算法，并通过对历史数据的分析实现了查询的优化处理。 ( 3 ) 通过实验对算法进行模拟。实验结果表明算法在查询的精确性方面是十分有 效的，并且极大程度地提高了查询性能。 1 3 研究意义 空间数据库中查询优化技术的研究，特别是轮廓查询技术的研究在空间数据库领域 具有深远的影响和巨大的作用。近些年来，轮廓操作和轮廓计算越来越受到人们的重视， 这主要是由于轮廓在多种实际应用中起到非常重要的作用，如多标准决策【1 6 1 、数据挖掘 和可视化【17 1 、用户偏好查询【1 8 】等。 数据库管理系统在决策支持中的应用越来越多，这些应用主要有以下四个特点。 第一，查询通常是基于多个目标的，且这些目标有时是有冲突的。例如，某人在旅 行中有很多的旅馆供其选择，根据酒店的价格和距离的远近决定哪一个适合用户。有离 当前位置近的和远的旅馆，可能离得近一些的旅馆价格高，离得远一些的旅馆价格低。 这些都要视情况而定。 第二，与传统的应用不同，该结果不是单个的最优结果( 或结果集) 。也就是说， 得到的结果对于用户来说不一定是最好的选择。例如，在上面所举的旅行例子中，不可 能只存在一个价格又低且距离市中心又近的旅馆，因此，对于用户来说，答案就是不确 定的。 第三，由于上面所述的第二点，用户通常查找令他们满意的结果。也就是通过对提 供给用户的结果集进行查找，最终找出用户所关心的结果。 第四，对于相同的查询，不同的用户根据他们个人的偏好可能找到不同的结果。这 里所谓不同偏好指的是用户对查询条件的选择有所不同。有的用户可能愿意多花一些钱 选择距离市中心近一些的旅馆，而有的用户可能愿意住稍微便宜一些的旅馆，只要去市 里方便一些就可以。 一4 一 东北大学硕士 据处理等领域的发展，空间数据库以及对空间数据进行查询的研究倍受关注。由于空间 数据量庞大、数据结构复杂【2 0 1 、操作代价昂贵，空间查询优化及处理势必成为空间应用 的难点和突破点，这就使得轮廓查询有了更宽阔的应用领域。 轮廓查询技术是现实生活中常见的问题，轮廓计算是解决空间数据库领域内类似问 题的一种非常重要的新方法。它具有一定的科研和学术价值，并且在实际应用中，这种 情况的发生也是非常普遍的，往往对于一个时刻的或者是某几个维度的轮廓查询所具有 的应用范围有限，很多实际例子都涉及到本问题，历史数据对于轮廓查询应该是比较关 键的，采用另外一种方式很好地解决了查询的多样性及准确性。可以说本研究课题继承 了前人的研究成果，并且通过转化形成了新的一个理论，这一技术具有较高的实际应用 价值，可以运用到很多的现实查询实例当中去。 1 4 组织结构 j 本文其他章节内容安排如下： 第一章为引言，主要介绍研究背景和现实意义。 第二章主要介绍当前有关轮廓查询的相关工作。 第三章给出本文的问题定义，介绍历史数据的轮廓查询的基本概念，其中包括讨论 问题所需定义、定理和证明等相关知识，以及本文所要讨论问题的详细描述。 第四章给出了在一般情况下的原始算法，其中包括了各个聚合函数下历史数据的轮 廓查询的最初算法聚合优先( a a c n ) 算法及相关说明。 第五章给出在特定聚合函数下历史数据的轮廓聚合查询的解决策略以及本文提出的 两种算法：时刻优先算法( c e t a n ) 和基于过滤策略的动态优化a b t 算法。 第六章主要通过实验对历史数据的轮廓聚合查询算法进行测试并对实验结果进行分 析。 第七章对全文进行了总结并对未来工作进行展望。 一5 一 一6 一 东北大学硕士学位论文 第二章相关工作 随着数据库的广泛应用，越来越多的数据被存放在数据库中，这使 并从中高效获取知识成为一种当然需要。为此，不同领域的学者从各自 行了有益的探索。近些年，一种新的数据库操作正逐渐成为当前研究热点之一，它是一 种有别于传统的数据库操作，其目的就是要搜索出数据集中所有不被任何其他点“支配” 的数据点，也称这样的点为轮廓查询的结果点。所谓个点支配另外一个点，是指一数 据点的每一维( 或者属性) 都不比另一点差，而且必需至少有一维比另一点好。其中差 和好并无统一的定义，它只是一种偏序关系，是根据用户的选择和喜好不同而有不同的 定义【3 4 1 。 2 1 轮廓查询相关工作 由于轮廓查询技术有着重要的理论研究价值和实际应用价值，所以一直是相关领域 专家们的研究重点【2 l 】。目前，已经有多种轮廓查询方法被提出。下面分别介绍国内外的 研究成果。 2 1 1 轮廓查询操作符 轮廓查询操作符又叫做s k y l i n eo p e r a t o r ，是最原始轮廓算法所提出的名词f 2 2 2 3 。它 是在数据库环境下，由s q l 语句演变而来的。这个操作符可以过滤出系列用户关心 的点集，即是开始时定义的轮廓点集。这一节主要介绍轮廓的起源，以及在数据库当中 的应用。 假设你要去旅游胜地巴哈马首都拿骚去度假，自然你希望寻找一个价格便宜尽量靠 近海边的好酒店。不幸的是，这两方面考虑的是鱼和熊掌不可得兼的关系。通常，越靠 近海边的酒店价格越高。旅行社的数据库管理系统也不能为你决定哪个是最好的酒店。 但是，其至少应该告诉你一些你感兴趣的酒店。实际上，如果不是两方面都不好于其他 酒店，这样的酒店都是可以感兴趣的，这里称这样的酒店组成的集合为轮廓结果集，每 个可以感兴趣的酒店称之轮廓结果点【2 4 】。 按照距离和价格组成的2 维坐标系，对空间数据集进行排列，由图2 1 所示，折线 相连的点即为既便宜又离海边近的轮廓查询结果集。很明显，很多其它决策地区的应用 系统也可以同样被找到。 一7 一 第二章相关工作 05 01 0 01 5 02 0 0 价格( 荚兀) 图2 1 旅店的轮廓点坐标 f i g 2 1c o o r d i n a t e so ft h eh o s t e ls k y l i n ep o i n t s 轮廓查询对于数据库可视化也有很大的帮助，如图2 2 所示，轮廓查询返回的是更 高、更靠近河流的建筑。换句话说，无论你个人对于价格还有距离的偏好有多少，你将 在轮廓点集中找到你想要的。并且轮廓点中一定不包含任何人所不想要的数据。在这里， 假设所有数据集都被放在内存中，并且这个数据集并不是想要的查询结果。主要是把轮 廓操作符结合到数据库操作系统中去。可以从图清晰地看出曼哈顿建筑物一部分。随着 数据管理技术向深度和广度的进一步发展，面向用户偏好的查询方式来寻找的应用将会 层出不穷【9 1 。 嬲彬一一粥一_ * 7 誊 ； 图2 2 曼哈顿的轮廓图 f i g 2 2s k y l i n ed r a w i n go fm a n h a t t a n 2 1 2 块嵌套循环方法 计算轮廓的一个直接方法就是将每个数据点p 与其他的每个数据点进行比较，如果 点p 不被支配，那么它就是轮廓的一部分。b o r z s o n y 等提出块嵌套循环方法b n l ( b l o c k 一8 一 东北大学硕士学位论文 n e s t e dl o o p ) 就是基于这个思想。b n l 算法是在整个数据集中构建 表，所有新到来的数据通过与现有的全部数据进行比较来实现数据的 这个轮廓列表就是最终的查询结果。一个b n l 的模型如图2 3 所示【2 磁盘 输入 主存 读入数据，比较溢出 一口皿一 窗口 临时文件 图2 3b n l 算法模型图 f i g 2 3m o d e lc h a r to fb n la l g o r i t h m 求轮廓的一个比较直接的方法是把每一个点与其它的每一个点相比较，如果这个点 不被支配，那么它就是轮廓的一部分。b n l 在此基础上扫描数据文件并在主存内保存 轮廓候选点的列表。第一个数据点插入到列表中后，随后的点分3 种情况： 1 ) 如果被列表中的任何一个点支配，那么就会被删除，它不是轮廓的一部分： 2 ) 如果支配列表中的任何一个点，那么将被插入列表中，并且列表中所有被支配 的点都将被删除。 3 ) 如果既不被支配，也不支配列表中的点，那么它将被插入到列表中，它有可能 是轮廓的一部分。 同时更新推荐列表，在扫描完所有数据后，所得到的推荐列表就是最后所要的轮廓 结果。b n l 的优点是它无需建立索引或把数据文件排序，可以应用到任意维空间。b n l 的缺点是依赖主存，列表可能会变得比主存还大。 下面介绍一下块嵌套循环算法的变种算法。首先维护窗口作为自组织列表：如果发 现窗口元组w 统治其他元组，则将w 移至窗口开始，这样下一条输入元组将首先与w 比较。特别适合于数据分布是偏斜的情况，也即存在一两个统治性元组( 即统治许多元 组) 以及大量中立元组( 即轮廓结果集中不统治其他元组的中立元组) 。替换窗口中元 组：在窗口中保持最有统治性的元组。假定窗口只能容纳两条元组，现有元组：嘲l ，5 0 5 ， 1 0m i l e 、 。新至l j ，显然j l l l 和厅3 能消除更多的元组， 一9 一 东北大学硕士学位论文第二章相关工作 用玩替换垃。替换策略为l r u ( l e a s tr e c e n t l yu s e d ，最近使用优先替换) 。其开销为： c u p 系统代价和元组两次比较的响应时间。b n l 优点是它无需建立索引或把数据文件 排序，可以应用到任意维空间。b n l 缺点是依赖主存，列表可能会变得比主存还大。 2 1 3 分而自治的轮廓查询 分而自治的轮廓查询即为d & c 方法( d i v i d e a n d c o n q u e r ) ，它是将空间数据集划 分成多个分区，这样可以把每一个分区放到主存。然后利用主存算法计算每个分区内的 轮廓上的点，最终的结果是把所有的分区结果放在一起求得。 2 1 3 1 基本分而自治算法 基本d & c 算法是基于对数据集进行区域划分，在自治区域内部进行查询处理，最 后再进行自治区域的合并的一种轮廓查询算法，实现原理如图2 4 所示，s l l 区域里的点 一定是支配s 2 2 区域里的点，基于这个原理，其实现过程如下：首先把所有的数据按照 属性列来对其进行区域划分，在将所有的数据分配到若干个子区域后，然后对每个区域 在其内部进行中间过程的轮廓计算，得到每个子区域内部的轮廓，最后再将所有子区域 内部的轮廓合并成全局的轮廓，在子区域合并的过程中，如果区域之间存在着支配关系， 就会直接过滤掉被支配的区域，减少合并过程，这样在计算过程中，能够使数据的计算 更加高效，有效地减少了系统c p u 和系统i o 的负担。 d & c 方法仅处理小数据集时效率高( 例如，如果把整个数据集放到主存中仅需要 应用一个主存轮廓算法) 。对于大数据集，划分过程至少需要对整个数据集进行一次读 和写，因此产生巨大的i o 代价，而且这种方法不适合在线处理，因为直到划分阶段结 束才能得出一条轮廓 9 1 。 图2 4 基本m e r g e 图 f i g 2 4t h eb a s i cc h a r to fm e r g e i l o 一 图2 5 三区域m e r g e 图 f i g 2 5t h ec h a r to ft h r e e - w a y 廓的计算能够有着更高的效率。 膨路划分( m - w a yp a r t i t i o n i n g ) 算法就为改进后的d & c 算法，如图2 5 所示，是3 - w a y m e r g e 方法，其实现过程如下：第一步，如果内存放不下输入，基本算法性能非常差， 因为需要反复读、划分、写入磁盘，直至某个分区适合放入内存。第二步，在第一步， 将输入划分为m 个分区，每个都可放入内存，用a 分位数代替中值，每个分区的轮廓都 可在内存中算出。在第三步，合并轮廓对，m 路划分保证所有子分区的合并在内存中执 行，即所有子分区最多占用可用内存的一半9 1 。 2 1 4 位图轮廓查询 位图方法将确定一个点是否在轮廓上所用到的全部信息用位图进行编码。位图方法 的效率取决于逐位操作的速度。这种方法根据点的插入顺序可快速返回少数轮廓上的 点，但不适合不同用户的优先考虑，这是一个好的轮廓算法的重要属性。整个轮廓的计 算非常昂贵。 l234567391 0善 图2 6 基本m e 唱e 图 f i g 2 6t h eb a s i cc h a r to fm e r g e 0 9 8 7 6 s 4 3 2 l o 东北大学硕士学位论文第二章相关工作 位图方法可以加速支配比较的计算，通过把操作符转化为一个按位比较的方法。其 具体方法如下：假设在第f 维上的值的不同的数量是m ，那么一数据点p 在这个坐标轴 上的坐标就可以用一个长度为m 的位字符串表示了。如果p 的坐标在这个维度上是最小 的，那么它的最后扣l 位被设定为0 ，其余几位被设为1 【2 5 1 。 举个例子来说明一下这个方法：如图2 6 所示的点坐标，n l = 1 0 ，n 2 = 1 0 ，那么点c ( 4 ，6 ) 就可以被表示为( 1 1 1 1 1 1 1 0 0 0 ，1 1 1 1 1 0 0 0 0 0 ) 。因为在x 轴上点c 是第3 个小的， 所以最后3 位被设为0 ，其他几位被设为l ；同理，在y 轴上点c 是第5 个小的，所以 最后5 位被设为0 ，其余几位设为1 。其它各点的b i t m a p 表示如表2 1 所示。 表2 1 基本m e r g e 表 t a b l e2 1t h eb a s i ct a b l eo fm e r g e 数据点位图表示 口( 1 ，1 0 ) b ( 3 ，8 ) c ( 4 ，6 ) d ( 6 ，8 ) e ( 9 ，9 ) 厂( 7 ，6 ) g ( 3 ，5 ) h ( 5 ，5 ) i ( 5 ，3 ) ( 6 ，5 ) k ( 8 ，4 ) ，( 6 ，3 ) 所( 1 0 ，1 ) 玎( 9 ，3 ) ( 1 1 1 1 1 1 1 1 1 1 。1 0 0 0 0 0 0 0 0 0 ) ( 1 1 1 1 1 1 1 1 0 0 ，1 1 1 0 0 0 0 0 0 ) ( 1 1 1 1 1 1 1 0 0 0 ，1 1 1 1 1 0 0 0 0 0 ) ( 1 1 1 1 1 0 0 0 0 0 。1 1 1 0 0 0 0 0 0 0 ) ( 110 0 0 0 0 0 0 0 ，11o o o o o o o o ) ( 1 1 1 1 0 0 0 0 0 0 ，1 1 1 1 1 0 0 0 0 0 ) ( 1 1 1 1 1 1 1 1 0 0 ，1 1 1 1 1 1 0 0 0 0 ) ( 1 1 1 1 1 1 0 0 0 0 ，1 1 1 1 1 1 0 0 0 0 ) ( 1 1 1 1 1 1 0 0 0 0 ，1 1 1 1 1 1 1 l o o ) ( 1 1 1 1 1 0 0 0 0 0 ，1 1 1 1 1 1 0 0 0 0 ) ( 1 1 1 0 0 0 0 0 0 0 ，1 1 1 1 1 1 1 0 0 0 ) ( 1 1 1 1 1 0 0 0 0 0 。1 1 1 1 1 1 1 l o o ) ( 1 0 0 0 0 0 0 0 0 0 ，1 1 1 1 1 1 1 1 1 1 ) ( 1 1 0 0 0 0 0 0 0 0 ，1 1 1 1 1 1 1 1 0 0 ) 可以看出，由于b i t m a p 是通过对点位置的排序所决定的，所以b i t m a p 不支持轮廓 查询的更新，也不适合动态的数据集，并且位图法的效率依赖于位图操作的速度。这个 轮廓的计算是昂贵的，因为对于每一个要检测的数据点，必须检索所有点的位图信息来 得到对应位。如果不同值的数目非常大，那么空间代价可能会很高 2 6 】。 2 1 5b t r e e 索引轮廓查询 b t r e e 索引2 7 , 2 8 1 是数据库中存取和查找文件( 称为记录或键值) 的一种方法。b - t r e e 算 法减少定位记录时所经历的中间过程，从而加快存取速度。一个b t r e e 的典型例子就是 硬盘中的结点。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬 盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二 元树相比，b - t r e e 利用多个分支( 称为子树) 的结点，减少获取记录时所经历的结点数， 一1 2 一 东北大学硕士学位论文 第 从而达到节省存取时间的目的。 使用b 树的轮廓查询算法，有如下实例：h o t e l 有两个属性：p r i c e 和d i s t a n c e 。分别 对这两个属性进行递增排序，并分别存储在两个列表索引里，同时扫描这两个索引，发 现第一个匹配时即终止，则肯定属于轮廓查询结果集，在两个索引中都低于匹配条件的 肯定不属于轮廓查询结果，其他的可能也可能不属于轮廓结果点【9 l 。 2 1 6r - t r e e 索引轮廓查询 使用r t r e e 的轮廓算法的基本思想：给定一个旅馆h ，无需搜索r 树的可以确定只 包含被h 所统治的旅馆的那些分枝。如果知道一个旅馆( 3 0 5 ，1 0m i l e ) ，那么r 树中位于 ( 4 0 5 ，6 0 $ ) ，( 2 0m i l e ，3 5m i l e ) 的旅馆就无需考虑。对r 树进行深度优先的搜索，利用新 发现的旅馆对r 树进行剪枝。只有r 树包含了轮廓查询子句中的所有属性时才有效。 图2 7 二维空间上的r - t r e e 的例子 f i g 2 7t h ee x a m p l eo fr - t r e ei nt w od i m e n s i o ns p a c e r - t r e e 索引结构是一个长度平衡树，在这里空间数据被分层聚集。r t r e e 也可以被 理解为高维度的b t r e e 。r - t r e e 搜索的关键域是在维度的集合上，关键字的值将被视为 一个盒子，并被坐标轴上的一个区间所限定。这样在r t r e e 上的一个直接入口就叫做限 定盒子( b o u n d i n g b o x ) 。在r t r e e 上的一个入口就是最小限定盒子的一个树结点或者是 个数据点。被最小盒子限定的入口只能在单一的页面上出现。图2 8 就是图2 7 所对 应的r - t r e e 的例子的r t r e e 实现。 一1 3 一 ，m 9 8 7 6 5 4 3 2 1 o 学硕士学位论文第二章相关工作 图2 8 二维空间上的r - t r e e 的例子 f i g 2 8t h ee x a m p l eo fr t r e ei nt w od i m e n s i o ns p a c e 一个d 维空间上一个r - t r e e 里一个直接入口防7 l 夕l 】b ，2 以】x xi x 翻的左 是点( l ，以，以) ；而入口的右上角就是点( 妒l ，妒2 ，以) 。从一个矩形( r - t r e e 到一个点p 的距离被定义为距离点p 和在矩形里的点的最小距离。而从一个给定 个入口的距离被命名为m i n d i s t 。总之，r - t r e e 方法为轮廓查询进行索引策略提供 的帮助【2 5 1 。 使用尺树的轮廓算法：给定一个旅馆h ，我们无需搜索尺树的可以确定只包含被h 所统治的旅馆的那些分枝。如果我们知道一个旅馆( 3 0 5 ，1 0m i l e ) ，那么r 树中位于( 4 0 $ ， 6 0 5 ) ，( 2 0m i l e ，3 5m i l e ) 的旅馆就无需考虑。对r 树进行深度优先的搜索，利用新发现 的旅馆对r 树进行剪枝。只有尺树包含了轮廓查询子句中的所有属性时才有效。 2 1 7 边界区域轮廓查询 边界区域轮廓查询( b b s ) 算法是应用了r t r e e 的索引技术，和最近邻居搜索策略一 样，是返回距离给定区域最相近的点集。 b b s 算法通过把所有候选入口点放在一个堆栈里，直到它没有用处。在堆栈里的( 入 口) 元素是通过它们( 到原点) 的最小属性值来排序的，然后轮廓查询结果点就会像到 原点的最近邻居一样一一产生出来。同时，用一个支配过滤器来减少查询的空间代价。 如果入口的最左下角被已经存在的轮廓查询点所支配，那么它将被删除。对于支配关系 的验证，最初产生的轮廓查询点是被保存在主存的一个列表s 里 2 9 1 。 注意：一个入口点要与轮廓查询集合丁进行2 次支配关