硕士论文空间移动对象的最近邻查询方法研究——移动对象连续k近邻查询

1、Y 911771分类号（中图法） TP3111 UPC (DDC) 005 密级 内部 . 论文作者姓名 吴林燕 学号0330703008单位河海大学 .论文中文题名空间移动对象的最近部查询方法研究.论文中文副题名移动对象连续k近邻查询.论文英文题名 Research on Nearest Neighbor Query for Spatial Moving Objects .论文英文副题名 Continuous k-Nearest Neighbor Query for Moving Objects论文语种汉语论文摘要语种汉、英论文页数46论文字数 (万） 论文主题词地理信息系统、连续k近邻查询

2、、空间索引、R-tree、TPR-tree .申请学位级别 工学硕士 专业名称计算机软件与理论研究方向空间数据库指导教师姓名 朱跃龙教授 导师单位 河海大学计信学院冯钩副教授导师单位 河海大学计信学院论文答辩日期2006年6月8曰AbstractWith the rapid development of GPS and wireless communication, it is easy to trace and record the positions of moving objects. The research on nearest neighbor queries， especiall

3、y the nearest neighbor queries of moving query and target objects, is arousing more and more interests and attentions.According to the track of moving objects, there is two different kinds of nearest neighbor queries of moving query and moving target objects. One of them, the continuous k-nearest ne

4、ighbor queries without track is more popular in application. The traditional algorithm of continuous k-nearest neighbor queries is a series of static k-nearest neighbor queries, using snapshot in TPR-tree. This algorithm has a problem of repeating computation. It has to re-search all the k neighbors

5、 when query every time.This thesis improves the traditional algorithm of k-nearest neighbor queries on moving objects. Based on the truth that the results of every continuous two queries are related to each other when the interval of continuous queries is in some region, we present a candidate set t

6、o replace the whole target set. In this way, we can reduce the search region and enhance the query efficiency. Meanwhile, the candidate set can be diminished again by judging the trend of moving.Finally, we compare the improved algorithm to the traditional algorithm. The experiment proves the stabil

7、ity and efficiency of the improved algorithm is better than the traditional algorithm.Keywords: Geographical Information System，continuous k-nearest neighbor query， spatial index R-tree, TPR-tree第一章绪论研究背景与意义地理信息系统（Geographical Information System, GIS)是20世纪60年代迅速 发展起来的集地理空间数据处理与计算机技术于一体的一门边缘技术学科，是指在计

8、 算机软硬件下，来集、存储、管理、处理、检索、分析和显示空间物体的地理分布以 及与之相关的属性，为地理研究和地理决策等服务的计算机技术系统1。如今，GIS 正形成完整的技术系统并逐渐建立起独立的理论体系。地理信息系统的主要任务之一是有效检索空间数据以及快速响应不同用户的查 询2。其中，最近邻（the Nearest Neighbor，NN)查询是经常遇到的一类查询，它 用来找出空间中距离指定点最近的对象，即找到其最近邻居。最近邻查询与传统数据 库的查询不同，例如，要查找人口超过10万的城市有哪几座，通过传统数据库可以 很方便得到查询结果，但若是要求查找距离南京最近的人口超过10万的城市，复杂

9、性便大大增加。首先要找到满足人口要求的所有城市，然后还要需要计算毎个城市距 离南京的距离，而最坏情况是找到最后的城市才满足要求。传统数据库管理这类空间 地理信息有一定局限性，对于此类涉及地理信息的查询，一般方法是选用适当的索引 结构。随着计箅机技术、信息技术、空间技术的发展，地理信息系统的应用越来越广泛。 而全球定位系统（Global Positioning System，GPS)的出现，更是提高了 GIS的动态 分析能力。GPS是20世纪70年代由美国陆海空三军联合研制的新一代空间卫星导航 定位系统，由于其所具有的全天候、高精度和自动测量等特点，作为先进的测量手段 和新的生产力，己经融入了国

10、民经济建设、国防建设和社会发展的各个应用领域，并 开始逐步深入人们的日常生活。GPS系统的高精度、全天候和全球性定位，使得跟踪并记录移动对象的位置变得 可行，针对移动对象的最近邻查询越来越被人们关注。最近邻查询在智能交通系统、 科学调查、军事、资源管理中有广泛的应用前景，是空间访问方法及查询方法的研究 热点之一。例如，在智能交通系统中，查找离移动的出租车最近的加油站，或者查找 从A地到B地沿途最近的饭店等等。最近邻的数目可以是一个，也可以是k(kl)个，若kl则称k近邻。例如， 在地理信息系统中，对一个特定的位置或目标，要求系统査找并返回五个离它最近的 对象；在智能交通系统中，查找无人驾驶公交

11、车周围最近的10辆汽车等等。本文主 要硏究的是移动对象的连续k近邻査询。最近邻查询是k近邻查询的一种特殊情况，一般研究都是从最近邻开始，然后扩 展到k近邻。针对最近邻的查询，近几年已有不少文章做出研究，如最近邻查询311、 连续最近邻查询U218、逆最近邻査询1922等等。但究其本质，可以根据空间对 象（查询对象和目标对象）在空间中随时间变化的状态（如固定或移动）分为四大类， 如表1.1所示。表1.丨：最近邻查询分类码定移动固逝静-态査询查询对象 路线己知查_对象 路线小矩:移动査刑对象_定 a标对象栘动a査ifl对象 il标对象均移动其中，1)、2)两类查询对象固定，需要查找的最近邻为静态或

