（计算机软件与理论专业论文）道路网络中的多对象最近邻查询研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：亟垫丝日期：迪丑! s ： 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：亘啦导师签名：3 司_ 睦乏笙 道路网络中的多对象最近邻查询研究 摘要 多对象最近邻查询( 甜ln e a r e s tn e i g h b o r sq u e r y ) f 1 在地理信息系统、城市规 划和资源分配等领域有广泛的实际应用，也可作为模式识别和分类【2 】、某些聚 类算法或应用的核心模块【3 ，4 ，5 】。道路网络在实际生活中广泛存在，但是至今为 止，道路网络环境中的多对象最近邻查询问题还没得到很好的解决：一方面，针 对欧氏空间的查询处理算法不能直接适用于道路网络环境：另一方面，通过重复 调用道路网络环境下的最近邻查询算法来进行多对象最近邻查询处理的计算代 价较大。我们利用m 树 6 】对道路网络中的边建立索引结构，基于该索引，提出 了一个新颖的多对象最近邻查询处理算法b a n n s ( b a t e h e da l ln e a r e s tn e i g h b o r s s e a r c h ) a l 、定义道路网络中边与边之间的m a x d 距离，其实际意义为：在道路网络 中，从一条边的任意一个端点出发，到达另条边的某个端点所经过的道路网络 距离一定不超过m a x d 距离。 2 、利用m 树【6 】为道路网络环境中的边建立索引结构。基于该索引结构，我 们提出了b a n n s 算法，采用了批处理的基本思想来处理道路网络中的多对象最 近邻查询。 3 、为了给实际应用提供更多的信息，我们对b a n n s 算法进行了扩展，使 b a k n n s 算法能查询空间对象集合b 中a 集合元素的多个最近邻。 4 、分别使用人造道路网络和真实道路网络数据，验证了b a n n s 和b a k n n s 算法的性能。实验结果显示b a n n s 和b a k n n s 性能稳定、高效：当空间对象 集合a 较大时，b a n n s 算法具有更好的性能；对于b a k n n s 算法来说，随着k 的增加，可以适当增大m 树的扇出值。 综上，我们研究了道路网络中的多对象最近邻查询问题，提出一个新颖的查 询处理算法b a n n s ，并对萁进行了扩展。b a n n s 算法对于空间对象集合a 和 b 都不要求其本身带有任何索引结构，并能稳定、高效地进行查询处理。 关键词：多对象最近邻查询，道路网络 道路网络中的多对象最近邻查询研究 a b s t r a c t g i v e nt w os e t so fs p a t i a lo b j e c t s aa n db ，a l ln e a r e s tn e i g h b o r sq u e r y 1 1r e t r i e v e s f o re a c ho b j e c ti nai t sn e a r e s tn e i g h b o ri nb i th a sw i d ea p p l i c a t i o ni nc i t yp l a n n i n g , g i s e t c i tc a r la l s oa c ta st h ec o r em o d u l ef o rs o m ec l u s t e r i n ga l g o r i t h m so r 印p l i c a t i o r t s 【2 ，3 ，4 ，a n d5 】c u r r e n tw o r kw h i c hf o c u s e so ne u c l i d e a ns p a c e sc a l l tb e a p p l i e dt or o a dn e t w o r ke n v i r o n m e n t ；w h i l er e p e a t e d l yu s i n gn e a r e s tn e i g h b o rq u e r y a l g o r i t h mi nr o a dn e t w o r kw o u l dc a u s el a r g ec o m p u t a t i o nc o s t w es t u d yt h ei m a r e s t i n gp r o b l e mo fa l ln e u e s tn e i g h b o r sq u e r yi nr o a dn e t w o r k e n v i r o m n e n t , p r o p o s eb a n n s ( b a t c h e , da l ln e a r e s tn e i g h b o r ss e a r c h ) a l g o r i t h mf o r f a s ta n da c c u r a t ea l ln e a r e s tn e i g h b o r sq u e r yp r o c e s s i n gi r ir o a dn e t w o r k s 1 w ed e f i n em a x dd i s t a n c eb e t w e e ne d g e si nar o a dn e t w o r k i i lar o a d n e t w o r lt h er o a dn e t w o r kd i s t a n c eb m w e e nt w on o d e sw o n te x c e e dm a x d d i s t a n c eb e t w e e nt h e i re x i s t i n ge d g e sw ep r o v et h a t ：m a x dd i s t a n c ei s m e t r i cd i s t a n c e 2b a s e d0 1 1m a x dd i s t a n c e , w ei n d e xa 1 1t h ee d g e si nr o a dn e t w o r kb ya n m - t r e e 【6 1 ，b a n n sd o e sn o tr e q u i r ea n ye x i s t i n gi n d e xo us p a t i a lo b j e c ts e t a a n d b 3 i no u re x p e r i m e n t s ，w ec o m p a r eb a n n sw i t hb a s i cm e t h o dw h i c h r e p e a t e d l ys e a r c h e sf o re a c ho b j e c ti i lai t sn e a r e s tn e i g h b o ri nb n l er e s u l t s s h o wt h a tw h e nt h ec a r d i n a l i t yo fs e tai sb i g g e rt h a nt h a to fs e t 口b a n n s p e r f o r m sm u c hb e t t e r 4 w ea l s oe x t e n db a n n st op r o c e s sa l l k n e a r e s t n e i g h b o rq u e r i e sw h i c h m p l i s g i v e nt w os e t so fs p a t i a lo b j e c t sa ，b ，f i n de a c ho b j e c ti nai t sk n e a r e s tn e i g h b o r si nb t h r o u g he x t e n s i v ee x p e r i m e n t s ，w ev a l i d a t ef o ra l ln e a r e s tn e i g h b o r ss e a r c hi n r e a dn e t w o r ke n v i r o n m e n t ，b a n n si saf a s ta n da c c u r a t ew a y k e y w o r d ：a l ln e a r e s tn e i g h b o r sq u e r y ；r o a dn e t w o r k 2 道路网络中的多对象最近邻查询研究 1 1 背景介绍 第一章引言 在人类的生活和生产过程中，存在着大量与空间位置有关的信息。随着地理 信息系统、相关定位设备、计算机辅助设计、卫星图像数据处理、空间数据库等 领域技术的发展，对空间数据查询问题的研究近年来倍受关注。近年来，各大公 司纷纷推出了自己的空间数据引擎，如e s r i 公司的s d e ( s p a t i a ld a t a b a s e e n 垂n e e r ，空间数据库引擎) 、o r a c l e 公司的s p a t i a l 空间数据库组件、i n f o r m i x 公司推出的空间数据刀片( i b mi n f o r m i xs p a t i a ld a t a b l a d em o d u l e ) 、i b m 推出 的d b 2 空间扩充器( i b md b 2s p a t i a le x t e n d e r ) 、北京超图公司开发的 s u p e r m a p s d x + 海量空间数据管理引擎等等。当年国际上一些权威期刊如v l d b j ( i n t e m a l i o n a lj o u m a lo nv e r yl a r g ed a t ab a s e s ) 、t k d e ( i e e et r a n s a c t i o n so n k n o w l e d g ea n dd a t ae n g i n e e r i n g ) 和重要学术会议a c ms i g m o d ( p r o c e e d i n g so f t h ea c mc o n f e r e n c eo nt h em a n a g e m e n to fd m a ) 、i c d e ( i m e m 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 ) 、v l d b ( i n t e m a t i o n a lc o n f e r e n c eo i lv e r yl a r g ed a t ab a s e s ) 、 s t d b m ( w o r k s h o po ns p a t i o - t e m p o r a ld a t a b a s em a n a g e m e n t ) 、e d b t ( p r o c e e d i n g s o f 1 e i n t e r n a t i o n a lc o n f e r e n c e o 1 _ e x t e n d i n g d a t a b a s e t e c h n o l o g y ) 等将对空间数据 查询的研究作为主题内容之一，为该领域的广大研究人员提供了更多的交流机 会。 最近邻查询【7 】是典型的空间数据查询问题之一，其定义为给定一个查询对 象，在一个数据集合中查找距离查询对象最近的一个或多个对象。 多对象最近邻查询( a t ln e a r e s tn e i g h b o r sq u a , y ) 1 是最近邻查询的一个扩 展，其定义为给定两个空间对象集合a 、b ，为4 中所有的对象查找在口中的最 近邻。多对象最近邻查询问题的应用十分广泛，包括基于位置关系的模式挖掘 【8 1 、模式识别和分类【2 】、基于图的机器学习【9 】等，也可以作为某些聚类算法 【3 ，1 0 ，1 1 ，1 2 或应用的核心模块【4 ，5 ，1 3 ，1 4 1 。在实际生活中，多对象最近邻查询在 地理信息系统、城市规划和资源分配等领域有着广泛的实际应用。例如，连锁店 经理需要考察所有分店距离配送点的距离，以便决定是否增加配送点；又如在市 政规划中，有关部门需要查询距离各个文物建筑最近的消防局，这样的数据信息 对相关决策具有重大的意义。 第一章引言 现有的多对象最近邻查询处理方法【1 】主要分成两大类：一类使用查询点集合 本身存在的r 树索引结构【1 5 1 ，另一类基于空间划分。利用最近点对( c l o s e s t p a i r ) j 1 6 的查询处理算法也可以进行多对象最近邻查询。以上这些查询处理方法 都假定对象之间的距离是欧氏距离，但这样的假设不符合实际生活中的一些情 形。例如：在城市中，从一个地点到另外一个地点的距离往往不是欧氏距离。人 们一般在一定的道路网络中活动：从一点到另一点要遵循已有的道路，而不能任 意穿行。城市中的道路情况是典型的道路网络。在道路网络中，空间对象之间的 距离应定义为实际情况下的道路网络距离。图1 1 是道路网络的简单示意图，图 中n l 和n 5 之间的欧氏距离很小，但两者之间的实际道路网络距离却很大( 从 n 1 到n 5 必须经过n 2 或者经过n 9 、n 1 0 ) 。这些针对欧式空间的多对象最近邻 查询处理方法不适用于道路网络环境。 f i g1 1r o a dn e t w o r ks c h e m a t i cd i a g r a m 图1 1 道路网络示意图 道路网络环境在实际生活十分常见：车辆、行人必须在城市的道路中穿行： 火车、地铁也必须按照既有的轨道行驶。道路网络中空间对象的查询处理已经成 为空间数据库领域中一个新的研究热点。目前已有针对道路网络环境中的最近邻 查询问题、区间查询、最近点对查询和e 距离邻近问题( e d i s t a n c ej o i n ) 的研 究成果。除此以外，道路网络中的空间对象的聚类问题、反向最近邻查询问题、 移动空间对象的最近邻问题等研究问题也都处于探索过程中。道路网络中的多对 象最近邻查询问题比欧式空间中的多对象最近邻查询问题更贴近现实生活，可以 广泛应用于地理信息系统、城市规划和资源分配等领域。但是，至今为止，道路 网络环境中的多对象最近邻查询问题还没得到很好的解决。 4 道路网络中的多对象最近邻查询研究 当然，通过重复调用现有的道路网络中最近邻查询算法，如r n e 1 7 、i e r ， m r i s 等，也可以处理道路网络中的多对象最近邻查询问题。但是，这种方法 的计算代价较大，在后面的章节中我们将进行具体分析。 至今为止，道路网络环境中的多对象最近邻查询问题还没得到很好的解决。 1 2 本文贡献 针对现有的问题，我们研究了道路网络中的多对象最近邻查询问题，提出一 个新颖的查询处理算法b a n n s ，该算法对于空间对象集合爿和b 都不要求其本 身带有任何索引结构，并能稳定、高效地进行查询处理。 本文的主要贡献有： 1 、定义道路网络中边与边之间的m a x d 距离，其实际意义为：在道路网络 中，从一条边的任意一个端点出发，到达另一条边的某个端点所经过的道路网络 距离一定不超过m a x d 距离。我们证明m a x d 距离是一种度量距离。 2 、利用m 树【6 】为道路网络环境中的边建立索引结构。基于该索引结构，我 们提出了b a n n s 算法，采用了批处理的基本思想来处理道路网络中的多对象最 近邻查询。 3 、为了给实际应用提供更多的信息，我们对b a n n s 算法进行了扩展，使 b a k n n s 能查询空间对象集合b 中a 集合元素的多个最近邻，并进行了实验分 析。 4 、分别使用人造道路网络和真实道路网络数据，验证了b a n n s 和b a k n n s 算法的性能。我们比较了b a n n s 、b a k n n s 算法和重复调用i n e 【1 8 】的方法的 性能，并分析了空间对象集合a 和口的大小以及m 树的扇出大小对b a n n s 、 b a k n n s 算法性能的影响。实验结果显示b a n n s 、b a k n n s 性能稳定、高效； 当空间对象集合a 较大时，b a n n s 具有更好的性能。对b a k n n s 算法来说， 随着k 的增加，可以适当增大m 树的扇出值。 从上面的描述我们可以看到：b a n n s 算法不同与以往的多对象最近邻查询 处理算法，该算法可适用于道路网络环境中，采用了道路网络距离来描述空间对 象之间的距离，更符合实际生活的情况，并且利用了批处理的思想，提高了查询 处理的效率。 5 第一章引言 1 4 本文结构 本文的正文结构如下：第二章介绍主要的相关工作，包括现有的针对欧氏空 间的多对象最近邻查询方法和道路网络中空间对象的查询问题研究现状：第三章 对道路网络环境和m 树索引结构进行介绍；我们将在第四章具体定义m a x d 距 离和b a n n s 算法，并证明m a x d 距离的相关性质；对b a n n s 算法的扩展将在 第五章中进行介绍：第六章采用两种道路网络数据，通过实验分别比较了 b a n n s 、b a k n n s 和重复调用i n e 的方法，并进行相关实验分析；最后部分是 总结和展望。 6 道路网络中的多对象最近邻查询研究 第二章相关工作 昴一草相天上作 多对象最近邻查询是最近邻查询的一个扩展，其应用十分广泛。道路网络环 境在实际生活十分常见，并且有着与欧式空间不同的特性。目前，道路网络中空 间对象的查询处理已经成为空间数据库领域中一个新的研究热点。但是，至今为 止，道路网络环境中的多对象最近邻查询问题还没得到很好的解决。 本文的相关工作分为以下两部分进行介绍：2 ，l 节介绍现有的针对欧氏空间 的多对象最近邻查询方法；道路网络中的相关工作将在22 节中进行介绍。 2 1 欧氏空间中的多对象最近邻查询 多对象最近邻查询是在给定两个空间对象集合a 、b 时，为a 中所有的对象 查找在口中的最近邻，是最近邻查询的一个扩展。z h a n g 等人 i i 对欧氏空间中的 多对象最近邻问题进行了研究，将多对象最近邻问题看成是最近邻问题和空间连 接( s p a t i a lj o i n ) 的混合，针对空间对象集合4 、b 本身是否存在索引的情况分 别进行了讨论，利用r 树索引和基于哈稀的方法来进行查询处理。在空间对象 集合b 本身带有索引的情况下，z h a n g 等人提出了m n n ( m u l t i p l en e a r e s t n e i g h b o r ) 和b n n ( b a t c h e dn e a r e s tn e d g h b o rs e a r c h ) 算法。其中，m n n 算法 采用嵌套循环的思路：首先，将空间对象集合爿的元素排序，然后，对每个集 合a 中元素进行最近邻查询处理。b n n 算法把空间对象集合爿中的元素划分成 不相交的子集，对每个子集的元素遍历一遍集合b 的r 树索引，从而进行查询处 理。z h a n g 等人提出了多种对b n n 算法的优化方法，如对空间对象集合月的采 用不同的分组方法。 对于空间对象集合b 本身不带有索引的情况，z h a n g 等人提出了基于哈稀的 h a n n ( h a s h - b a s e da n na l g o r i t h m ) 算法，该算法采用了空间哈稀( s p a t i a l h a s h i n g b 9 1 ) 的思想，利用规整的网格将空间划分为桶( b u c k e t ) ，将空间对象 集合a 、b 的元素映射到桶中，对于同一个桶中的集合a 的元素，在映射到对应 的桶中的集合曰的元素中查找最近邻。但是对于某个特定的空间对象来说，其 对应的集合口中的最近邻元素可能位于其他的桶中，所以该算法需要进行两遍 扫描。z h a n g 等人利用了l - h l b e r t 空间填充曲线1 2 0 1 ，通过改变桶的处理顺序来对 7 第二章相关工作 这个方法做了优化。 c o f f a l 等人 2 1 】通过遍历r + 树索引【2 2 来进行查询处理，采用优先队列来决 定节点的处理顺序，弄可用传统的m a x m a x l d s t 度量( 其定义为r + 树中两个节 点间相距最远的点之间的距离) 来剪枝。b o h m 和k r e b s 2 3 提出了类似的方法， 并推广到为集合彳中的每个元素查找对应的集合b 中的k 个最近邻。c h e l a 和 p a t e l 2 4 对欧式空间中利用树型索引结构来处理多对象晟近邻问题的算法进行 了进一步讨论，提出一个新的度量m i n m a x m l n d i s t ( 缩写为n x n d i s t ) ，采 用深入优先的方法遍历优化的四元树( q u a d t r e e 2 5 1 ) 。实验证明n x n d i s t 比 m a x m a x i d s t 更有效。 x i a 等人 2 6 1 提出了g - o r d e r 算法，利用p c a 技术( p r i n c i p a lc o m p o n e n t s a n a l y s i s ) 将集合a 、b 的空间转化为主成分空间( p r i n c i p a lc o m p o n e n ts p a c e ) ， 采用网格顺序( g r i do r d e r ) 对转换后的数据进行排序，最后用块嵌套循环连接 ( b l o c kn e s t e dl o o pj o i n ) 方法来处理k 近邻连接( k n nj o i n ) 问题。 在欧氏空间中，也可以利用最近点对( c l o s e s tp a i r ) 1 6 1 、【2 7 1 的查询处理算法 进行多对象最近邻查询。最近点对查询问题是给定两个空间对象集合a 、口，依 次找出两两距离最小的k 对空间对象，这里所说的一对空间对象是指包含一个集 合a 中的元素和一个集合口中的元素的两个空间对象。最近点对也是空间对象 研究领域的一个重要问题，c o r r a l 等人【1 6 、【2 7 对该问题做了深入的研究。c o r r a l 等人【1 6 】在空间对象集合4 和口都具有r 树索引时，提出了启发式的剪枝方法， 并利用这个剪枝方法设计了三个分之界限的算法来进行最近点对问题的查询处 理。利用最近点的查询处理算法来进行多对象最近邻查询的方式是：首先，为空 间对象集合a 中的每一个元素设一个标志位，并初始化为0 ：然后，调用最近点 对查询处理算法依次计算最近点对( a ，b ) ，如果a 的标志位为0 ，则把b 作为a 的最近邻，并把a 的标志位更新为1 ，否则继续计算下一个最近点对，直到空间 对象集合爿的所有元素的标志位都已经被设为1 。这种方法的缺点是计算代价很 大，因为最近点对的查询结果可能重复包括集合a 中的某些元素。 与多对象最近邻查询问题类似的还有距离连接问题( d i s t a n c ej o i n ) 。距离连 接问题是空间关系查询问题的一种，通过空间距离关系将多个空间数据集关联起 来进行分析。h j a l t a s o n 等人 2 8 1 ，s h i n 等人1 2 9 采用了r 树和优先队列讨论了具 有一定范围约束的距离空间连接。 但是，无论是z h a n g 等人提出的m n n 、b n n 和h a n n 算法，还是利用最 近点对查询处理算法来进行多对象最近邻查询处理、距离连接算法，都针对采用 欧氏距离的情况，不能直接适用于道路网络环境。 8 道路网络中的多对象最近邻查询研究 2 2 道路网络中空间对象的查询处理 在人类的生活和生产过程中，存在着大量与空间位置有关的信息，而在这其 中，道路网络又是十分常见的：车辆、行人必须在城市的道路中穿行：火车、地 铁也必须按照既有的轨道行驶。道路网络的示意图见图1 1 。道路网络中空间对 象的查询处理是空间数据库领域中一个新的研究方向。p a p a d i a s 等人【1 6 】首先提 出了在道路网络中对空间对象的查询问题，并给出了几个基本查询问题的算法， 包括k 近邻查询问题( k n n ) ，区间查询( r a n g eq u e r y ) ，最近点对查询和e 距 离邻近问题( e - d i s t a n c ej o i n ) 。p a p a d i a s 等人将实际的道路网络存储为带权有向 图，利用实际的道路网络距离来衡量空间对象之间的距离。p a p a d i a s 等人采用了 e r ( e u c l i d e a nr e s t r i c t i o n ) 和n e ( n e t w o r ke x p a n s i o n ) 两个框架来解决k 近邻 查询问题、区间查询、最近点对查询和e 距离邻近问题。e r 架构利用了两点问 道路网络距离不大于直线距离的性质，以直线距离为限制条件，缩小了查找范围： n e 架构以网络扩展( n e t w o r ke x p a n s i o n ) 3 0 1 为中心思想：从道路网络中的一 点出发，向各个方向进行网络扩展，直到找到符合查询条件的对象。 s h a h a b i 等人 1 7 1 利用空间映射的方法( r o a dn e t w o r ke m b e d d i n g ) 将道路网 络映射到高维空间，用棋盘距离( c h e s s b o a r dd i s t a n c 七m e t r i c ) 模拟实际的道路 网络距离，在这个基础上进行k 近邻查询处理。但由于空间的扭曲，其结果将会 产生一定的误差。 目前，对道路网络中的查询问题研究方兴未艾。绝大部分研究工作都把道路 网络抽象为带权图，所有的空间对象都位于道路网络的边上。y i u 等人对空间对 象的聚类问题 3 l i 和反向最近邻查询问题( r n n r e v e r s en e a r e s tn e i 曲b o r ) 3 2 1 分 别进行了研究。聚类问题是空间数据库的重要研究课题。y i u 等人首先对道路网 络中的聚类问题进行了研究，将道路网络看成一个带权无向图，提出了基于划分、 基于密度和基于层次的三种聚类方法。反向晟近邻查询问题是指给定空间对象集 合p 和一个空问对象q ，返回所有集合p 中以牮为最近邻的空间对象。y i u 等人 3 2 】提出了两种算法来进行反向最近邻查询处理，一是尽快地对访问到的网络节 点进行剪枝，二是对搜索区域进行剪枝。k o l a h d o u z a n 3 3 等人在道路网络环境中 利用维诺图( v o r o n o id i a g r a m ) 的概念来计算k 最近邻问题。其中，维诺图是 种基本的几何结构，是对空间的一种剖分，剖分得到的子空间不相互重合，所 有子空间的并集刚好铺满整个空间。维诺图本身就隐含着空间邻近关系。 k o l a h d o u z a n 等人通过将较大的道路网络分为较小的维诺区( v o r o n o ir e g i o n ) ，通 9 第二章相关工作 过预先计算维诺区内和维诺区间的道路网络距离，来减少查询处理的时间。 j e n s e n 等人【3 4 1 对道路网络环境中的移动空间对象的最近邻问题进行了研究。随 着移动通信和定位技术的发展，为移动用户提供其他移动用户的信息成为可能。 j e r t s e n 等人提出了一个原型系统来进行道路网络中的移动对象的k 近邻查询处 理。该系统采用服务器客户端架构，首先由服务器产生可能的候选结果，然后由 客户端维护动态的k 近邻结果：每隔一段时间就更新候选结果以减少误差。j i n 3 5 1 等人对道路网络中的离群点问题进行了研究。离群点问题是数据挖掘中的重要任 务之一，这里的离群点是道路网络中基于距离的离群点。j i n 等人通过对道路网 络的划分，排除不可能存在离群点的边，从而迅速在剩余的边上找到存在的离群 点。s h e k h a r 和y o o 3 6 j 对沿着某条路径移动的空间对象的最近邻问题做了初步探 索，提出了四个算法来进行i r n n ( i n r o u t en e a r e s tn e i 曲b o o n 题的查询处理， 并用实验比较了各个算法的优缺。f e n g 等人 3 7 1 讨论了道路网络中的多对象最近 邻查询的更新问题，通过定义两个搜索区域( p r e g i o n , r - r e g i o n ) 来减少搜索的 范围。但是，至今为止，道路网络环境中的多对象最近邻查询问题还没得到很好 的解决。 值得注意的是：大部分研究工作中的路径计算都采用了网络扩展的思想：从 一点出发，向各个方向进行网络扩展。该方法可以实时计算道路网络中任意两点 的道路网络距离，但其计算代价较大。a g r a w a l 等人、j u n g 等人采用预先计算的 办法 3 8 ，3 9 1 ，大大减少了计算道路网络距离的时间代价，道路网络中任意两点之 间的距离可以在常数时间内得到。本文将采用预先计算的方法计算道路网络距 离，对道路网络中的边建立m 树索引，提出一个新颖的道路网络中多对象最近 邻查询算法b a n n s ，并对其进行了扩展，使b a k n n s 算法能查询空间对象集合 b 中a 集合元素的多个最近邻。 1 0 道路两络中的多对象最近邻查询研究 第三章相关概念 道路网络环境在实际生活十分常见：行人、车辆往往在一定的道路网络中行 进。在道路网络中，空间对象之间的距离应定义为实际情况下的道路网络距离。 正因为如此，针对欧式空间的多对象最近邻查询处理方法不适用于道路网络环 境。针对现有的问题，我们研究了道路网络中的多对象最近邻查询问题，利用m 树为道路网络环境中的边建立索引结构，提出了一个新颖的查询处理算法 b a n n s 。 m 树是度量空间中索引技术的代表。c i a e c i a 等人【4 0 1 首先提出了m 树索引 结构， 本章对相关概念进行介绍，结构如下：3 1 节介绍道路网络的基本概念，包 括其形式化定义：3 2 节介绍m 树索引结构的基本概念。下面先对文中涉及的相 关定义进行介绍。 3 1 道路网络基本概念 在实际生活中，人们常常在一定的道路网络中活动。在道路网络中，从一点 到另一点要遵循已有的道路，所以两点之间的实际距离往往不能用欧式距离来表 示。道路网络( r o a dn e t w o r k ) 可以表示成一个无向有权图，记为g e 叨，其 中矿是节点的集合；是边的集合，边p 可以表示为( ，n e ) ，肋为e 的起始 端点， - 为g 的结束端点，m 和 _ 的选择可以根据两者的实际坐标来决定；映 射i e e - - - ) r + 给每条边指定一个非负的长度。 道路网络中的任意一点n 可以表示为( n i ，m ，p o s ) ，其中为n 所处的边p 的起始端点，2 为g 的结束端点：p o s 0 ，聊砂】，代表n 的相对位置，到n 这 部分边的长度为p o s ，n 到m 这部分边的长度为w ( e ) - p o s 。位于同一条边上的任 意两点n 、m 之间的部分边的长度为l v o s 。- p o l 。以下将同条边上的任意两点r t 、 搬之间的边的长度记为荔。 在道路网络中，节点之间路径的长度为该路径所包含的边的长度之和。任意 两个节点之间的距离为道路网络距离( n e t w o r kd i s t a n c e ) 3 1 】，记为d ( ，川) ，即 从节点，到节点，的所有路径中最短路径的长度。任意个不是节点的点n 到 第三章相关概念 任意节点坼的道路网络距离为r a i n i 。 1 2 l ( 五矿+ d ( ，以) ) ，其中n ，( 1 = 1 ，2 ) 是n 所在边的端点。对任意两个不是节点的点n 、肌之间的道路网络距离可以类似的 定义： 如果n 、 a 不在同一条边上，r 所在边的端点记为n ，m 所在边的端点记为 m ，则n 、m 之间的道路网络距离为： m i n f a ，2 i ， l ，2 ( 州，+ j ( ，m 。) + 删，) 3 1 如果n 、肌在同一条边上，则两者间的道路网络距离为上述结果与；磊之间的 最小值。综上，道路网络中任意两个不是节点的点、m 之间的道路网络距离记为： m ，小州m i nf 砘2 j ( 兰“n 肘r a m j ) ，训妒，= 0 2 一。i n u ni a ，2 t j l ，2 ( n n ，+ d ( ，m ，) + 删) i t 0 1 d 2 其中，n 所在边o t 的端点为n ，m 所在边0 2 的端点为m 。 以下将道路网络中的任意两点工、y 之间的道路网络距离以t 力简写为x y 。 3 2m 树索引简介 m 树是对度量空间( m e t r i cs p a c e ) 的动态索引结构，在凡是采用度量距离 ( m e t r i cd i s t a n c e ) 的环境中都可以利用m 树为对象建立索引结构 4 0 1 。下面首先 介绍度量空间和度量距离的概念。 度量空间在形式上定义为m 气0 ，d ) ，其中o 是特征值的范围，d 是一个度 量距离。假设仉，d ，q 是对象集中的三个对象，它们之间的相似性可通过度 量距离d 来度量。度量距离d 是一个距离函数，具有以下特性： 】对称性。即d 似，例= d 织，鲫 2 非负性。即当0 g 时，d ( g ，例 o ，当识= 口时，d a 0 = o 3 三角不等式。即d n 0 d r 0 ；0 1 j + a ( o o 3 基于度量空间的索引技术是一种应用非常广泛的索引技术，它能够对普通的 度量空间的数据进行有效的查询，m 树是度量空间中索引技术的代表。 下面定义一些文中用到的记号和术语，如表1 所示： 1 2 道路网络中的多对象最近邻查询研究 s v m b o ld e f i n i t i o n o r ( f e a t u r ev a l u eo f t h e ) r o u t i n go b j e c t t ( 0 0 c o v e r i n gt r e eo f 口 p t r ( t ( o j ) p o i n t e rt ot h er o o to f t ( o r ) r ( o r )c o v e r i n gr a d i u so f0 r d ( o r , p ( o r ) ) d i s t a n c eo f o rf r o mi t sp a r e n t c l( f e a t u r ev a l u eo f t h e ) d bo b j e c t o j d ( o )o b j e c ti d e n t i f i e r d l o h p i o d i s t a n c eo f qf r o mi t s p a r e n t t a b l e1 ，l i s to fs y m b o l s 表1 本文定义的一些记号和术语 m 树是一棵平衡树，其节点分为中间节点和叶节点两种。中间节点保存路由 对象，路由对象记为【0 _ p 扩仃徊，r ( o r ) ，d 仇p r o 圳】，覆盖一个以0 ，为中心，r ( o r ) 为半径的区域，所有聊中的对象到d 的距离都不超过，r ，。u 。根节点中的路 由对象无需定义d ( o 。p ( o 圳。为方便起见，路由对象也可简称为d 。叶子节点 中的项记为 c i ，o t d ( o ) d ( q ，尸r 0 l 。图3 1 为欧氏空间中m 树的简单示意图，图 中黑色圆点均为被索引的对象。 f i g 3 1m - t r e es c h e m a t i cd i a g r a m 图31 m 树示意图 m 树的建立可采用逐个插入被索引对象的方法。插入对象时，从根节点出发 循环查找最适合插入对象的子树，直到该子树只包含一个节点，即m 树的叶节 点，执行插入操作。如果插入操作将引起溢出，那么执行分裂操作，并更新上层 第三章相关概念 节点信息。在每一次选择将要插入对象的子树时，选择插入操作不会引起r ( 0 0 增加的t ( 0 9 ，如果存在多个这样的t ( o d ，j j v z , 选择距离插入对象最近的口所 对应的t ( 0 9 ：如果不存在这样的z 徊，那么选择插入对象后，r 0 9 增量最小的 t ( 0 9 。c i a e c i a 等人【4 1 l 提出了批量构建m 树的方法( b u l kl o a d i n g ) ，该方法通 过一种自底向上的批量装载技术实现快速的索引构建。 m 树利用三角不等式过滤和分支界限技术可以高效地支持范围查询和最近 邻查询。在第五章、第六章中将要介绍的b a n n s 算法和b a k n n s 算法也利用 到了m 树相关的剪枝技术。图3 2 、图3 3 为m 树范围查询剪枝示意图，显示了 当查询条件为给定查询点q 和距离范围时，怎样利用m 树的性质进行剪枝。 图中，q 为查询对象，为距离范围。图3 2 中，o _ v 为路由对象。 f i g3 2m - t r e er a n g eq u e r y , p r u n i n gs c h e m a t i cd i a g r a m 图3 2m 树范围查询剪枝示意图 当d 他0 纠 r o y ) + 8 的时候，就可以不再考虑以0 ，为路由对象的节点。因 为此时： d ( q ，q d n 9o n ) 一d 口o n ) d ( q 。o 一r o y ) r 门彬+ r o y ) = e 3 3 图3 3 中，o r 、印都是路由对象。当l d ( o p , 一讲o j i ，例+ 时，可以 不再考虑o ，所代表的节点中的对象。这是因为： d 怫9 一d ( o r 例r r 0 + 曹d ( o nq ) ，r 。+ 3 4 1 4 道路网络中的多对象最近邻查询研究 f i g 3 3m q r e er a n g eq u e r yp r u n i n gs c h e m a t i cd i a g r a m 图3 3m 树范围查询剪枝示意图 1 5 道路两络中的多对象最近邻查询研究 第四章b a n n s 算法 多对象最近邻查询在地理信息系统、城市规划和资源分配等领域有着广泛的 实际应用。但是至今为止，道路网络环境中的多对象最近邻查询问题还没得到很 好的解决。本文定义道路网络环境下的多对象最近邻查询为：给定一个道路网络 和该道路网络中的两个空间对象集合4 、b ，在集合口中查找集合中所有对象 的最近邻。这里空间对象集合a 、b 中的元素可以是道路网络中的节点，也可以 是位于边上的任意点。我们利用m 树对道路网络中的边建立索引结构，基于该 索引，提出了一个新颖的多对象最近邻查询处理算法b a n s 。b a n n s 算法对 于空间对象集合a 和b 都不要求其本身带有任何索引结构，并能稳定、高效地 进行查询处理。 本章结构如下：4l 节提出了施工d 距离和相关性质，证明了m a x d 距离是 一种度量距离。4 2 节提出了道路网络环境中的多对象最近邻查询处理算法： b a n n s ，并给出了详细的说明。 4 1m a x d 距离 为了对道路网络中的边建立高效的索引结构，我们定义道路网络中边与边之 间的胁工d 距离，其实际意义为：在道路网络中，从一