（计算机软件与理论专业论文）空间移动对象的最近邻查询方法研究——移动对象连续k近邻查询.pdf

摘要 近年来，随着卫星定位系统( 如g p s ) 和无线通讯技术的快速发展，跟踪并记录 移动对象的位置变得可行，针对地理信息系统中最近邻查询方法的研究引起了人们越 来越多的兴趣和关注，尤其是查询对象和目标对象均移动的最近邻查询。 查询对象和目标对象均移动的最近邻查询可以按移动对象的运动轨迹是否己知 分为两类，其中，运动轨迹未知的最近邻查询在实际应用中较为广泛，而且这类应用 往往都是做连续的k 近邻查询。传统的移动对象连续k 近邻查询的方法是在t p r t r e e 索引结构上采用快照方式，作一系列静态的k 近邻查询。这种方法每次查询都要重新 查找所有的k 个邻居，存在重复计算的问题。 本文在传统的移动对象k 近邻查询算法上进行改进，考虑到当连续查询的时间间 隔在一定范围内时，前后两次的查询结果存在一定联系，提出用查找候选集代替搜索 整个目标对象集合，使查询范围变小，提高查询效率。同时，候选集内的对象还可以 通过判断运动趋势进行筛选，再次精化候选集。 本文分别就传统移动对象连续k 近邻算法和改进移动对象连续k 近邻算法作了模 拟实验比较，模拟实验表明，改进算法的稳定性较好，且查询效率要优于传统算法。 关键词：地理信息系统，连续k 近邻查询，空问索引，r - t r e e ，t p r - 订e e a b s t r a c t w i mt h er a p j dd e v e l o p m e mo fg p sa 1 1 dw i r e l e s sc o m m u n i c a t i o n ，i ti se a s yt ot r a c ea n d r e c o r dt h ep o s i t i o n so fm o v i n go b j e c t s t h er e s e a r c ho nn e a r e s tn e i g h b o rq u e r i e s ， e s p e c i a j l yt h en e a r e s tn e 培h b o rq u e r i e so fm o v i n gq u e r ya n dt a r g e to b j e c t s ，i sa r o u s i n g m o r ea n dm o r ei n t e r e s t sa n da t t e m i o n s a c c o r d i n gt ot h c 仃a c ko fm o v i n go b j e c t s ，t h e r ei st w od i f r e r e n tk i n d so fn e 盯e s tn e i 曲b o r q u e r i e so fm o v i n gq u e r ya n dm o v i n gt a 玛e to b j e c t s o n eo ft h e m ，t h ec o n t i n u o u sk - n e a r e s t n e i g h b o rq u e r i e sw i t l l o u tt m c ki sm o r ep 叩u l a ri na p p l i c a t i o n t h et r a d i t i o n a la l g o r i t h mo f c o n t i n u o u sk n e a r e s tn e i g h b o rq u e r i e si sas e r i e so fs t a t i ck n e a r e s tn e i g h b o rq u e r i e s ，u s i n g s n 印s h o ti nt p r t r e e t h i sa l g o r i m mh a sap r o b l e mo fr e p e a t i n gc o m p u t a t i o ni t h a st o r e s e a r c ha l l 山ekn e i g h b o r sw h e nq u e r ye v e r yt i m e t h i st | l e s i si m p r o v e st h et r a d i t i o n a la l g o r i t h mo fk n e a r e s tn e i g h b o rq u e r i e so nm o v i n g o b j e c t s b a s e do nt h et m t l lt h a t 血er e s u l t so fe v e r yc o n t i n u o u st w oq u e r i e sa r er e l a t e dt o e a c ho t h e fw h e nt h ei n t e r v a lo fc o n t i n u o u sq u e r i e si si ns o m er e g i o n ，w ep r e s e n ta c a r d i d a t es e tt or e p l a c et h ew h o l et 8 r g e ts e t i nm i sw a y ，w ec a nr e d u c et h es e a r c hr e g i o n a 1 1 de n h a n c et h eq u e r ye 伍c i e n c y m e a n w h i l e ，t h ec a n d i d a t es e tc a nb ed i m i n i s h e da g a mb y j u d g i n gn l et r e n do fm o v i n g f i n a l l y ，w ec o m p a r et h ei m p m v e da l g o r i t h mt ot h et r a d i t i o n a la l g o r i t t h ee x p e r i m e n t p r o v e st l l es t a b i l i t ya n de m c i e n c yo ft l l ei m p r o v e da l g o r i t h mi sb e t t e r t h a l lt h et m d i t i o n a l a l g o r i 曲n k e y w o r d s ：g e o g r a p h i c a li n f o n n a t i o ns y s t e m ，c o n t i n u o u sk n e a r e s tn e i 曲b o rq u e r y s p a t i a l i n d e x ，r - t r e e ，t p r t r e e 1 1 1 - l 研究背景与意义 第一章绪论 地理信息系统( g e o g m p l l i c a li t l f o r n l a t i o ns y s t e m ，g i s ) 是2 0 世纪6 0 年代迅速 发展起来的集地理空问数据处理与计算机技术于一体的一门边缘技术学科，是指在计 算机软硬件下，采集、存储、管理、处理、检索、分析和显示空间物体的地理分布以 及与之相关的属性，为地理研究和地理决策等服务的计算机技术系统 1 。如今，g i s 正形成完整的技术系统并逐渐建立起独立的理论体系。 地理信息系统的主要任务之一是有效检索空间数据以及快速响应不同用户的查 询f 2 1 。其中，最近邻( m en e a r e s tn e i 曲b o r ，n n ) 查询是经常遇到的一类查询，它 用来找出空问中距离指定点最近的对象，即找到其最近邻居。最近邻查询与传统数据 库的查询不同，例如，要查找人口超过1 0 万的城市有哪几座，通过传统数据库可以 很方便得到查询结果，但若是要求查找距离南京最近的人口超过1 0 万的城市，复杂 性便大大增加。首先要找到满足人口要求的所有城市，然后还要需要计算每个城市距 离南京的距离，而最坏情况是找到最后的城市才满足要求。传统数据库管理这类空间 地理信息有一定局限性，对于此类涉及地理信息的查询，一般方法是选用适当的索引 结构。 随着计算机技术、信息技术、空间技术的发展，地理信息系统的应用越来越广泛。 而全球定位系统( g l o b a ip o s i t i o n i n gs y s t e m ，g p s ) 的出现，更是提高了g i s 的动态 分析能力。g p s 是2 0 世纪7 0 年代由美国陆海空三军联合研制的新一代空间卫星导航 定位系统，由于其所具有的全天候、高精度和自动测量等特点，作为先进的测量手段 和新的生产力，已经融入了国民经济建设、国防建设和社会发展的各个应用领域，并 开始逐步深入人们的日常生活。 g p s 系统的高精度、全天候和全球性定位，使得跟踪并记录移动对象的位置变得 可行，针对移动对象的最近邻查询越来越被人们关注。最近邻查询在智能交通系统、 科学调查、军事、资源管理中有广泛的应用前景，是空间访问方法及查询方法的研究 热点之一。例如，在智能交通系统中，查找离移动的出租车最近的加油站，或者查找 从a 地到b 地沿途最近的饭店等等。 最近邻的数目可以是一个，也可以是k ( k 1 ) 个，若k 1 则称k 近邻。例如， 在地理信息系统中，对一个特定的位置或目标，要求系统查找并返回五个离它最近的 对象：在智能交通系统中，查找无人驾驶公交车周围最近的1 0 辆汽车等等。本文主 要研究的是移动对象的连续k 近邻查询。 1 2 国内外研究现状 最近邻查询是k 近邻查询的一种特殊情况，一般研究都是从最近邻开始，然后扩 展到k 近邻。针对最近邻的查询，近几年已有不少文章做出研究，如最近邻查询 3 1 1 、 连续最近邻查询【1 2 1 8 】、逆最近邻查询【1 9 2 2 】等等。但究其本质，可以根据空间对 象( 查询对象和目标对象) 在空间中随时间变化的状态( 如固定或移动) 分为四大类， 如表1 1 所示。 表1 l ：最近邻查询分类 鸯瑚对缘 同杯寿八、 弼定移动 查谰对象 路线已鬟睢8 1 ) 固定髅态奄铷1 镬嘟对辍 路线：定3 - 2 查m 对象逝定 盘踟对象 移动 日标对象移动2 ) 嘲貅对象均穆衲一) 其中，1 ) 、2 ) 两类查询对象固定，需要查找的最近邻为静态或移动：3 ) 、4 ) 则针对移动查询 对象，查找静态或移动的晟近邻。这里的移动又可以分为二维空间中的自由移动或是沿着一定轨 迹移动两种类型。 下面分别介绍这四类查询的研究现状： ( 1 ) 静态查询。这类查询的研究比较成熟，目前国内外已有不少相关文献 3 6 ，2 3 。3 l 】。普遍的方法是利用特定的空间索引结构( 如r 一仃e e 2 3 、x t r e e 2 4 】、 m 一仃e e 2 5 等) 的特性，结合一定的辅助数据结构进行查找。 计算机将存储器分为内存、外存，而访问外存所花费的时间是访问内存的千倍以 上。在实际的g i s 应用中，大量的空间数据是存储在外存上的，如果对外存上数据的 位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这种访问磁盘的 代价就会严重影响系统的效率。因此，g i s 必须将数据在磁盘上的位置加以记录和组 织，通过内存中的一些计算来取代对磁盘漫无目的的访问，以便提高系统效率。一个 实际的g i s 涉及各种海量的复杂空间数据，数据的索引对于系统的处理效率至关重要 3 2 1 。美国加州大学g u t t n l a n 教授在1 9 8 4 年提出的一种空间索引结构_ r t r e e ，现 已成为空间数据库索引中应用最广泛的算法之一。r - t r e e 较好地解决了许多传统算法 未能解决的空间数据的索引问题。 静态查询最为典型的研究是g r h j a l t a s o n 等在 3 】中提出r - t r e e 索引结构结合优 先队列的方法。这个方法使得查询时，不需要遍历所有的对象，通过利用剪枝策略提 高查询效率。而且根据优先队列的特性，对于查找k 近邻效率更高。 国内的一些学者则对索引结构作了不少改进。张芩等在【2 7 】中提出q r _ t r e e ，先 对整个索引空间用四叉树进行划分，子索引再采用r - t r e e ，实质是将一棵“大”的 r 一订e e 分解成多棵“小”的r 一仃e e ，将查询尽可能限定在局部空间区域，从而提高查 询性能：邱建华等在 2 8 中则在酣仃e e 基础上引入了四叉树，提出q r + t r e e 。r + t r e e 是对r ，t r e e 的改进，i h r e e 的主要缺陷是结点的重叠，r + t r e e 则尽量减小结点间的重 叠面积。此外，国内的相关研究还有：张明波等在【2 6 仲回顾了r _ t r e e 的演变和发展； 刘宇等在 2 9 】中提出了基于r 一仃e e 的两个新的最近邻搜索剪枝策略；过志峰等在 3 0 1 中提出了基于r + 一t r e e 的优化的空间查询系统框架设计；白玉琪等则在 3 l 】中将r t r e e 算法用于搜索引擎。 ( 2 ) 查询对象固定、目标对象移动的最近邻查询，如“1 0 分钟后距离某加油站 最近的汽车”，这类查询的关键是为移动的目标对象选择适当的索引结构，典型的方 法如y f t a o 等在 1 l 仲利用t p r _ 廿e e 索引结构来做查询。当把移动的目标对象索引 起来后，查询就可以参照静态查询的方法。这类查询有其特殊性，如查找医院周围最 近的一些救护车等等，目前的研究不是很多。 ( 3 ) 目标对象为静态，查询对象移动的最近邻查询，主要应用在智能交通系统 中，如以饭店、加油站等为静态目标对象，运动中的公交车、出租车为查询对象，查 询出租车行进路线上最近的加油站。这类查询又分为查询对象运动轨迹预知和未知两 类： 当查询对象移动的轨迹预定时，这类查询需要为查询对象的每一个位置重复计算 它的k 近邻。解决问题的关键在于：如何减少随着查询对象的移动而带来的重复计算。 目前有大量的研究对此进行探讨 7 ，8 ，1 2 1 4 】，综合起来不外乎两点： 利用查询对象的移动轨迹信息，减少重复计算。典型的研究是y ft a o 等在 1 2 中提出的找到查询对象移动轨迹上的分割点的方法。这种方法主要目的是求连续最近 邻，如出租车从a 地到b 地，找出沿途的所有的最近加油站。 对目标对象集进行预处理，从而利用预处理结果来满足查询要求。典型研究 是【7 ，8 ，1 4 】中提出的v o m n o i 方法。采用v o r o n o i 方法预先划分目标对象区域，这样在 目标对象为静态的情况下，一旦路线给出，就能很快的给出每一段路线上的最近邻。 对于查询对象移动轨迹不确定的情况，则需要从如何减小重复计算的角度考虑。 如s o n g 在 9 】中提出的利用前次查询结果来缩小下次查询范围的方法。 m k o l a l d o u z a ! l 等在 7 】中提出的v o r o n o i 方法同样也可用于查询对象移动轨迹不 定的情况，因为目标对象固定，且已经过预处理，一旦知道查询对象目前在哪个区域 内即可确定其最近邻。j z h a n g 等则在 1 0 】中提出当查询对象q 仍在初始位置周围的一 定区域( 有效区域) 内，则最近邻结果不变。而这个有效区域可以通过v o r o n o i 方法 来获得，这种方法同样通过减少更新次数来提高效率。这两个采用v o r o r n o i 的方法同 样不适用求k 近邻。 ( 4 ) 目标和查询对象均移动，这类查询的主要问题是计算量大，所有对象均移 动，不能很好掌握更新时间。这一类的研究不是很多，而且一般都假设所有移动对象 的运动函数已知。y f l i 等在【1 6 】中充分利用了已知的对象运动函数，提出不需要监 视所有的k 个对象，只要考虑第k 个邻居，因为它的变化是心i n 变化的必要条件。 但是在实际的应用中，移动对象的轨迹往往不可预知，如公路网上的汽车，这时 就需要找到一种更有效的查询方法。c s j e n s e n 等在 3 3 1 中讨论了公路网上的移动对 象查找移动的k 近邻的方法，采用c ，s 体系结构。对于查询对象q 发出的查询请求 k n n ，服务器端给出一个最近邻候选集合瑚n n ( m k ) ，而由客户端完成对候选集的 维护，即再计算候选集中目标对象到查询对象的距离，给出k n n ，然后周期性地更 新候选集，以避免查询结果的不精确。该方法以搜索候选集来替代搜索整个目标对象 集，同时由求出的最近邻位置与实际位置之问的误差来决定更新，以此提高搜索效率 和精度。但是这种方法的更新时间难以把握，若更新时间过短，则计算量太大：若更 新时间过长，则计算结果误差增大。 随着卫星定位系统( 如g p s ) 和无线通讯技术的快速发展，跟踪并记录移动对象 的位置变得可行，移动对象的最近邻查询成为最近邻查询的重点和难点，特别是目标 对象和查询对象均移动的情况。而在实际应用中，目标对象和查询对象均移动的最近 邻查询往往与连续查询结合在一起，这就是本文要研究的空间移动对象的连续k 近邻 查询。 1 3 本文的主要内容 1 3 1 研究内容与目标 本文研究空间移动对象的连续k 近邻查询方法，即查询对象和目标对象均移动。 同时，研究的并不只是某一时刻的k 近邻查询方法，而是针对移动查询对象的连续k 近邻查询，如每隔一分钟查找一下移动车辆的k 近邻。假设各移动对象均在二维空间 运动，且速度的大小和方向不变。 考虑到预知每个对象运动轨迹的查询局限性太大，本文研究移动对象运动轨迹未 知的查询，更贴近于真实应用。移动对象连续k 近邻查询的研究有着广泛的应用前景， 如智能交通中，无人驾驶的公交车，连续判断其周围的交通状况，以做出正确的路线 选择；军事上可应用连续的k 近邻查询来协同作战：另外还可用于海洋导航、移动自 组网络的路径选择等等。 1 3 2 本文的贡献 传统的移动对象k 近邻查询，采用t p r t r e e 索引结构，查询方法类似于静态k 近邻查询。而作连续查询时，采用快照方式，由一系列静态查询构成，即每一次都重 新做了一遍静态的k 近邻搜索。 本文改进了传统的移动对象k 近邻查询算法，使之更适用于做连续查询。主要思 想是考虑到在一定时间内，查询对象的k 近邻始终在查询对象周围的一定范围内，此 范围外的对象在这段时间内都不需要考虑。改进算法通过缩小搜索范围来提高查询效 率。 本文构建了三个数据集来比较改进算法和传统算法的优劣。第一个数据集中对象 均匀分布，同时每个对象的速度相同( 包括大小和方向) ；第二个数据集的对象也是 均匀分布，但速度为随机值；第三个数据集的对象和对象的速度均取随机值，以此来 模拟现实世界中的真实移动对象。 比较结果表明，改进算法更有利于作移动对象的连续k 近邻查询，且查询效率高 于传统算法。 1 4 本文的组织 本章是绪论部分，主要介绍最近邻查询的研究背景和意义，并介绍了目前国内外 的研究现状，简单分析了各种类型的k 近邻查询方法的优点和不足，最后给出了本文 研究的主要内容，包括研究目标和研究成果。 第二章移动对象连续k 近邻查询的传统算法，由于这种查询以静态k 近邻查询为 基础，先详细介绍了静态最近邻查询，然后分别介绍移动对象运动轨迹预知和未知的 连续k 近邻查询。 第三章移动对象连续k 近邻查询的改进算法，在传统算法的基础上引入候选集， 并讨论候选集的更新和精化，最后给出了查询的算法描述。 第四章实验比较移动对象连续k 近邻查询的传统算法和改进算法，并分析两个算 法各自的优劣。 第五章总结和展望，总结全文工作，并对进一步的工作作出展望。 第二章移动对象连续k 近邻查询的传统算法 本章主要讨论移动对象连续k 近邻查询的传统算法，这种查询按照移动对象的运 动轨迹分为两类：移动对象运动轨迹预知的连续k 近邻查询和运动轨迹未知的连续k 近邻查询。本文侧重研究运动轨迹未知的连续k 近邻查询，而这类查询以静态最近邻 查询为基础，因此本章首先介绍静态最近邻查询。 2 1 静态最近邻查询 静态最近邻查询是其它各种最近邻查询( 包括移动对象最近邻查询) 的基础，而 在介绍静态最近邻查询之前，首先要介绍空间索引技术，它是快速查询、显示、更新 地理空间数据的重要指标。 空间对象的数据一般可用多属性的一条记录来描述，但因为这类数据的数据量 大、结构和关系复杂，传统的数据库系统不能有效地支持对这类数据的处理：空间操 作与计算比传统的关系运算代价高，不能像传统数据库那样用某种命令对空问目标进 行分类、排序【3 4 】。因此，空问数据处理必须采用特定的索引技术。 以传统的索引技术观点来看，可以把空问索引技术大致分为四大类f 4 5 ：基于b 树、基于h a s h i n g 、基于二叉树和基于空间填充曲线。按照建立索引时，划分区域是 否与空间对象的分布特征有关，空问索引又可以分为两大类：( 1 ) 划分区域与空问对 象分布特征无关；( 2 ) 划分区域与空间对象的分布特征有关。前者包括网格索引、四 叉树；后者包括b s p 廿e e 、k d - 仃e e 、k d b _ t r e e 、r 屯e e 及其变种、c e l l - t r e e 、x t r e e 和t r e e 等众多空间索引。 在这众多空间索引结构中，又以网格空间索引、四叉树系列空间索引和r t r e e 系列空间索引最为常见。其中，r _ t r e e 具有很强的灵活性与可调节性，建树过程中无 需预知整个空问对象所在的空间范围，同时它具有较高的执行效率，被公认为是较好 的空间索引结构，已经得到广泛应用。下面详细介绍r 一e e 索引结构。 2 1 1r _ t r e e 索引结构 r t r e e ( 图2 1 ) 是一种具有层次结构的平衡树，它是b + 一t r e e 的扩展 3 。其构建 思想是以最小限定矩形( m i n i m 眦b o u n d i n gr e c t a j l g l e ，m b r ) 递归地对数据集空问按 照“面积”规则进行划分【2 。r _ 讹e 中非叶结点代表一个划分的空间区域，即一个矩 形空间区域；叶子结点包含的矩形区域对应空间对象的m b r 。构造矩形空间的原则 是：( 1 ) 矩形之间尽可能少重叠；( 2 ) 矩形尽可能包含更多的空间对象：( 3 ) 矩形可 以嵌套，即矩形中可以包括更小的矩形。 r - t r e e 的结点是一个二元组 ，其中p o i n t e r 是指向子树的指针，而 k e y 是最小限定矩形，包含p o i n t e r 指向的子树中所有对象的m b r 。在r _ t r e e 的叶子 结点中，d o i n t e r 是具体对象的标识符。 每个结点能包含的对象或子结点的最大值称为结点容量，取值范围为 m ，m 1 。 m 取决于数据在硬盘驱动器上的存储参数，如磁盘页面大小或容量，通常选取使得 一个结点填充满( 或小于) 一个磁盘页的数值。当结点中的对象数超过m 时，就需 要分裂，r _ 仃e e 采用使分裂产生的两部分面积之和最小的分裂方案。m 取决于数据库 的操作，若数据库仅仅( 或大部分) 只需要查询而较少更新，m 取较大的值，使r 树高度小，从而搜索快，但易引起溢出或下溢；若数据库需要经常更新或调整，则m 取小值。通常m 在2 m 2 之间选择。 r 仃e e 允许结点相互重叠 3 6 】，这种重叠可以使r - 仃e e 保持较高的空间利用率( 内 存、磁盘) 和保持树的平衡。但另一个方面，过多重叠可能会造成查询效率的降低， 最坏的情况下对某一对象的查询可能造成对整个树的搜索。 l 澈 gl i d! i ， 飓 c ( a ) 线段的空i 司位置和其m b r( b ) r - t r e e 索引结构 图2 1 ：线段的r t r e e 索引结构 r 仃e e 的空间划分与数据结构如图2 1 所示。进行空间检索时，首先判断哪些矩 形区域与查询对象相交，再进一步判断落在这些矩形区域中有哪些被检索的对象。 查找效率主要取决于r - 仃e e 的深度及予树索引空间的重叠程度【3 4 1 。r t r e e 的深 度越低，查找过程中访问的结点数就越少，查询效率越高；子树索引空间的重叠越少， 查找过程中遍历的子树就越少，访问的结点数也就越少，查询效率也就越好。 由于r - 仃e e 的深度只与空间对象的数量有关，所以，r _ t r e e 构造的关键就是尽量 减少子树索引空间的重叠。在r - 慨e 的构造算法中，g u 讹l a l l 将索引空间的“面积” 作为惟一的度量，空问对象总是插入使索引空间“面积”增量最小的子树中，以期尽 量缩小索引空间的重叠“面积”，减少索引空间的重叠程度及缩短查找路径。但是， 由于构造算法的动态性，r t r e e 不可避免地会产生大量的重叠和“死空间”( 不包含 空间对象的索引空间) ，从而导致效率下降。 综上所述，r - 仃e e 存在的问题可以归纳为两方面f 2 1 ： ( 1 ) 由于空间对象千姿百态，其索引空间经常重叠，且其重叠的程度随着数据 量或空间维数的增加而增加。索引空问的重叠必然造成树的深度及存储空间的增加， 从而导致遍历时间增加查询效率下降； ( 2 ) 在动态构建r 一廿e e 时会产生大量“死空间”( 不包含空间目标的索引空间) ， 造成存储空间的浪费，产生无效的遍历。 虽然r i t r e e 存在上述问题，但是，由于其具有很强的灵活性与可调节性，建树过 程中无需预知整个空间对象所在的空间范围，同时还具有较高的执行效率，r _ t r e e 及 其变种现已成为空间数据库索引中应用最广泛的索引结构之一。 2 1 2 查询算法描述 最近邻查询主要是距离的查询，下面首先给出距离函数的定义 定义2 1 ：距离函数d i s t ( q ，p ) 表示q 到p 的距离，其中，q 是具体对象，p 是具体 对象或r t r e e 中的结点m b r 。若p 是具体对象，d i s t ( q ，p ) 是对象问的欧氏距离；若 p 是m b r ，则d i s t ( q ，p ) 是q 到p 的最小距离。 r - t r e e 索引结构中，划分区域与空间对象的分布有关，直观地讲，即同一个m b r 中的元素从空间上来看是聚在一起的。在作最近邻查询时，可以充分利用这些已划分 好的区域，先找到距离查询对象最近的一个区域，则所求的结果很有可能就在这个区 域里。根据这个特点，有定理2 1 3 】： 定理2 1 ：v n ，n 是r - 仃e e 中结点，了n ，n n ，都有d i s t ( q ，n ) d i s t ( q ，n ) 其中，距离函数d i s t ( q ，p ) 表示对象q 到p 的距离。 最小限定矩形m b r 是包含对象或予结点的最小矩形，根据此性质，定理2 1 中 的n 可以是结点或具体对象，如图2 2 。 定理2 1 - 说明了对象q 到m b r 的距离肯定要小于q 到此m b r 内的对象的距离。 注意，找到最近的m b r 并不代表最近邻就在此m r 内。见图2 3 ， d i s t ( q ，n 1 ) d i s t ( q ，p 2 ) ，即结点n 1 距离q 近，但是q 的最近邻是n 2 中的p 2 ，而非n l 中的p l 。 *n 什 圈2 2 ：定理2 1 示意图图2 3 ：最近邻不在距q 最近的m b r 内 为了充分利用r t r e e 的定理2 1 来做查询，方法是引入优先队列 3 。优先队列中 的元素以一个二元组表示 ，p o i m e r 指向最小限定矩形，d i s t a n c e 表示 查询对象q 距此m b r 的距离，当为叶结点时，p o i n t e r 是具体对象的标识符，d i s t a l l c e 是q 到具体对象的距离。优先队列是在队列的基础上加上一个限制条件，即元素按照 到q 的距离升序排列。每次查找时，均从队首开始。优先队列中的结点在到达队首之 前不需要被查找。 设q 为查询对象，最初，扫描整个索引结构，建立优先队列：然后把队首元素展 开( 即把队首的m b r 展开) ，再次插入优先队列，直到队首元素为对象，则找到q 的最近邻。当查询对象q 是一个点的时候，这个过程也可以描述如下( 图2 4 ) 。首先 确定q 所在的叶子结点，然后想象有个以q 为圆心的圆向外扩展，这个圆称搜索区域， 每当圆碰到一个结点的边界时，这个结点所包含的子结点都放入队列，而当碰到的是 对象的时候，此对象即为q 的下一个邻居。 图2 4 ：找到邻居p 后的查询过程 网格表示叶子结点，浅色阴影部分为搜索区域，深色阴影表示在优先队列中下次要查找的结 点。 注意当圆碰到一个结点或一个对象时，必须确保这个结点或对象已经在优先队列 里面，即其父结点已经被查找过并插入队列。 在算法中考虑对象的般性，即对象不是点，可以是线段、多边形等等，则r _ t r e e 的叶子结点中存储的是对象的m b r 。 r t r e e 上的最近邻查询算法描述如下【3 】： f i 加一n n ( q u e r y o b j e c t ，r - 订e e ) ( 1 ) q u e u e n e w p r i o r i t y ( ) ( 2 ) e n q u e u e ( q u e u e ，r t r e e r o o t n o d e ，o ) ( 3 ) w h i i en o ti s e m p t y ( q u e u e ) d o ，初始化优先队列 ，r t r e e 的根结点入队 队首元素出队，此时队首元素是距离查询对象q 最近的结点或对象 ( 4 ) e l e m e n t d e q u e u e ( q u e u e ) ( 5 )i fe l e m e n ti sa no b j e c to ri t sb o u n d i n gr e c t a n 9 1 et h e n ，队首是对象的m b r ，则把对象插入队列 ( 6 )i fe l e m e n ti sm eb o u n d i n gr e c t a n g l eo fo b j e c t a n dn o t i s e m p t y ( q u e u e ) a n dd i s t ( q u e r y o b j e c t ，0 b j e c t ) f i r s t ( q u e u e ) k e yt h e ( 7 ) e n q u e u e ( q u e u e ，o b j e c t ，d i s t ( q u e r y o b j e c t ，0 b j e c t ) ) ( 8 ) e l s e 是具体对象，即为所求最近邻 ( 9 ) r e p o r te l e m e ma st h en e x tn e a r e s to b j e c t ( 1 0 )e n d i f ( 1 1 )e l s e i f e l e m e n ti sal e a f n o d et h e n ，队首是叶子结点，把其中的每个对象m b r 插入队列 ( 1 2 )f o re a c he n t r y ( o b j e c t ，r e c t ) i nl e a f n o d ed o ( 13 ) e n q u e u e ( q u e u e ，【o b j e c t 】，d i s t ( q u e r y o b j e c t ，r e c t ) ) ( 1 4 )e n d d o ( 1 5 )e l s e 队首是非叶结点，则把其中的每个子结点m b r 插八队列 ( 1 6 )f o re a c he n t r y ( n o d e 皿c t ) i nn o d ee l e m e n td o ( 1 7 ) e n q u e u e ( q u e u e ，n o d e ，d i s t ( q u e r y o b j e c t ，r e c t ) ) ( 1 8 )e n d d o ( 1 9 )e n d i f ( 2 0 ) e n d d o 此算法首先初始化优先队列( 第1 行) ，然后把r t r e e 的根结点插入队列( 第2 行) ，此时整个队列只有一个元素，即队首根结点。把队首元素展开，其中的每个子 结点m b r 都重新插八队列，重复这个过程( 第3 2 0 行) ，直到队首元素是具体对象， 其问队首元素始终距离查询对象最近。 注意第2 行中入队的时候并不是真的需要计算真实距离，因为根结点会先出队计 算。第9 行找到下一个邻居。第6 7 行表示队首为对象的m b r 且q 到此m b r 距离 大于队首元素到q 的距离，则重新插入优先队列。第1 1 1 4 行和第1 6 1 8 行分别表示 了队首为叶子结点和非叶结点时的插入操作。 阻上给出了查找最近邻的算法，当需要查找k 近邻的时候，算法与此类似，只是 要添加一个计数变量，当从队首开始有连续的k 个具体对象时算法结束。 2 1 3 例子 2 1 2 介绍了在r _ t r c e 上的最近邻查询算法，下面给出具体例子说明查询过程。 假设要查找图2 1 中查询对象q 的三个最近邻，目标对象是存储在r 。t r e e 中的线 段，查询对象q 是点对象。下面给出算法的步骤和每个步骤优先队列中的内容。 表21 ：r _ i r e e 中查询对象q 到线段及限定矩形的距离 m b rd i s t 凡 r r 2 r 。 如 心 o o o 1 3 1 l 0 4 4 ( a ) q 到线段和线段m b r 的距离( b ) q 到结点m b r 的距离 查询对象q 到每个线段和线段m b r 的距离由表2 1 ( a ) 给出，( b ) 是查询对象q 到 结点m b r 的距离。线段和m b r 在优先队列中按q 到它们的距离升序排列。线段的 m b r 通过线段两端点的坐标确定，在下文中以标号加括弧表示，如f h 。以娲的入队 为算法的开始，下面步骤为： ( 1 ) d e q u e u e 凡，e n q u e u e r l 和r 2 ，q u e u e ： ( r 】，0 ) ，( r 2 ，o ) ) 。 ( 2 ) d e q u e u e r l ，e n q u e u er 3 和r 4 ，q u e u e ： ( r 2 ，0 ) ，( r 4 ，1 1 ) ，( r 3 ，1 3 ) 。 ( 3 ) d e q u e u er 2 ，e n q u e u e r 5 和心，q u e u e ： ( r 5 ，0 ) ，( 凡，1 1 ) ，( r 3 ，1 3 ) ， 限6 ，4 4 ) ) 。 ( 4 ) d e q u e u e r 5 ，e n q u e u e 【c 】和【i 】( 对象c 和i 的限定矩形) ，q u e u e ： ( i 】，0 ) ， ( r 4 ，1 1 ) ，( r 3 ，1 3 ) ，( r 6 ，4 4 ) ，( c 】，5 3 ) ) 。 ( 5 ) d e q u e u e i 】，q 到i 的距离2 1 ，大于q 到r 4 的距离，所以e n q u e u e i ， q u e u e ： ( r 4 ，1 1 ) ，( r 3 ，1 3 ) ，( i ，2 1 ) ，( 心，4 4 ) ，( c ，5 3 ) 。 ( 6 ) d e q u c u er 4 ，e n q u e u e d 】，吲和 h 】，q u e u e ： ( r 3 ，1 3 ) ，( h ，1 7 ) ，( i ，2 1 ) ， ( 【d 】，3 0 ) ，( k ，4 4 ) ，( 【c 】，5 3 ) ，( 【乩7 4 ) ) 。 ( 7 ) d e q u e u er 3 ，e n q u e u e a 和【b 】，q u e u e ： ( 【a 】，1 3 ) ，( h 】，1 7 ) ，( i ，2 1 ) ， ( b 】，2 7 ) ，( d ，3 0 ) ，( k ，4 4 ) ，( c ，5 3 ) ，( 【吐7 4 ) 。 ( 8 ) d e q u e u e a 】，q 到a 的距离1 7 ，不大于q 到 1 1 的距离，所以得到最近邻a ， q u e u e ： ( h ，1 7 ) ，( i ，2 1 ) ，( 【b 】，2 7 ) ，( 【d ，3 0 ) ，( r 6 ，4 4 ) ，( c 】，5 3 ) ，( g 】，7 4 ) ) 。 ( 9 ) d e q u e u e 嘲，q 到h 距离1 7 ，不大于q 到i 的距离，所以h 是第二近邻， q u e u e ： ( i ，2 1 ) ，( 【b 】，2 7 ) ，( 【d 】，3 0 ) ，( 心，4 4 ) ，( c 】，5 3 ) ，( n7 4 ) 。 ( 1 0 ) d e o u c u ei ，得到第三近邻，算法结束。 注意到直到算法结束，仍在优先队列里面，没有展开其中内容。算法不需要 查找q 到每个对象的实际距离，即通过剪枝提高了效率。 同时再注意到，当最近邻被找到以后，只需要花较少的开销就能找到第二近邻和 第三近邻。根据这一点，作静态k 近邻查询时，同样利用优先队列，找到从队首开始 的连续的k 个对象即找到了k 近邻，查找的效率要远远优于每个最近邻依次查找。 2 2 传统移动对象连续k 近邻查询 在详细介绍了静态最近邻查询的基础上，下面着重介绍传统的移动对象连续k 近邻查询，首先给出连续查询的定义： 定义2 2 ：查询对象q ，目标对象舶i 0 ，n 】，n k 。刘象q 和p i 均在作匀速 直线运动，时间间隔t ，查询对象q 每隔t 便查询一次k 近邻，则称这种一系列的 查询为移动对象的连续k 近邻查询。 在介绍查询之前，要先考虑空间索引技术。空间索引技术是通过对存储在介质上 的空间数据的描述，建立空间数据的逻辑记录与物理记录之间的对应关系，最终目的 是提高系统对空间数据获取的效率，它是快速查询、显示、更新地理空间数据的重要 指标【2 。 查询对象和目标对象都为静态时，利用r t r e e 的性质，可以通过剪枝高效查找查 询对象q 的k 近邻，但当目标对象为动态时，r t r e e 已不能满足查询要求，这时需要 考虑移动对象的索引技术。 移动对象的索引技术可以分为两类【3 7 】：( 1 ) 对移动对象历史位置的索引；( 2 ) 对移动对象当前和未来位置的索引。移动对象的历史位置轨迹可以看作是带有时间特 性的对象序列，对象间关系可以用静态关系模拟。而结合实际应用，目前研究较多的 是对移动对象当前和未来位置的索引。本文要求的索引结构也为后者。 对移动对象未来位置的索引，按未来轨迹是否已知可分为两种：( 1 ) 预知对象未 来轨迹的索引结构；( 2 ) 对象未来轨迹未知的索引结构。结合这两种索引结构，传统 的动态连续k 近邻查询可以分为两类：( 1 ) 预知对象运动轨迹的连续k 近邻查询；( 2 ) 对象运动轨迹未知的连续k 近邻查询。下面分别对这两种查询作介绍。 2 2 1 运动轨迹已知的连续k 近邻查询 由于预知所有对象的运动轨迹这个特殊性，这类情况下的最近邻查询也有其不同 之处。一般预知对象的运动轨迹，就可以存储每个目标对象的运动轨迹函数 1 7 ，3 8 ，3 9 。见图2 5 ，可以有三种不同的查询：时间片查淘q i ，即固定的区域查询； 窗口查询q z ，即移动的区域查询；而移动查询q 3 ，是区域移动且大小改变的查询。 这类查询的最新的研究成果是s t m p e s 【4 0 】，它是由j m p a t e l 等在2 0 0 4 年提出 的一种基于0 u a d t r e e 的索引结构，用于对移动对象预测轨迹的检索。采用对偶变换 ( d u a l i t y t r a n s f o n n a t i o n ) ，将二维空间中对象移动信息转换为四维空间中一个点对象， 采用q u a d t r e e 这种非平衡树结构对四维空间中的对象进行索引，从而取得对预测轨 迹的索引结构。其查询方式与上述类似。 q l 饧 q 3 图25 ：运动轨迹已知的查询 对于连续的k 近邻查询，y fl i 等在【1 6 】中充分利用了已知的对象运动函数，提 出不需要监视所有的k 个对象，只要考虑第k 个邻居，因为邻居的变化是心m 变化 的必要条件。 y f “把移动对象的原始坐标( 图2 6 ( a ) ) ，转化成“时间一距离”坐标( 图2 6 ( b ) ) 。 图2 6 ( b ) 中，横轴是时间t ，纵轴是相应时间下目标对象到q 的距离。称第k 个邻居 变化的曲线为海滩线( b e a c hl i n e ) ，见图2 ，6 ( b ) 中的实线，海滩线始终描述了第k 个 邻居。可以看到：在海滩线下方的对象属于卧n 。 图2 6 给出了求查询对象q 的最近的两个邻居的过程示意图，通过图形，可以看 出在 o ，t 1 上q 的2 n n 依次是p l 和p 2 ；在 1 l ，t 2 】上是p l 和p 3 ；在 t 2 ，t 3 上是p 3 和p 1 ； 在【t 3 ，蜘上是p 3 和p 2 ；在【t 4 ，5 上是p 2 和p 3 。 y d p 3 p 2 p l ( a ) 二维空间坐标 ( b ) 各移动对象的运动轨迹 图2 6 ：转化结构示意图 预知运动轨迹有其