12、移动；3)、4)则针对移动查询 对象，査找静态或移动的最近邻。这里的移动又可以分为二维空间中的自由移动或是沿着一定轨 迹移动两种类型。下面分别介绍这四类查询的研究现状：(1)静态查询。这类查询的研究比较成熟，目前国内外已有不少相关文献 36，2331。普遍的方法是利用特定的空间索引结构（如R-tree23、X-tree24, M-tree25#)的特性，结合一定的辅助数据结构进行查找。计算机将存储器分为内存、外存，而访问外存所花费的时间是访问内存的千倍以 上。在实际的GIS应用中，大量的空间数据是存储在外存上的，如果对外存上数据的 位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这

13、种访问磁盘的 代价就会严重影响系统的效率-因此，GIS必须将数据在磁盘上的位置加以记录和组 织，通过内存中的一些计算来取代对磁盘漫无目的的访向，以便提高系统效率。一个 实际的GIS涉及各种海量的复杂空间数据,数据的索引对于系统的处理效率至关重要 32。美国加州大fGuttman教授在1984年提出的一种空间索引结构R-tree,现 已成为空间数据库索引中应用最广泛的算法之一。R-tree较好地解决了许多传统算法 未能解决的空间数据的索引问题。静态查询最为典型的研究是等在3中提出R-tree索引结构结合优 先队列的方法。这个方法使得查询时，不需要遍历所有的对象，通过利用剪枝策略提高查询效率。而且

14、根据优先队列的特性，对于查找k近邻效率更高。国内的一些学者则对索引结构作了不少改进。张苍等在27中提出QR-tree,先 对整个索引空间用四叉树进行划分，子索引再釆用R-tree,实质是将一棵“大”的 R-tree分解成多棵“小”的R-tree,将查询尽可能限定在局部空间区域，从而提高査 询性能；邱建华等在28中则在R*-tree基础上引入了四叉树，提出QR*-tree。R*-tree 是对R-tree的改进，R-tree的主要缺陷是结点的重叠，R*-tree则尽量减小结点间的重 叠面积。此外，国内的相关研究还有：张明波等在26中回顾了 R-tree的演变和发展； 刘宇等在29中提出了基于R-

15、tree的两个新的最近邻搜索剪枝策略；过志峰等在30 中提出了基于R*-tree的优化的空间査询系统框架设计；白玉琪等则在31中将R-tree 算法用于搜索引擎。查询对象固定、目标对象移动的最近邻査询，如“10分钟后距离某加油站 最近的汽车”，这类查询的关键是为移动的目标对象选择适当的索引结构，典型的方 法如等在11中利用TPR-tree索引结构来做査询。当把移动的目标对象索引 起来后，査询就可以参照静态查询的方法。这类査询有其特殊性，如查找医院周围最 近的一些救护车等等，目前的研究不是很多。目标对象为静态，查询对象移动的最近邻査询，主要应用在智能交通系统 中，如以饭店、加油站等为静态目标对象

16、，运动中的公交车、出租车为查询对象，查 询出租车行进路线上最近的加油站。这类查询又分为查询对象运动轨迹预知和未知两 类：当查询对象移动的轨迹预定时，这类查询需要为查询对象的每一个位置重复计算 它的k近邻。解决问题的关键在于：如何减少随着查询对象的移动而带来的重复计算。 目前有大量的研究对此进行探讨7,8，12-14,综合起来不外乎两点-利用査询对象的移动轨迹信息，减少重复计算。典型的研究是等在12 中提出的找到查询对象移动轨迹上的分割点的方法。这种方法主要目的是求连续最近 邻，如出租车从A地到B地，找出沿途的所有的最近加油站。对目标对象集进行预处理，从而利用预处理结果来满足査询要求。典型研究

17、是7,8，14中提出的voronoi方法。釆用voronoi方法预先划分目标对象区域，这样在 目标对象为静态的情况下，一旦路线给出，就能很快的给出每一段路线上的最近邻。对于査询对象移动轨迹不确定的情况，则需要从如何减小重复计算的角度考虑。 如Song在9中提出的利用前次查询结果来缩小下次查询范围的方法。MKolahdouzan等在7中提出的vorotioi方法同样也可用于査询对象移动轨迹不 定的情况，因为目标对象固定，且已经过预处理，一旦知道查询对象目前在哪个区域 内即可确定其最近邻。等则在10中提出当査询对象q仍在初始位置周围的一 定区域（有效区域）内，则最近邻结果不变。而这个有效区域可以通

