（计算机应用技术专业论文）空间对象的最佳近邻和可视反近邻查询研究.pdf

浙江大学硕士学位论文摘要 摘要 随着移动计算、无线通信以及定位技术的快速发展，大量的应用领域，如交 通、商贸、物流、气象、军事等，积累了巨大的空间数据。人们迫切需要对这些 数据进行各种查询分析以便发现其隐藏的知识或做出正确的决策。空间数据库作 为一种保存空间数据的容器已然成为当代数据库领域中备受关注的前沿方向之 一，而空间对象查询则是空间数据库的重要操作之一。尽管国内外的数据库专家 学者在空间对象查询处理技术方面已经取得了许多可喜的成果，然而随着人们各 种新的查询需求的不断出现，数据库研究者们仍然需要不断地引入新颖的空间对 象查询类型，并提出相应的查询处理方法。 基于此，本文首先引入了最佳距离的概念，提出了最佳近邻( o p t i m a ln e a r e s t n e i g h b o r ) 查询这一新型查询类型。此类查询涉及到两个空间数据集，在此基础 上，提出了三种不同的空间数据查询算法( f p ，r p ，t s ) ；此外为了减少i o 次 数，本文利用重用的技术提出了两个改进算法( 甲，i 沁) ，力求对每个数据对 象所在磁盘只访问一次。其次，首次提出了可视反近邻( r e v e r s ev i s i b l en e a r e s t n e i g h b o r ) 查询及其相应的处理方法。具体来说，在提出基本的处理算法( n r ) 的基础上，为了较大程度上减少内存消耗和c p u 时间，结合t p l 技术，提出了 伪t p l 算法( t r ) 。另外，还给出了可视反近邻查询的两个扩展变体查询空 间对象的受限可视反近邻查询和空间对象的占可视反近邻查询的定义及其相 应的处理方法。 总的来说，本文主要的贡献及创新点包括： 首次提出了最佳近邻查询和可视反近邻查询的概念。作为最近邻查询的变 体，它们在利用空间数据进行决策支持的应用中十分有用。 对最佳近邻查询进行了形式化的定义，提出了最佳距离的度量方法，并将 其作为评价最佳性的标准。 提出了一系列算法用来有效地处理最佳近邻查询和可视反近邻查询。 浙江大学硕士学位论文 摘要 同时利用真实和合成的数据集在不同的设置条件下对本文提出的所有算法 进行了实验，并评价了这些算法在其有效性和延展性方面的性能。 关键词：空间数据库，空间对象，最佳近邻，反近邻，可视，查询处理，算法 浙江大学硕士学位论文a b s t r a c t a b s t r a c t w i t ht h ea d v a n c e si nm o b i l ec o m p u t i n g ，w i r e l e s sc o m m u n i c a t i o n , a n dp o s i t i o n i n g t e c h n o l o g i e s ，m a n ya p p l i c a t i o n s ( s u c ha st r a f f i cc o n t r o l ，b u s i n e s st r a d e ，l o g i s t i c s ， w e a t h e rf o r e c a s t ，d i g i t a lb a t t l e f i e l d ，e t c ) a c c u m u l a t eah u g em a s so fs p a t i a ld a t a i ti s i m p e r a t i v ef o rp e o p l et oa n a l y s et h ed a t a , f i n dt h ei m p l i c i tk n o w l e d g ea n dm a k ear i g h t d i c i s i o n s p a t i a ld a t a b a s eh a sb e c o m eo n eo ft h el e a d i n gp o s i t i o n si nt h ea r e ao f d a t a b a s ea tt h ep r e s e n ta g ea n dh a sr e c e i v e dm o r ea n dm o r ea t t e n t i o n a l t h o u g h n u m e r o u sd a t a b a s es p e c i a l i s t sh a v eb e e ne f f o r to nt h eq u e r yp r o c e s s i n gt e c h n i q u e so n s p a t i a ld a t a b a s ea n do b t a i n e dan u m b e ro fv a l u a b l er e s u l t s ，t h e r ei sag a pf o rs a t i s f y i n g v a r i o u sq u e r yr e q u i r e m e n t so ft h eu s e r sa sw e l la s t h ei n c r e a s i n g l yn e wq u e r y r e q u i r e m e n t s m o t i v a t e db yt h i sp r o b l e m ，i nt h i st h e s i s ，w ei n t r o d u c ean e w c o n c e p tc a l l e d o p t i m a ld i s t a n c e a n dan o v e lq u e r yp r o c e s s i n gt e r m e da s o p t i m a ln e a r e s tn e i g h b o r q u e r y ”w h i c hi n v o l v e st w od a t a s e t s i no r d e rt oa v o i da c c e s s i n gt h en o d e sw h i c ha r e n o tt h ea c t u a lr e s u l t s ，w ep r o p o s et h r e ea l g o r i t h m s ( i n c l u d i n gf p ，r p ，t s ) i n a d d i t i o n ，w eu s et h er e u s i n gt e c h n o l o g ya n dd e v e l o pt w oa d v a n c e da l g o r i t h m s ，n a m e l y r f pa n dr r p 9t od e c r e a s et h ei o f u r t h e r m o r e ，w ef i r s tf o r m u l i z et h er e v e r s ev i s i b l e n e a r e s tn e i g h b o rq u e r ya n dp r e s e n ts e v e r a la l g o r i t h m st oh a n d l ei t i np a r t i c u l a r , w e s o v e li tr e s p e c t i v e l y 、i t hn a i v e - r v n ns e a r c h ( n r ) a n dt p l r v n ns e a r c h ( t r ) w h i c hu s e st h et p l t e c h n o l o g yt or e d u c et h em e m o r ys p a c ec o n s u m p t i o na n dt h ec p u t i m e i na d d i t i o n ，c o n s t r a i n e dr e v e r s ev i s i b l en e a r e s tn e i g h b o ra n d6r e v e r s ev i s i b l e n e a r e s tn e i g h b o ra r ep r o p o s e d 、加mt h e i rp r o c e s s i n gm e t h o d s f o re a c ho ft h et w o k i n d so fn o v e lq u e r y , a i le x t e n s i v ee x p e r i m e n t a ls t u d yw i t hb o t hr e a la n ds y n t h e t i c d a t a s e t sd e m o n s t r a t e st h ep e r f o r m a n c ep r o p e r t i e so ft h ep r o p o s e da l g o r i t h m si nt e r m s o fe f f i c i e n c ya n ds c a l a b i l i t y t os u mu p ，0 1 1 1 k e yc o n t r i b u t i o n si nt h i st h e s i sa r ea sf o l l o w s ： w ei n t r o d u c et h en o t i o no fo n n q u e r ya n dr v n nq u e r y , t w oa l t e r n a t i v ef o r m s o fn ns e a r c h ，w h i c ha r eu s e f u lt y p e so fq u e r i e si nm a n yp r a c t i c a la p p l i c a t i o n s i i i 浙江大学硕士学位论文 a b s t r a c t i n v o l v i n gs p a t i a ld a t af o rd e c i s i o nm a k i n g w ef o r m a l i z et h eo n n q u e r i e sa n dd e v e l o pt h eo p t i m a l i t ym e t r i ct h a ts e lv e sa s t h es t a n d a r df o ro p t i m a l i t ye v a l u a t i o n w e p r o p o s es e v e r a la l g o r i t h m s t op r o c e s so n na n dr v n n q u e r i e se f f i c i e n t l y w ec o n d u c te x t e n s i v ee x p e r i m e n t sw i n lr e a la n ds y n t h e t i cd a t a s e t su n d e ra v a r i e t yo fs e t t i n g s ，t od e m o n s t r a t et h ep e r f o r m a n c ep r o p e r t i e so fo u rp r o p o s e d a l g o r i t h m si nt e r m so fe f f i c i e n c ya n ds c a l a b i l i t y k e y w o r d s ：s p a t i a ld a t a s e t ，s p a t i a lo b j e c t ，o p t i m a ln e a r e s tn e i g h b o r , r e v e r s en e a r e s t n e i g h b o r , v i s i b l e ，q u e r yp r o c e s s i n g ，a l g o r i t h m 浙江大学硕士学位论文表目录 表目录 表3 1o n n 算法常用符号1 2 表3 2o n n 实验的真实数据集的描述2 8 表3 3o n n 实验参数范围及默认值2 8 表4 1r v n n 算法中障碍的数据结构4 l 表4 2r 1 删v s 摄w n n 5 2 表4 3r 呵n 相关算法的参数范围及默认值5 4 浙江大学硕士学位论文 图目录 图目录 图3 1 一个o n n 查询的例子。1 l 图3 2 范围近邻查询和点近邻查询的例子1 5 图3 3 真实距离的作用2 0 图3 4 例2 的示图。2 2 图3 5t s 的第三阶段优化。2 4 图3 6 五种o n n 算法随着k 变化的性能变化3 0 图3 7 五种o n n 算法随着以变化的性能变化3 l 图3 8 五种o n n 算法随着尺变化的性能变化3 2 图3 9 五种o n n 算法随着维数变化的性能变化( 均匀分布) 3 3 图3 1 0 五种o n n 算法随着, 变化的性能变化3 4 图3 1 1 五种o n n 算法随着撕变化的性能变化( 均匀分布) 。3 5 图4 1 一个简单的例子3 8 图4 2t p l 裁剪技术( 无障碍) 3 9 图4 3 障碍集及其对对应的尺树4 2 图4 4q - i n v i s i b l e 4 2 图4 5 分割，4 2 图4 6 视点g 对点p 的可见度4 3 图4 7 视点口对线段e 的可见度4 4 图4 8g 对m b r 部分可视4 4 图4 9 障碍集数据集及它对应的r 树4 6 图4 1 0 p 与p 之间存在障碍o 4 7 图4 11t r 与n r 的比较5 5 图4 1 2 陋 v l o l 变化时t r 总时间的变化趋势5 6 图4 1 3 切变化时t r 总时间的变化趋势5 7 i v 浙江大学硕士学位论文 图目录 图4 1 4i p i i o l 变化时c - t r 总时间的变化趋势5 8 图4 1 5c 变化时c - t r 总时间的变化趋势5 9 图4 1 6 切变化时c - t r 总时间的变化趋势6 0 图4 1 7l p i i o l 变化时甜r 总时间的变化趋势。6 l 图4 1 8 万距离变化时参t r 总时间的变化趋势6 2 图4 1 9 如变化时& t r 总时间的变化趋势6 3 v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：弓长繇 签字日期：沙口岳年 易月7 日 学位论文版权使用授权书 本学位论文作者完全了解迸姿盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝鋈盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：弓长豳 签字同期： 沙扩g 年莎月7 日 导师签名： 签字日期：沙3 年月7 日 浙江大学硕士学位论文第1 章绪论 1 1 研究背景及意义 第1 章绪论 空间数据库是当代数据库领域中备受关注的前沿方向之一，它主要用于存储 和管理空间中各类静止对象的位置或形状。空间数据库的研究内容相当丰富，主 要涉及空间对象的表达、建模、索引和查询等。 由于空间数据库在地理信息系统、多媒体应用、智能交通、导航系统、生态 环境系统、数字战场等方面具有广泛的应用前景和潜在的经济价值，从而激发了 世界上广大科研工作者及有关商家的浓厚兴趣。例如，o r a c l e 定位器( l o c a t o r ) 和o r a c l e 空间在o r a c l e9 i 数据库系统中提供了对基于位置查询的支持【l l 。当前国 际上一些权威期刊( 如i e e et k d e ，i e e et r a n s a c t i o n so nk n o w l e d g ea n dd a t a e n g i n e e r i n g ) 和国际著名学术会议( 如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 a e n g i n e e r i n g ) 也都将空间数据库研究作为主体内容之一，为该领域的广大研究人 员提供了广泛的交流机会。 空间对象查询是空间数据库的重要操作之一。同时，空间数据库的查询效率 是衡量空间数据库性能的重要指标。目前，存储和管理实际生活中的空间对象已 成为了现实。在许多应用领域中，用户需要有效地查询各种空间数据。然而空间 数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地 发挥作用，进而更不能满足于用户新的查询需求，所以研究新的查询处理技术来 有效地支持各种空间对象的查询问题( 包括新提出的查询问题) 变得更加重要了。 基于上述背景，本文提出并研究和探讨了空间数据库中一些新的查询类型及 其相应的处理技术，其意义在于： ( 1 )丰富我国在空间数据库查询处理技术方面的研究成果 在国外，有众多的研究机构、大学和企业进行空间对象查询处理技术的研究， 并取得了大量的研究成果。但在国内，目前开展该领域研究的单位并不多，主要 浙江大学硕士学位论文第1 章绪论 集中在中科院部分研究所( 如软件所) 和几所大学，如北京大学、中国人民大学、 复旦大学、上海交通大学等。因此开展空间数据库查询处理技术的研究，对于丰 富我国在该领域的研究成果，促进空间数据库的实际应用具有重要的理论和实践 意义。 ( 2 )空间数据库查询处理技术的研究有着广阔的应用前景 随着移动计算、无线通信以及定位技术的快速发展，大量的应用领域，如交 通、商贸、物流、气象、军事等，积累了巨大的空间数据。人们迫切需要对这些 数据进行各种查询分析以发现其隐藏的知识或做出正确的决策。所以，作为空间 数据挖掘应用和决策支持应用开发的核心部件，空间数据库查询处理技术的应用 前景将是不可低估的。 ( 3 )推动空间数据库的实用化进程 目前还没有完全支持空间应用的真正意义上的空间数据库系统，仅有一些实 验用的原型系统。为此，适时开展空间数据库查询处理关键技术的研究是有意义 而且必要的。它不但可以推动空间数据库的实用化进程，而且还可以为将来真正 实现空间数据库管理系统奠定基础。 1 2 相关研究及存在的问题 目前，常见的一些空间查询类型主要有： ( 1 ) 点查询：给定一个查询点g ，在所给空间数据集内查找所有与之重 叠的空间数据对象。 ( 2 ) 区域查询【6 8 - 7 1 】：这是一种常用的拓扑查询，它指的是给定一个查询 区域月，在所给空间数据集内查找所有被它覆盖的空间数据对象。 ( 3 )最近邻查询 2 - 8 1 ：这是最为重要的空间查询类型之一，它是为了在 所给数据集内找到距离查询点q 最近的那个数据对象而被提出来的。 ( 4 ) 反最近邻居查询【1 2 。3 0 】：它是最近邻查询的变体之一。它的定义是： “给定一个查询点g 和一个距离度量( 如欧几里得距离等) ，一个反最近 邻查询找出所有将g 作为其最近邻居的空间数据对象”。 2 浙江大学硕士学位论文 第l 章绪论 国内外的数据库专家学者在以上空间对象查询处理技术方面已经取得了许 多可喜的成果。但也存在一些不足之处，尽管一些查询变体不断被提出，如对于 最近邻查询而言，有连续的最近邻查询【3 9 ，加1 ，受限的最近邻查询l 蚓和可视最近邻 查询【9 l 等，研究者越来越从用户的角度出发，考虑人们的需求。然而，这些距离 满足人们不断出现的、复杂而多样的查询需求还有一定的差距，有待相关研究进 一步的深入，其中存在的一个问题就是：缺少满足新型应用需求的空间对象查询 类型及其处理技术。 新的查询需求的不断出现迫切需要数据库研究者们不断地引入新颖的空间 对象查询类型，并提出相应有效的查询处理方法，从而满足人们日益增长的多样 化的查询需求。譬如，在涉及空间对象数据的许多应用( 如数据挖掘、决策支持 等) 中，人们可能想要查找相对于某个对象而言它的最佳近邻，以便他们发现这 些数据背后隐藏的知识或做出正确的决策。这一应用例子就孕育了一种可称之为 “最佳近邻查询”的空间对象查询类型。本文主要阐述了两种新颖的空间对象查询 类型，即最佳近邻查询和可视反近邻查询，并分别给出了有效的查询处理方法。 最佳近邻查询可以认为是最近邻查询( n n ) 或是距离连接查询的一种变体， 但与它们又是决然不同的：( 1 ) n n 查询一般只涉及到查询点和一个数据集，而 最佳近邻查询必须同时考虑两个数据集；( 2 ) n n 查询的每一次查询都是独立的， 也就是说通过查询点q j 搜索到的结果与另一个查询点9 2 是无关的，而最佳近邻 查询中，是将对观察集的任何一点变动，都可能会影响到结果，可以说它更侧重 于宏观性。( 3 ) 尽管距离连接查询也是设计到两个数据集，但是每对结果之间是 相互独立的，不存在最佳近邻查询中的排序性。正因为最佳近邻查询具有以上的 特点，它的查询也会更加复杂，需要进一步研究。 与可视近邻( 州) 查询和障碍近邻( o n n ) 查询一样，可视反近邻查询也 是因为障碍的引入而被提出来的。v n n 查询需要进行可视性的判断，但是它只需 要考虑当前一个查询点的可视范围就可以了。而可视反近邻查询必须同时考虑当 前查询点和不可估计数量的目标对象的可视范围，这就增加了问题的复杂性，也 是研究的难点所在。 浙江大学硕士学位论文第1 章绪论 1 3 本文研究目标和研究内容 1 3 1 研究目标 本文的研究目标是：在已有的空间数据库查询处理技术研究的基础上，结合 空间对象的海量性和复杂性的特点，以最小化i 0 ( 即结点访问量) 和c p u 代价 为优化目标，展开一系列能够满足实际应用需要的空间对象的查询处理技术研 究，提出高效的查询处理算法，并通过实验和理论分析的手段全面地评价和比较 算法的性能。 1 3 2 研究内容 针对当前研究中存在的问题和本文提出的研究目标，本文拟开展以下方面内 容的研究： ( 1 ) 空间对象的最佳近邻查询 给出两个多维的数据集坊和仇，一个空间区域足和一个临界距离以，空间 对象的最佳近邻查询( o _ p t i m a l - n e a r e s t - n e i g h b o r , o n n ) 要求在尺周围找到仍中的 一个对象，且使这个对象具有最大的最佳性。为了阐述它，本文在以下章节中将 对o n n 查询进行形式化的定义并详细说明最佳距离的由来，同时依次提出五个 处理这类查询的算法，最后通过实验阐述这些算法各自在性能方面的有效性和延 展性。 ( 2 ) 空间对象的可视反近邻查询 给定一个数据集尸及查询点g ，在存在障碍集o 的情况下，空间对象的可视 反近邻查询( r e v e r s ex i s i b l en e a r e s tn e i g h b o r , r v n n ) 是为了在所给的数据集p 中 找到这样的一些点p ，使它们均是将g 作为它们的可视最近邻。为了说明它，本 文将介绍相关查询，同时对r v n n 进行形式化的定义，在最基本算法的基础上， 利用t p l ( yt a o ，d p a p a d i a s ，a n dx l i a n ) 技术尽可能对访问结点进行裁剪，减 少磁盘访问量，提出伪t p l 算法，提高性能。同时，本文也对此类查询进行了扩 展，提出了它的两个查询变体及其相应的处理方法。针对这些算法，本文将通过 4 浙江大学硕士学位论文第1 章绪论 大量实验证明它们各自的性能。 1 4 本文结构组织 本文总共分五章，第1 章为绪论，第5 章为总结与展望，第2 章至第4 章为 本文研究内容。 第l 章介绍本文的研究背景及意义，给出当前研究存在的问题，提出本文的 研究目标和研究内容。 第2 章介绍空间查询处理中主要的两类查询( 空间近邻查询和空间反近邻查 询) 的研究现状。 第3 章主要研究了空间最佳近邻查询，从不同的角度提出不同的算法进行处 理。为了减少i o 代价运用重用技术进行算法改进，通过实验证明这些算法各自 的性能，进而分析了其主要影响因素。 第4 章主要研究空间可视反近邻查询，并提出两个算法进行处理，同时通过 实验对它们各自的性能进行评估。其后研究两个变体查询( 空间对象的受限可视 反近邻查询和空间对象的巧可视反近邻查询) 及它们的处理方法。 第5 章总结本文完成的主要研究工作及成果，描述本文的主要创新点和贡献， 最后指出在此基础上可以进一步研究的内容。 浙江大学硕士学位论文 第2 章空间对象的查询处理研究综述 第2 章空间对象的查询处理研究综述 目前，空间对象的查询处理中有两大类查询被广泛关注：空间近邻查询和空 间反近邻查询。下面，将首先具体地分析国内外的研究学者在这两方面的研究工 作。 2 1 空间近邻查询 基于r 树及其变体的最近邻查询处理技术是空间数据库领域的一个研究重点 与热点。目前，大量的最近邻查询算法已经被提出。根据查询对象和数据对象的 属性( 包括静态和移动) ，现有的算法主要可以划分为如下三大类：1 ) 静态对象 的静态最近邻查询；2 ) 静态对象的移动最近邻查询；3 ) 移动对象的移动最近邻 查询。其中第一类查询被广泛地研究，对此，已有的算法主要遵循深度优先遍历 ( d e p t h - _ f i r s t ，d f ) f 2 ，3 域最佳优先遍历( _ b e s t _ f i r s t ，b f ) 1 4 5 1 。r o u s s o p o u l o s 等人 6 1 首次提出了一种基于d f 的最近邻查询算法。该算法是对一种基于k d 树的最近 邻查询算法的改进。为了在算法执行过程中实现排序和剪枝，文献【6 】又提出了两 个距离度量( 即m i n d i s t 与m i n m a x d i s t ) 以及相应的三种剪枝策略。但是，文献 7 】 证明了基于d f 的最近邻查询算法的i o 代价不是最佳的，即它存在一些不必要 的i o 开销。 基于b f 的最近邻查询算法最小化i o 代价。同时它还能够以查询点与最近 邻居之间的距离增量地返回最近邻居。h j a l t a s o n 和s a m e t l 4 首次将这种思想引入 到空间数据库中，并提出了算法来排序空间对象。该算法是在一棵p m r 四叉树 上实现，并且使用了一个优先队列。h e 耐c h 【8 】也提出了一个可以应用于l s d 树的 类似方法，但是该方法却使用了两个优先队列。随后，h j a l t a s o n 和s a m e t 5 】将他 们在文献 4 】中所提出的算法应用到r 树上，并且用大量的实验证明了基于b f 的 最近邻查询处理方法在f o 和c p u 代价方面要大大地胜过基于d f 的最近邻查询 6 浙江大学硕士学位论文第2 章空间对象的查询处理研究综述 处理方法。 目前，除了前述传统的最近邻查询之外，大量的最近邻查询变体也已经被提 出并研究，诸如逆最近邻查询b 2 , 1 s 2 5 舶刀 2 s 2 9 捌( r e v e r s en ns e a r c h ) ，带约束的最 近邻查询( c o n s 打a i n e dn ns e a r c h ) 【3 6 1 ，连续的最近邻查询【3 9 删( c o n t i n u o u sn n s e a r c h ) ，分组最近邻查询 3 4 1 ( g r o u p n n s e a r c h ) ，聚集最近邻查询【3 5 】( a g g r e g a t en n s e a r c h ) ，全最近邻查询f 4 1 1 ( a l ln ns e a r c h ) ，范围最近邻查询【3 7 】( r a n g en ns e a r c h ) ， 面最近邻查询【3 5 1 ( s u r f a c e n ns e a r c h ) ，等等。各种查询类型的研究主要以最小化 c p u 及i o 代价为目标，提出各种剪裁策略，使达到有效进行查询处理的最终目 的。 尽管国内外学者对传统的空间近邻查询及其变体作了大量的研究，但是可以 看到这些查询大都是从对象出发，仅仅考虑的是距离的远近。虽然这些查询都是 针对实际应用提出的，但却没有真正的考虑用户的喜好问题。因此，引入最佳距 离，并进一步研究最佳近邻查询是有开创意义的。 2 2 空间反近邻查询 自从反最近邻查询被k o m 和m u t h u k r i s h n a n 1 2 1 首次提出以来，它已经受到了 数据库界的广泛关注，因为它在诸如决策支持、资源配置、数据挖掘以及基于剖 面的市场( p r o f i l e b a s e dm a r k e t i n g ) 分析等领域中有着重要的应用价值。 早先的算法1 1 2 - 1 5 1 都是基于预处理的。具体地说，对每个数据点p ，预先计算 出它与数据集合中的最近邻居之间的距离，用d n n 表示；接着，通过检查给定的 查询点留是否落在以p 为圆心以d n n 为半径的圆内就可以很容易地判断出p 是否 是一个留的反最近邻居。但是，此方法的缺点是需要花费昂贵的代价来保存每个 数据点或结点( 即m b r ) 的d n n 。 随后，一系列不需要进行预处理的反最近邻查询处理方法在近来的数据库文 献中被提出。这样的算法首先由s t a n o i 等人【1 6 1 提出，它采用了两阶段的处理技术： ( i ) 将g 周围的二维空间划分成6 个相等的区域，并且从中找到6 个受限的最近 7 浙江大学硕士学位论文第2 章空间对象的查询处理研究综述 邻居作为最终查询结果的候选点集合；( i i ) 判断每个候选点是否为真正的反最近 邻居。但不幸的是，这种方法只适用于二维空间，而不适用于高维( 3 ) 空间。 后来，s i n g h 等人【1 7 1 提出了一种多步骤的反最近邻查询算法。但是，它却可能产 生遗漏，即不能保证找到所有的查询结果。为了避免前述反最近邻查询处理方法 的缺陷，t a o 等人【1 8 】提出了一种称之为t p l 的反最近邻查询处理方法。迄今为止， t p l 是种在欧几里德空间中对静态数据集合进行反最近邻查询处理的最为有效 的方法。同时，t p l 不仅适应于任意维空间，而且也可以处理反七( 1 ) 最近邻 查询问题。最近，t a o 等人1 1 9 1 又探讨了连续反k 最近邻查询问题，并给出了相应 的查询处理方法。 另外，许多的反最近邻查询问题的变体也已经被研究。b e n e t i s 等人 2 0 - 2 1 】系统 地讨论了移动对象的反七最近邻查询问题。s t a n o i 等人【2 2 】探讨了双色( b i c h r o m a t i c ) 反最近邻查询问题。k o m 等人【2 3 】研究了数据流的聚集反最近邻查询问题。x i a 等 人【矧提出了一种基于估算的反k 最近邻查询算法。最近，y i u 等人 2 5 - 2 6 】先后探讨 了在大图像和a d h o c 子空间上的反最近邻查询处理方法。x i a 和z h a n g 2 7 】讨论了 连续反最近邻查询监控的问题。t a o 等人【2 8 】和a c h t e r t 等人【2 9 】各自研究了度量空间 ( m e t r i cs p a c e ) 上的反最近邻查询问题。k a n g 等人i 3 0 l 探讨了连续单色 ( m o n o c h r o m a t i c ) 反最近邻和连续双色反最近邻的查询处理方法。 尽管国内外的研究学者对本课题的研究已有了一定的进展，但是这些研究还 没有涉及一些符合实际应用需要的、新颖的查询问题，如在现实生活中障碍是随 处可见的，没有障碍的理想状态一般是不会出现的。因此在这样的研究背景下， 进行可视反近邻查询问题的处理技术研究是有意义而且必要的。 2 3 本章小结 在本章中，主要介绍了空间对象查询处理中的近邻查询问题和反最近邻查询 问题，概括了最近一些年来国内外研究学者在这些查询中的研究成果和主要贡 献，并分别描述了这两大类查询的特点以及相关研究进展。通过对这些查询的介 8 浙江大学硕士学位论文第2 章空间对象的查询处理研究综述 绍，为接下来的最佳近邻查询和可视反近邻查询的研究提供了一些准备知识。 9 浙江大学硕士学位论文 第3 章空间对象的最佳近邻查询 3 1 引言 第3 章空间对象的最佳近邻查询 最近邻( n n ) 查询是空间数据库中最为普遍的查询类型之一。它的一个最常 见的扩展是k 最近邻( k n n ) 查询。给出一个多维的数据集d 和一个查询点q ， k n n 查询返回数据集d 中的一个七元子集，其中的元素都是离q 最近的。形式化 地可以表示为k n n ( g ) = 舻pi - - , 3p d p s u c ht h a td i s tp ，d c a r ( s o ，0 9 ，或者( 2 ) 当c a r ( s o ，0 ) = c a r ( s o ，0 9 时，& 中所有对 象到o 的加权距离和小于，中所有对象到o 的加权距离和。图3 1 显示了一个 o n n 查询，其中每个黑色点b j ( 1 ，s 6 ) 都带有一个以自身为圆心，以以为半 径的的圆。在这个图中，用口，a 2 ，a 1 5 标识的灰色点表示数据集坊，用b ，b 2 ， l o 浙江大学硕士学位论文第3 章空间对象的最佳近邻查询 b 9 标识的黑色点表示另一个数据集d b 。在这种情况下的最佳近邻( o n n ) 是b ， 因为b j 所带的圆包含了两个仍中的点( 即a 3 ，a 4 ) ，同时在权值均取1 的情况 下( d i s t ( a 4 ，6 ，) + d i s t ( a 3 ，6 ，” o ，这是因为iri ls i ；( i i ) o 三鲻锗爱等 易表示，当且仅当o p t t , y 冠讲t o p k 妇y ( 初始化为) 是否成立。如果成立，意味着e 的评价值劣于融， 则这次迭代可以停止( 第9 行) ；否则，开始评价e 。接着，f p 利用相应的忍由 公式1 ( 在第2 节提出的) 计算得到e 的最佳性o p t e ( 第l o 行) 。若o p t e lrl ( 意味着协中有元素) 并且h r a t u s e d k ，则f p 将e 插入砒f ，并在h r s t t u s e d = k 时将h r , u t o p k k e y 设置为哆k e y 。若0 p 疋 lrl 并且h i n t u s e d = k ，则f p 首 先判断o p t e 巩，r t o p k k e yt h e n 9 ：c o n t i n u e c o m p u t ee so p t i m a l i t yo p t eu s i n ge q u a t i o n1 i f o e t , lr i t h e n 谴h b i i u s e d kt h e n i n s e r t ( p ，o t t e ) i n t oe 神 诅h | 1 u s e d = k t h e n h 蛳t o p k k e y = p 鼬脚 e b e i fo p 疋 n r s l t t o p k k e yt h e n r e m o v et h et o p 咖廿妇t ，萨恼t ，k e y ) f r o mh n i n s e r t ( 己d p 疋) i n t o 珥曲 h 姗t o p k k e y = 寸b t k e ) r e t n r nh n f u n c t i o nf i n d 小烈s i n a ( 乃，功，冠以，月：4 ) l ：i n i t i a l i z eas t a c ks t = a c c e p t i n ge n t r i e so f t h ef o r m ( p ，k e y ) 2 ：p u s h ( t a r o o t , 0 1i n t os t 3 ：w h i l e s t d o 4：pop t h et o pe n t r y ( p ，k e y ) f r o ms t 5 ：i f pi sa p o i n tt h e n 6 ：i f 0 d i s t ( p ，6 ，) 以t h e n 7 ： i n s e r t ( p ，d i s t ( p ，岛) ) i n t oh a 8 ：e l s eei sa l li n t e r m e d i a t en o d e 9 ：f a r e a c hc h i l de n t r ye e d o 10 ：i fe 。i n t e r s e c t srt h e n 11：truncate e lt og e tp o r t i o ne f t h a ti se n c l o s e db yr 1 2 ：i f 0 m i n d i s t ( 白：6 ，) 以t h e n 13 ：p u s h ( p f ：m i n d i s t ( p - b g ) i n t os t 当前被评价的候选点( 如b ) 与e 的m b r 和尺相交的部分之间的真实距离( e x a c t d i s t a n c e ) 。图3 3 显示了这个真实距离的作用，其中b j ( 黑色点) 是要被评价的 点，r 是一个空间区域，e j 是被访问的非叶子结点，e j 是e 的m b r 与r 重叠的 部分。如图3 3 所示，b ，到e ，的最短距离小于以，而b j 到e f 的最短距离大于喀。 也就是说，e ，实际上是一个无用的结点，利用真实距离可以将它排除。 1 9 m n 佗b h b硌d加扒 浙江大学硕士学位论文第3 章空间对象的最佳近邻查询 图3 3 真实距离的作用 倒1 。应用f p 算法( 脱) 对图3 1 中的数据集玩和现进行处理，点6 ，幻， b 3 ，b 彳，b s 和玩首先作为候选点被找到并存储在冠b 中。接着f p 有选择地递归地 评价每个b j ( 1s 歹6 ) 。在这里，f p 只评价b l 和6 2 ，并把它们插入。而6 如 b 一， 如和玩不需要进行评价，因为它们很显然劣于h ，, i t t o p k k e y = o p t b 2 。最后 算法将玩，= b l ，b 2 作为2 - o n n s 的结果返回。 3 4 2 反向处理算法 上述的f p 算法在i o 和c p u 上有极大的耗费，因为它为了评价所有的候选 点需要多次遍历树乃。此外，它在算法的第一阶段可能访问一些不必要的结点。 例如例l 中的b 6 就是这样的一个点，可以发现在以b 6 为圆心以以为半径的圆中 没有包含任何的位于足中的仇中的点。为了避免这种情况的发生，提出了第二 个算法反向处理方法一p ( 在算法2 中给出了伪代码) 。 首先，r p 通过遍历乃找到所有落于r 中的点并将它们保存在一个小堆z 易 ( 第3 行) 。注意到这里堆排序使用的键值是很重要的，因为如果两个接连访问 的点( 在第6 行中作为查询点) 彼此相邻，则在进行第二个查询时大部分需要的 页面可以由第一次查询处理写入l r u 缓存中，进而减少o 次数。为了达到这个 目标，r p 令兄中的点按它们的希尔伯特值( h i l b e r t ) 排序，这样对它们进行处 理时可以达到最大的空间本地化。一旦阮得到后，对每个玩中的点e ，r p 首先 调用函数f i n d - n n s i n - b 遍历找到那些落于尺周围的并且与e 的距离小于以的 浙江大学硕士学位论文第3 章空间对