18、过voronoi方法 来获得，这种方法同样通过减少更新次数来提高效率。这两个采用voromoi的方法同 样不适用求k近邻。(4)目标和查询对象均移动，这类查询的主要问题是计算量大，所有对象均移 动，不能很好掌握更新时间。这一类的研究不是很多，而且一般都假设所有移动对象 的运动函数已知。等在16中充分利用了已知的对象运动函数，提出不需要监 视所有的k个对象，只要考虑第k个邻居，因为它的变化是_变化的必要条件。但是在实际的应用中，移动对象的轨迹往往不可预知，如公路网上的汽车，这时 就需要找到一种更有效的查询方法。等在33中讨论了公路网上的移动对 象查找移动的k近邻的方法，采用C/S体系结构。对于查

19、询对象q发出的査询请求 kNN，服务器端给出一个最近邻候选集合niNN(m咨k)，而由客户端完成对候选集的 维护，即再计算候选集中目标对象到查询对象的距离，给出kNN，然后周期性地更 新候选集，以避免查询结果的不精确。该方法以搜索候选集來替代搜索整个目标对象 集，同时由求出的最近邻位置与实际位置之间的误差来决定更新，以此提高搜索效率 和精度。但是这种方法的更新时间难以把握，若更新时间过短，则计算量太大；若更 新时间过长，则计算结果误差增大。随着卫星定位系统（如GPS)和无线通讯技术的快速发展，跟踪并记录移动对象 的位置变得可行，移动对象的最近邻查询成为最近邻査询的重点和难点，特别是目标 对象和

20、查询对象均移动的情况。而在实际应用中，目标对象和查询对象均移动的最近 邻查询往往与连续查询结合在一起，这就是本文要研究的空间移动对象的连续k近邻 査询。本文研究空间移动对象的连续k近邻查询方法，即查询对象和目标对象均移动。 同时，研究的并不只是某一时刻的k近邻查询方法，而是针对移动査询对象的连续k 近邻查询，如每隔一分钟查找一下移动车辆的k近邻。假设各移动对象均在二维空间 运动，且速度的大小和方向不变。考虑到预知每个对象运动轨迹的查询局限性太大，本文研究移动对象运动轨迹未 知的查询，更贴近于真实应用。移动对象连续k近邻查询的研究有着广泛的应用前景, 如智能交通中，无人驾驶的公交车，连续判断其周

21、围的交通状况，以做出正确的路线 选择：军事上可应用连续的k近邻查询来协同作战；另外还可用于海洋导航、移动自 组网络的路径选择等等。传统的移动对象k近邻查询，采用TPR-tree索引结构，査询方法类似于静态k 近邻查询。而作连续查询时，釆用快照方式，由一系列静态查询构成，即每一次都重 新做了一遍静态的k近邻搜索.本文改进了传统的移动对象k近邻査询算法，使之更适用于做连续查询。主要思 想是考虑到在一定时间内，查询对象的k近邻始终在查询对象周围的一定范围内，此 范围外的对象在这段时间内都不需要考虑。改进算法通过缩小搜索范围来提高查询效 率。本文构建了三个数据集来比较改进算法和传统算法的优劣。第一个数

22、据集中对象 均匀分布，同时每个对象的速度相同（包括大小和方向）；第二个数据集的对象也是 均匀分布，但速度为随机值；第三个数据集的对象和对象的速度均取随机值，以此来 模拟现实世界中的真实移动对象。比较结果表明，改进算法更有利于作移动对象的连续k近邻查询，且查询效率髙 于传统算法。本章是绪论部分，主要介绍最近邻查询的研究背景和意义，并介绍了目前国内外 的研究现状，简单分析了各种类型的k近邻查询方法的优点和不足，最后给出了本文 研究的主要内容，包括研究目标和研究成果。第二章移动对象连续k近邻查询的传统算法，由于这种查询以静态k近邻査询为 基础，先详细介绍了静态最近邻查询，然后分别介绍移动对象运动轨迹

23、预知和未知的 连续k近邻查询第三章移动对象连续k近邻査询的改进算法，在传统算法的基础上引入候选集， 并讨论候选集的更新和精化，最后给出了査询的算法描述。第四章实验比较移动对象连续k近邻查询的传统算法和改进算法，并分析两个算 法各自的优劣。第五章总结和展望，总结全文工作，并对进一步的工作作出展望。第二章移动对象连续k近邻查询的传统算法本章主要讨论移动对象连续k近邻查询的传统算法，这种查询按照移动对象的运 动轨迹分为两类：移动对象运动轨迹预知的连续k近邻查询和运动轨迹未知的连续k 近邻查询。本文侧重研究运动轨迹未知的连续k近邻查询，而这类查询以静态最近邻 查询为基础，因此本章首先介绍静态最近邻查询

24、。静态最近邻査询是其它各种最近邻查询（包括移动对象最近邻查询）的基础，而 在介绍静态最近邻查询之前首先要介绍空间索引技术，它是快速查询、显示、更新 地理空间数据的重要指标。空间对象的数据一般可用多属性的一条记录来描述，但因为这类数据的数据量 大、结构和关系复杂，传统的数据库系统不能有效地支持对这类数据的处理：空间操 作与计算比传统的关系运算代价高，不能像传统数据库那样用某种命令对空间目标进 行分类、排序34。因此，空间数据处理必须采用特定的索引技术。以传统的索引技术观点来看，可以把空间索引技术大致分为四大类45:基于B 树、基于Hashing、基于二叉树和基于空间填充曲线。按照建立索引时，划分

25、区域是 否与空间对象的分布特征有关，空间索引又可以分为两大类：（1)划分区域与空问对 象分布特征无关；（2)划分区域与空间对象的分布特征有关。前者包括网格索引、四 叉树；后者包括 BSP-tree、KD-tree、KDB-tree、R-tree 及其变种、Cell-tree、X-tree 和TV-tree等众多空间索引。在这众多空间索引结构中，又以网格空间索引、四叉树系列空间索引和R-tree 系列空间索引最为常见。其中，R-tree具有很强的灵活性与可调节性，建树过程中无 需预知整个空间对象所在的空间范围，同时它具有较高的执行效率，被公认为是较好 的空间索引结构，己经得到广泛应用。下面详细介

26、绍R-tree索引结构。 R-tree索引结构R-tree (图2.1)是一种具有层次结构的平衡树，它是B+-tree的扩展3。其构建 思想是以最小限定矩形（minimum bounding rectangle, MBR)递归地对数据集空间按 照“面积”规则进行划分2。R-tree中非叶结点代表一个划分的空间区域，即一个矩 形空间区域；叶子结点包含的矩形区域对应空间对象的MBR。构造矩形空间的原则 是：（1)矩形之间尽可能少重叠；（2)矩形尽可能包含更多的空间对象；（3)矩形可以嵌套，即矩形中可以包括更小的矩形。R-tree的结点是一个二元组,其中pointer是指向子树的指针，而 key是最

27、小限定矩形，包含pointer指向的子树中所有对象的MBR。在R-tree的叶子 结点中，pointer是具体对象的标识符。每个结点能包含的对象或子结点的最大值称为结点容量，取值范围为m, M。 M取决于数据在硬盘驱动器上的存储参数，如磁盘页面大小或容量，通常选取使得 一个结点填充满（或小于）一个磁盘页的数值。当结点中的对象数超过M时，就需 要分裂，R-tree采用使分裂产生的两部分面积之和最小的分裂方案。m取决于数据库 的操作，若数据库仅仅（或大部分）只需要查询而较少更新，m取较大的值，使R 树高度小，从而搜索快，但易引起溢出或下溢；若数据库需要经常更新或调整则in 取小值。通常m在2M/2

28、之间选择。R-tree允许结点相互重叠36,这种重叠可以使R-tree保持较高的空间利用率（内 存、磁盘）和保持树的平衡。但另一个方面，过多重叠可能会造成查询效率的降低， 最坏的情况下对某一对象的查询可能造成对整个树的搜索。(a)线段的空间位置和其MBR(b) R-tree索引结构图2.1:线段的R-tree索引结构R-tree的空间划分与数据结构如图所示。进行空间检索时，首先判断哪些矩 形区域与查询对象相交，再进一步判断落在这些矩形区域中有哪些被检索的对象。查找效率主要取决于R-tree的深度及子树索引空间的重叠程度34 R-tree的深 度越低，查找过程中访问的结点数就越少，查询效率越高；

29、子树索引空间的重叠越少， 査找过程中遍历的子树就越少，访问的结点数也就越少，查询效率也就越好。由于R-tree的深度只与空间对象的数量有关，所以，R-tree构造的关键就是尽量 减少子树索引空间的重叠。在R-tree的构造算法中，Giittman将索引空间的“面积” 作为惟一的度量，空间对象总是插入使索引空间“面积”增量最小的子树中，以期尽 量缩小索引空间的重叠“面积”，减少索引空间的重叠程度及缩短查找路径。但是， 由于构造算法的动态性，R-tree不可避免地会产生大量的重叠和死空间”（不包含 空间对象的索引空间），从而导致效率下降。综上所述，R-tree存在的问题可以归纳为两方面由于空间对象

30、千姿百态，其索引空间经常重叠，且其重叠的程度随着数据 量或空间维数的增加而增加。索引空间的重叠必然造成树的深度及存储空间的增加， 从而导致遍历时间增加查询效率下降；在动态构建R-tree时会产生大量“死空间”（不包含空间目标的索引空间)， 造成存储空间的浪费，产生无效的遍历。虽然R-tree存在上述问题，但是，由于其具有很强的灵活性与可调节性，建树过 程中无需预知整个空间对象所在的空间范围，同时还具有较高的执行效率，R-tree及 其变种现已成为空间数据库索引中应用最广泛的索引结构之一。最近邻査询主要是距离的査询，下面首先给出距离函数的定义： 定义2.1:距离函数Dist(q，p)表示q到P的

31、距离，其中，q是具体对象，p是具体 对象或R-tree中的结点MBR。若p是具体对象，Dist(q,p)是对象间的欧氏距离；若 P是MBR,则Dist(q,p)是q到p的最小距离。R-tree索引结构中，划分区域与空间对象的分布有关，直观地讲，即同一个MBR 中的元素从空间上来看是聚在一起的。在作最近邻查询时，可以充分利用这些已划分 好的区域，先找到距离查询对象最近的一个区域，则所求的结果很有可能就在这个区 域里。根据这个特点，有定理2.13:定理 2.1: VN, N 是 R-tree 中结点，3n , neN,都有 Dist(q，N) 5 Dist(q，n)，其中，距离函数Dist(q，p

32、)表示对象q到P的距离。最小限定矩形MBR是包含对象或子结点的最小矩形，根据此性质，定理2.!中 的n可以是结点或具体对象，如图2.2。定理说明了对象q到MBR的距离肯定要小于q到此MBR内的对象的距离。 注意，找到最近的MBR并不代表最近邻就在此MBR内。见图2.3,Distq,Ni)Dist(q,p2),即结点 N距离 q 近但是 q 的最近邻是中的P2，而非Ni中的pi。图2.2:定理示意图图2.3:最近邻不在距q最近的MBR内为了充分利闻R-tree的定理来做查询，方法是引入优先队列3。优先队列中 的元素以一个二元组表示，pointer指向最小限定矩形，distance表示 查询对象q

33、距此MBR的距离，当为叶结点时，pointer是具体对象的标识符，distance 是q到具体对象的距离。优先队列是在队列的基础上加上一个限制条件，即元素按照 到q的距离升序排列。每次查找时，均从队首幵始优先队列中的结点在到达队首之 前不需要被査找。设q为查询对象，最初，扫描整个索引结构，建立优先队列；然后把队首元素展 幵（即把队首的MBR展开），再次插入优先队列，直到队首元素为对象，则找到q. 的最近邻。当查询对象q是一个点的时候，这个过程也可以描述如下（图2,4)。首先 确定q所在的叶子结点，然后想象有个以q为圆心的圆向外扩展，这个圆称搜索区域， 每当圆碰到一个结点的边界时，这个结点所包含

34、的子结点都放入队列，而当碰到的是 对象的时候，此对象即为q的下一个邻居。图2.4:找到邻居P后的査询过程 网格表示叶子结点，浅色阴影部分为搜索区域，深色阴影表示在优先队列中下次要査找的结点0注意当圆碰到一个结点或一个对象时，必须确保这个结点或对象已经在优先队列 里面，即其父结点已经被查找过并插入队列。在算法中考虑对象的一般性，即对象不是点，可以是线段、多边形等等，则R-tree的叶于结点中存储的是对象的MBR。R-tree上的最近邻查询算法描述如下3: Find_NN(QueryObject,R-tree) Queue NewPriority()EnQueue(Queue,R-tree.Roo

35、tNode,0)while not IsEmpty(Queue) do /队首元素出队，此时队首元素是距离查询对象q最近的结点或对象 Element 一 DeQueue(Queue) if Element is an object or its bounding rectangle then队首是对象的MBR，则把对象插入队列 if Element is the bounding rectangle of Object and not IsEmpty(Queue)and Dist(QueryObject,Object)First(Queue).Key then EnQueue(Queue,Ob

36、ject,Dist(QueryObject,Object) else/是具体对象，即为所求最近邻Report Element as the next nearest object endifelseif Element is a leaf node then/初始化优先队列 /R-tree的根结点入队 9)0) 1)/V r, xly2 3 4 5MBR插入队列 for each entry(Object,Rect) in leaf node doEnQueueQueue,Object,Dist(QueryObject,Rect)else /队首是非叶结点，则把其中的每个子结点MBR插入队列

37、for each entryNode,Rect) in node Element doEnQueue(Queue,Node,Dist(QueryObject,Rect)endif (20) enddo此算法首先初始化优先队列（第1行)，然后把R-tree的根结点插入队列（第2 行)，此时整个队列只有一个元素，即队首根结点。把队首元素展幵，其中的每个子 结点MBR都重新插入队列，重复这个过程（第320行)，直到队首元素是具体对象， 其间队首元素始终距离查询对象最近。6) 9)注意第2行中入队的时候并不是真的需要计算真实距离，因为根结点会先出队计 算。第9行找到下一个邻居。第67行表示队首为对象的

38、MBR且q到此MBR距离 大于队首元素到q的距离，则重新插入优先队列。第1114行和第1618行分别表示了队首为叶子结点和非叶结点时的插入操作。以上给出了查找最近邻的算法，当需要查找k近邻的时候，算法与此类似，只是 要添加一个计数变量，当从队首开始有连续的k个具体对象时算法结束。介绍了在R-tree上的最近邻查询算法，下面给出具体例子说明查询过程。 假设要查找图中查询对象q的三个最近邻，目标对象是存储在R-tree中的线 段，查询对象q是点对象。下面给出算法的步骤和每个歩骤优先队列中的内容。表2.1: R-tree中查询对象q到线段及限定矩形的距离 R 37305447)g 125347710

39、787986171 & 145548812ob abed efoohi0 0 0 n U 0MBR Dist. (a) q到线段和线段MBR的距离 （b) q到结点MBR的距离查询对象q到每个线段和线段MBR的距离由表2.Ka)给出，（b)是査询对象q到 结点MBR的距离。线段和MBR在优先队列中按q到它们的距离升序排列。线段的 MBR通过线段两端点的巫标确定，在下文中以标号加括弧表示，如h。以Ro的入队 为算法的开始，下面步骤为：DeQueueRo, EnQueue Ri 和 R2 Queue： (R】，0)（R20)。DeQueueRi, EnQueue R3和 R4，Queue： (R2

40、, 0), (R4, 11), (R3, 13) DeQueueR2, EnQueueR5和 Rg, Queue： (R5, 0), (R4, II), (R3, 13), (R6,44)DeQueueRs, EnQueue c和i(对象 c 和 i 的限定矩形)，Queue： (i, 0), (R4，11), (Rj, 13), (Re, 44), (c，53)。DeQueue i, q到i的距离21,大于q到R4的距离，所以EnQueue i, Queue： (R4,11)- (R3,13), (i，21) (R6,44), (c53)。DeQueue R4, EnQueue d, g和h

41、，Queue： (R3, 13), (h, 17), (i,21), m, 30), (R,44), (c，53), g,74)DeQueue R3, EnQueue a和b，Queue： (a, 13), (h，17)，(i,21),b, 27), (d,30), (R6,44), (c, 53), (g,74)Dequeue a, q到a的距离17，不大于q到h的距离，所以得到最近邻a， Queue： (h, 17), (i, 21). (b，27), (d, 30), (Re, 44)，（c，53), (g, 74) 。Dequeue h, q到h距离17,不大于q到i的距离，所以h是第

42、二近邻， Queue： (i，21) (b,27, (d，30), (Rs, 44), (c, 53), (g74)。DeQueuei，得到第三近邻，算法结束。注意到R直到算法结束，仍在优先队列里面，没有展幵其中内容。算法不需要 査找q到每个对象的实际距离.即通过剪枝提髙了效率。同时再注意到，当最近邻被找到以后，只需要花较少的开销就能找到第二近邻和 第三近邻。根据这一点，作静态k近邻查询时，同样利用优先队列，找到从队首开始 的连续的k个对象即找到了 k近邻，査找的效率要远远优于每个最近邻依次査找。k近邻查询在详细介绍了静态最近邻查询的基础上，下面着重介绍传统的移动对象迹续k 近邻查询，首先给出

43、连续査询的定义：定义2.2:査询对象q,目标对象Pi，ie0，n, nkk。对象q和pi均在作匀速直线运动，时间间隔At,査询对象q毎隔At便查询一次k近邻，则称这种一系列的 查询为移动对象的连续k近邻查询。在介绍查询之前，要先考虑空间索引技术。空间索引技术是通过对存储在介质上 的空间数据的描述，建立空间数据的逻辑记录与物理记录之间的对应关系，最终目的 是提高系统对空间数据获取的效率，它是快速査询、显示、更新地理空间数据的重要 指标m。查询对象和目标对象都为静态时，利用R-tree的性质，可以通过剪枝高效查找查 询对象q的k近邻，但当目标对象为动态时，R-tree已不能满足查询要求，这时需要

44、考虑移动对象的索引技术。移动对象的索引技术可以分为两类37: (1)对移动对象历史位置的索引；（2) 对移动对象当前和未来位置的索引。移动对象的历史位置轨迹可以看作是带有时间特 性的对象序列，对象间关系可以用静态关系模拟。而结合实际应用，目前研究较多的 是对移动对象当前和未来位置的索引。本文要求的索引结构也为后者。对移动对象未来位置的索引，按未来轨迹是否己知可分为两种：（1)预知对象未 来轨迹的索引结拘；对象未来轨迹未知的索引结构。结合这两种索引结构，传统 的动态连续k近邻查询可以分为两类：U)预知对象运动轨迹的连续k近邻查询：(2) 对象运动轨迹未知的连续k近邻查询。下面分别对这两种查询作介

45、绍。运动轨迹已知的连续k近邻查询由于预知所有对象的运动轨迹这个特殊性，这类情况下的最近邻查询也有其不同 之处。一般预知对象的运动轨迹，就可以存储每个目标对象的运动轨迹函数 17,38,39.见图15，可以有三种不同的查询：时间片查询Qi，即固定的区域査询： 窗口査询Q2,即移动的区域查询；而移动査询Q3,是区域移动且大小改变的査询。 这类查询的最新的研究成果是STRIPES40,它是由等在2004年提出 的一种基于Quadtree的索引结构，用于对移动对象预测轨迹的检索。采用对偶变换 (duality transformation)，将二维空间中对象移动信息转换为四维空间中一个点对象， 采用Q

46、uadtree这种非平衡树结构对四维空间中的对象进行索引，从而取得对预测轨 迹的索引结构。其查询方式与上述类似。图2.5:运动轨迹已知的查询对于连续的k近邻查询，等在16中充分利用了已知的对象运动函数，提 出不需要监视所有的k个对象，只要考虑第k个邻居，因为邻居的变化是_变化 的必要条件。把移动对象的原始坐标(图2.6(a)，转化成“时间一距离”坐标(图2,6(b)。 图2.6(b)中，横轴是时间t，纵轴是相应时间下目标对象到q的距离。称第k个邻居 变化的曲线为海滩线（beach line),见图2.6(b)中的实线，海滩线始终描述了第k个 邻居。可以看到：在海滩线下方的对象属于_q的最近的两

47、个邻居的过程示意图，通过图形，可以看 出在0，ti上q的2NN依次是和P2i在t|，t2上是Pl和P3:在t2，t3上是P3和P1; 在t3，t4上是P3和P2;在t4,t5上是P2和p3。p PiqcP3Xtl t2t3 t4 t5 tCb)各移动对象的运动轨迹 转化结构示意图,P2(a)：维空间坐标 预知运动轨迹有其特殊性，可以根据轨迹函数作特殊的查询，但在实际应用中， 更多的情况是不知道对象的运动轨迹，此时索引结构及查询方法都要发生改变，下面 介绍了未知运动轨迹情况下的连续k近邻査询。运动轨迹未知的连续k近邻查询当对象的运动轨迹未知时，可以在原始的二维空间索引数据，采用速度矢量将索 引结

48、构参数化，使得未来任何时刻的索引结构都能被得出37。TPR-tree (time-parameterized R-tree)就采用了这种方法，是一种非常直观的索引技术。 TPR-tree是Theodoridis等1996年在R树基础上提出的41 (2003年Tao等将之 扩展为TPR*-treell)，实现了对二维空间中自由移动对象的有效索引。TPR-tree是 考虑时间因素的R-Tree结构。它利用R*-Tree结构索引移动物体。在原有MBR的结 构基础上加上速度因素，引入VBR概念，即物体的MBR (最小包围矩形框）是动态 增加的，而其培加的速度由其所包围的矩形内节点的速度所决定，并取其极

49、值。索引结构本文研究的是移动对象随机运动时的连续fc近邻查询，需要对未来位置作索引， 且未来的位置轨迹未知，考虑到这些条件，本文来用TPR-tree索引结构。下面对其 作详细介绍。2.2.2.1 TPR-TPR-treeC图2.7)是一种针对连续移动物体设计的时空索引结构，它是具有R-tree 结构的平衡树，并在R-tree基础上引入了 VBR11。VBR指速度限定矩形（velocity bounding rectangle),由四元组组成First(Queue).Key then EnQueue(Queue,Object,Dist(QueryObject,Object)是具体对象，则得到所要

50、找的最近邻 Report Element as the next nearest objectendifelseif Element is a leaf node then/队首是叶子结点，把叶子结点中的每个对象的MBR插入队列 for each eiitry(Object,Rect) in leaf node doEnQueue(Queue,Object,Dist(QueryObject,Rect) enddo else/队首是非叶结点，把其中的每个子结点插入MBRfor each entry(Node,Rect) in node Element doEnQueue(Queue,Node,D

51、ist(QueryObj ect,Rect) 2021) endif22 23此算法与中静态最近邻算法类似，首先初始化优先队列，把TPR-tree的根结 点插入优先队列（第2行)。然后毎个查询时刻都做类似的算法查询（第323行)， 其中，第3行标记毎个查询时刻，第5行得到当前TPR-tree的快照，更新了优先队列-/初始化优先队列 /TPR-tree的根结点入队由于每个查询时刻都得到了当前优先队列的快照，即得到此时的TPR-tree索引结构，而在任意时刻，TPR-tree都可以被认为是一个特殊的R-tree,所以此时的最近 邻查询相当于在H-tree上进行，可以釆用优先队列的方法，逐层展开队首

52、MBR,直 到队首为具体对象，即找到最近邻。k近邻的査找即找到优先队列从队首开始的连续的k个具体对象。静态最近邻查询是各类最近邻査询（包括移动对象连续最近邻查询）的基础，本 章首先结合R-tree索引结构详细介绍了静态最近邻查询算法。然后讨论传统的移动对 象连续k近邻查询，传统移动对象连续k近邻查询分两类：移动对象运动轨迹预知和 移动对象运动轨迹未知，文中都作了介绍。本文的研究侧重点是移动对象运动轨迹未 知的连续k近邻查询，这类査询在TPR-tree索引结构基础上采用快照的方式，作一 系列静态k近邻査询。下一章讨论如何改进移动对象连续k近邻算法的查询效率。第三章移动对象连续k近邻查询的改进算法

53、空间移动对象的连续k近邻查询，指在査询对象和目标对象都移动的情况下，对 查询对象连续作其k近邻的查找。例如，在智能交通系统中，以无人驾驶的公交车为 查询对象，道路上的其它车辆为目标对象，每隔2分钟查找距离公交车最近的10辆 车。.传统的动态连续k近邻查询方法是采用的快照方式，相当于作了一系列的静态k 近邻查询，每次查询都要重新查找所有的k个邻居，存在重复计算的问题。本文下面 讨论改进的动态连续k近邻査询，期望能减少计算量，提高査询效率。对于连续的k近邻查询，需要从如何减少重复计算的角度考虑。Song在9中提 出了利用前次查询结果来缩小下次查询范围的方法，其中查询对象运动（且运动轨迹 未知）、g

54、标对象静止。Song的方法由下列的观察启发得到：两个査询对象qi、qz靠近，则它们的kNN 查询结果Si和S2必然相关，当已得到S1,则可少做很多工作得到S2。同样，当査询对象q移动较少距离时，其kNN查询结果可能不变,或者前后两 次查询结果之间存在一定联系。因此，见图3.1,在得到kNN结果集后，若能求出下 次的搜索范围，使之最少包含k个对象，则下次查找时就不需要搜索整个目标对象集 合，达到了减少重复计算的目的。Song基于这种思想提出定理3.U9。定理3.1: t时刻，在位置qt的査询对象q的k近邻为pl，p2，pk，D(k)是此时第k个邻居到qt的距离。t+1时刻q的位置为q+i,则下一

55、时刻的搜索范围n +1 ：ft+i=Dt(k) + (5,其中，5是qt到qi+i 的距离。根据最近邻的定义，有：Dist(qt，pOa(k)(Vik)式（3.1)根据三角形不等式，有：Dist(qHi，pi)SDist(qt，pi)+J (Vik)式（3.2)由式（3.1)式（3.2)可以得出：Dist(qHi，pi)SDt(lc)+5式（3J)所以，下一时刻的搜索范围st + i: mi = Dt(k)+5式（3.4)定理3.1表明，下一时刻至少有k个对象到qt+i的距离不大于Dt(k) + 3，所以把图3.：t+1时刻的搜索范围定理给出了下次查询的搜索范围，且这个搜索范围仅与査询对象的移

56、动距离 ？有关，而当查询对象移动较小的距离时，结果集可能不发生改变，这个距离的取值 范围由定理给出9J:定理3.2: t时刻，在位置qi的查询对象q的k近邻为pi，p2，.,.，pk, D,(k)是此 时第k个邻居到qt的距离，Dk + 1)是结果集外到qt的最小距离。t+1时刻q的位置 为qn，则当jgD + lDtCk)时结果集不变化，其中，万是到qi+|的距离。根据定理 3.1,有：Dist(qi+i，pi)5Dt(k)+5 (Vik)式（3.3)对于任意一个不在t时刻结果集里的对象p,根据三角形不等式，有：D.(k + l)-5Dist(p,qt+i)式(3.5)当原有结果集不变，即?

57、|,?2，.，？|仍是下一时刻的结果时，必须有：Dist(qt+i,pi)Dist(qt+i,p) (Vik)式（3.6)由式（3J)式（3.5)式（3.6)得出：Dist(qt+i, pi) Dtk)+ Dt(k+1)-J Dist(qH-i, p)式（3.7)所以：式（3 8)当查询对象移动、目标对象静止时，根据定理可以缩小下次搜索范围，而定 理指出当査询对象的移动距离5 + D,(k)时，结果集不变。下一时刻的搜索范围定为D(k) + 口4，而在HI时刻，四个近邻依次为P2P3, P4, Pi 另外，查询对象移动、目标对象静止时，候选集中对象会随着查询对象q的移动 而发生变化，即有一部分

58、原先在候选集中的目标对象会逃离候选集，也会有一部分原 先不在候选集中的对象会进入候选集。当目标对象也移动时，这个对象逃离、进入候 选集的频率必然要加快，有一些距离查询对象比较远，且会很快逃离出候选集的对象 可以作剪枝剔除出候选集。对于在查询对象和目标对象均运动的状态下，如何能够判 断对象的逃离和进入，本章在3.2.2中作了详细介绍。选取候选集的目标是为了缩小下次搜索范围，使得下一时刻的k近邻包含在候选 集内，减少重复计算，则候选集里面至少要有k个目标对象。结合定理，本文在 定理中给出候选集范围。图3.3: t+1时刻的搜索范围定理3.3: t时刻，在位置卩的查询对象9的11近邻为151，132

59、，,.,口1, Dt(k)是此时第k个邻居到qt的距离，vi是结果集中的最大速度。t+1时刻q的位置为qm，时间间隔At,则下一时刻的搜索范围1 + 1: = Dt(k) + 5 + 5%其中，5是qt到qt+i的 距离，=vkxAt. 证明：根据 k 近邻的定义，有：Dist(qi，pO Dt(k) (Vi k) 假设下一时刻Pi的位置为pi,有：式）式（3.9) 式（3.10)Dist(qt, pi) Dist(qt, pi)+vpi x At (Vi k) 又Vk是结果集中的最大速度：vpixAtSvfcxAt 且根据定义：5 = VkxAt 由式（3.9)式（3.10)式（3.11)有

60、：Dist(qt, pi) Dist(qt,根据三角形不等式，有：式 G.ll)式（3,12)式（3.13)(Vik)Dist(qt+i, pi)Dist(qt,由式（3.1)式（3.12)式（3.13),得出：Dist(qM,pi)Dt(k) + + ?(Vik)式（3.14)这表明t+1时刻至少有k个对象到qt+i的距离不大于D,(k) + 3 + 5，所以选取候选集的范围 + i = Dt(k) + 5 + y。注意，t时刻得到的k个近邻在t+1时刻仍在候选集里面,并不意味着这k个近 邻仍然是t+1时刻的k近邻，只是说明t+丨时刻的k个近邻不需要在候选集以外的空 间査找。因此，找到候选集