软件工程硕士论文-移动对象轨迹的最近邻居查询研究.doc

《软件工程硕士论文-移动对象轨迹的最近邻居查询研究.doc》由会员分享，可在线阅读，更多相关《软件工程硕士论文-移动对象轨迹的最近邻居查询研究.doc（91页珍藏版）》请在三一文库上搜索。

1、 密级： 硕 士 学 位 论 文 论文题目 移动对象轨迹的最近邻居查询研究作者姓名 指导教师 教授 学科(专业) 软件工程 所在学院 软件学院 提交日期 2007-05-15 A Dissertation Submitted to Zhejiang University for the Degree of Master of EngineeringTITLE: Nearest Neighbor Query Processing on Moving Object TrajectoryAuthor: Supervisor: Professor Subject: Software Engineeri

2、ng College: College of Software TechnologySubmitted Date: May 15, 2007 浙江大学硕士学位论文 摘要摘要随着无线通讯和位置定位系统的发展，移动对象数据库（MOD）变得越来越重要，也对数据库研究提出了极大的挑战。基于时间和空间的查询算法成为一些基于位置的服务急需解决的问题。比如：交通控制，近邻信息访问和对野生动物迁徙特性的分析等。而其中一个重要的查询类型就是k最近邻居（kNN）查询。它主要用来查询离某一移动对象最近的k个轨迹。据我们所知，在已有的研究文献中，他们主要处理的是对于一系列连续移动点的将来或者当前位置的查询，这些查询或

3、者基于静态的查询点或者基于连续移动的查询点。但是对于历史移动对象轨迹的最近邻居查询却很少。基于此，在本文中，首先，我们提出了两种基于最佳优先（Best-First）策略的算法：BFPkNN和BFTkNN。分别用来处理静态查询点以及移动轨迹的k最近邻居（kNN）。并且为了减少内存消耗和CPU时间，本文给出了一些有效的剪枝策略。这些剪枝策略能够有效的避免访问那些不可能包含最终结果的节点，也能剔除掉那些不会成为最终结果的迹线段。其次，我们还提出了在历史移动对象轨迹上处理连续k最近邻居查询的两个算法：HCP-kNN和HCT-kNN。同时我们分析并给出了在连续kNN查询中常用的维护和更新k个最近邻居列表

4、（kNearestLists）算法。再次，本文提出了在存储有历史移动对象轨迹的基于R树的索引结构上进行受限k最近邻居（CkNN）查询的概念，以及有效的处理方法。具体来说，为了有效处理CkNN我们提出了区域查询和kNN查询的依次查询方法以及在kNN查询中整合区域查询的方法。另外，我们还给出了两个算法，一个是截取迹线段得到时间域在某一范围内，空间区域包含在受限区域CR内的部分迹线段的算法，另外一个是截取节点获得时间在指定范围内，空间范围在CR内的部分记录的算法。关键词移动对象轨迹，TB树，k最近邻居查询，受限k最近邻居查询i浙江大学硕士学位论文 AbstractAbstractWith the i

5、ntegration of wireless communications and positioning technologies, the concept of Moving Object Databases (MOD) has become increasingly important, and has posed a great challenge to the database community. Emerging location-dependent services call for new query processing algorithms and techniques

6、to deal with both the spatial and temporal domains. Examples of these new services include traffic monitoring, nearby information accessing and migration patterns analyzing of wild animals. An important class of queries that is definitely useful for MOD processing is the so-called k nearest neighbor

7、 (k-NN) queries, where one is interested in finding the k closest trajectories to a predefined query object Q. To our knowledge, in the literature such queries primarily deal with either static or continuously moving query points over stationary datasets, or queries about the future or current posit

8、ions of a set of continuously moving points. Apparently, these types of queries do not cover NN search on historical trajectories.Motivated by this problem, in this paper, We develop two algorithms based on Best-First traversal paradigm, called BFPkNN and BFTkNN, which handle the kNN retrieval with

9、respect to the static query point and the moving query trajectory, respectively. In addition, we also enable several effective pruning heuristics to prune away all unnecessary nodes such that the memory space consumption and the CPU time can be decreased. The pruning heuristics avoids accessing node

10、s that cannot contain qualifying entries and discard any unnecessary entries. We also present two algorithms, called HCP-kNN and HCT-kNN, which deal with the problem of efficiently processing historical continuous k-Nearest Neighbor. An effective update strategy to maintain the nearest lists is prop

11、osed for continuous kNN search. Furthermore， We introduce and solve the constrained k-nearest neighbor (CkNN) query on R-tree-like structures storing historical information about moving object trajectories. We present several algorithms to handle the CkNN query problem efficiently. In particular, ou

12、r techniques process CkNN queries by either combining conditions of range and kNN queries, or by modifying the existing kNN query algorithms. Inadditionally, we present a algorithm to get the partial entry of trajectory segment that are contained in constrained region CR fully and its lifetime is wi

13、thin a specified time extent and a algorithm to get the portion of node N whose temporal extent is within a given time period as well as spatial area is contained in CR.Key words: Moving Object Trajectory, TB Tree, k nearest neighbour query, constraint kNN queryiii浙江大学硕士学位论文 目录目录摘要iAbstractii图目录III表

14、目录V第1章 绪论11.1 研究背景11.1.1 数据库索引11.1.2 移动对象和移动对象数据库31.1.3 基于R-tree的移动对象索引技术51.2 研究内容81.3 研究目标101.4 本文结构组织101.5 本章小结11第2章 历史移动对象的查询研究综述132.1 区域查询132.2 基于轨迹查询142.3 k（ 1）最近邻居查询142.4 相似轨迹查询152.5 不确定轨迹查询162.6 本章小结16第3章 历史移动对象的k最近邻居查询183.1 引言183.2 相关工作183.3 度量（metric）193.3.1 TB树193.3.2 剪枝策略203.4 点的k最近邻居查询算法

15、233.4.1 算法描述233.4.2 算法分析243.5 轨迹的k最近邻居查询算法253.6 实验评估283.6.1 BFPkNN算法的实验结果293.6.2 BFTkNN算法的实验结果313.7 本章小结33第4章 历史移动对象的连续k最近邻居查询344.1 引言344.2 相关工作354.3 k最近列表的更新364.4 点的连续k最近邻居查询算法424.5 轨迹的连续k最近邻居查询算法434.6 实验评估454.6.1 HCP-kNN 算法的试验结果464.6.2 HCT-kNN 算法的试验结果474.7 本章小结48第5章 历史移动对象的受限k最近邻居查询505.1 引言505.2 相

16、关工作535.3 静止点受限k最近邻居查询算法545.3.1 “两步走”策略545.3.2 “一步走”策略565.4 轨迹受限k最近邻居查询算法605.5 实验评估645.5.1 CkNNP算法的试验结果655.5.2 CkNNT算法的试验结果675.6 本章小结68第6章 总结与展望696.1 本文完成的主要研究工作696.2 本文的主要贡献以及创新点696.3 进一步的研究工作70参考文献72攻读硕士学位期间主要的研究成果78致谢79II浙江大学硕士学位论文 目录图目录图3.1 移动对象轨迹的k最近邻居查询示例2图3.2 TB树结构示例2图3.3 BFPkNN算法伪代码2图3.4 BFTk

17、NN算法伪代码2图3.5 GetMaxDistTrajetory算法伪代码2图3.6 GetMinDistTrajectory算法伪代码2图3.7 BFPkNN 的k变化性能评估2图3.8 BFPkNN TE变化性能评估2图3.9 BFPkNN #MO变化性能评估2图3.10 BFTkNN k变化性能评估2图3.11 BFTkNN TE 变化性能评估2图3.12 BFTkNN #MO变化性能评估2图4.1 移动对象轨迹的连续k最近邻居查询示例2图4.2 结构M中各变量意义示意图2图4.3 UpdatekNearests 算法伪代码2图4.4 UpdateNearests 算法伪代码2图4.5

18、T和M距离关系示意图2图4.6 nT和nM距离关系示意图2图4.7 HCP-kNN算法伪代码2图4.8 HCT-kNN算法伪代码2图4.9 HCP-kNN k 变化性能评估2图4.10 HCP-kNN TE变化性能评估2图4.11 HCP-kNN #MO变化性能评估2图4.12 HCT-kNN k变化性能评估2图4.13 HCT-kNN TE变化性能评估2图4.14 HCT-kNN #MO变化性能评估2图5.1 非受限最近邻居查询和受限最近邻居查询比较（k = 3）2图5.2 静态点和移动轨迹受限最近邻居查询示例（k = 2）2图5.3 CkNNP-DF算法伪代码2图5.4 GetEntryI

19、nConstraint算法伪代码2图5.5 GetNodeInConstraint算法伪代码2图5.6 CkNNP-BF算法伪代码2图5.7 CkNNT-DF算法伪代码2图5.8 CkNNT-BF算法伪代码2图5.9 CkNNP算法 CR变化性能评估2图5.10 CkNNP k变化性能评估2图5.11 CkNNP TE变化性能评估2图5.12 CkNNP #MO变化性能评估2图5.13 CkNNT CR变化性能评估2图5.14 CkNNT k变化性能评估2图5.15 CkNNT TE变化性能评估2图5.16 CkNNT #MO变化性能评估2V浙江大学硕士学位论文表目录表目录表3.1 真实和合成

20、数据集2浙江大学硕士学位论文第1章 绪论第1章 绪论1.1 研究背景移动计算、无线通讯和定位技术的快速发展使得跟踪和管理实际生活中的移动对象轨迹成为了现实。在许多重要领域应用中，诸如交通管制、车辆监控、智能导航、智能物流配送、城市数字规划、数字战场与仿真、移动电子商务、网络游戏等，用户需要有效地存储和查询各种移动对象轨迹信息。例如，在交通管制应用中，交通部门可以通过分析车辆轨迹信息来有效地提供交通拥堵预防、车辆限速等服务。移动对象轨迹是物体在某一个时间段内所经过的路线。它可看作二维或三维的时间序列，其固有的复杂性和海量性使得传统的数据库查询处理技术不能或不能有效地发挥作用，进而必须研究新的查询

21、处理技术来支持各种移动对象轨迹的查询问题。因此，如何提供各种高效的移动对象轨迹查询处理技术成为了当前涉及移动对象轨迹信息的时空数据库研究领域的重点与热点之一。目前在移动对象轨迹的查询处理技术方面，研究工作尚局限于区域查询和基于轨迹查询等处理问题上，仍面临许多重要的查询问题急需解决。此外，移动对象轨迹的查询处理包括对历史信息的查询和对当前及将来信息的查询。在本文中，我们拟对历史移动对象轨迹的查询处理技术进行深入地研究，因为它是众多实际应用中的共性支撑技术。综上所述，历史移动对象轨迹的查询处理技术研究具有现实的理论意义和广阔的应用前景，但因移动对象轨迹独特的特性，使得这一问题的研究面临不小的挑战。

22、1.1.1 数据库索引数据库索引的目的是优化数据库的存储结构，以支持对数据的高效存取与查询处理，保障数据库管理系统的数据处理能力。索引是这样一种数据结构：它以记录的特征（通常是一个或多个字段的值）为输入，并能快速地找出具有该特征的所有记录。具体的说，索引使我们只需要查看所有可能记录中的一小部分就能找到所需要的记录。目前已有多种不同的数据结构可用做索引，下面我们将对它们的研究发展历程做一简单的讨论。1)排序文件上的简单索引：由一个称为数据文件的排序文件得到另一个称为索引文件的文件，而这个索引文件是由关键字与指针对所组成的。若要在索引文件中查找关键字为K的记录，则可以在指针所指向的数据文件中查找关

23、键字为K的记录。2)非排序文件上的辅助索引：这种数据结构可用于任何索引目的，即有助于查找给定一个或多个字段值的记录。它与主索引的最大差别在于辅助索引不决定数据文件中记录的存放位置，而仅能得到记录的当前存放位置，这一位置可能是由建立在其他某个字段上的主索引确定的。3)B-tree：B-tree是一种可在任何文件上建立索引的常用方法，它最初是由Bayer和mcCreight于1972年提出来的。由于B-tree及其它的变体能够自动的保持与数据文件大小相适应的索引层次，能够对所使用的存储块空间进行管理，从而使得每个索引块的充满程度在半满与全满之间，不再需要溢出块。B-tree是建立索引的强有力工具，

24、它已经成为了商用数据库管理系统中一种最常用的索引结构。4)散列表：散列表是另一种有用而重要的索引结构，它以关键字为参数并根据散列函数（或称哈希函数）来计算记录的链接位置。基本的索引方法都是一维的，它们使用单个查找关键字，并且按给定的关键字值来检索记录。但随着数据管理系统应用范围的不断扩大，传统的索引方法已经不能完全支持应用系统中各种类型数据的索引。如在一些商业应用系统中，除了需要处理一些标准的数据类型（如整型、实型）数据之外，还需要处理许多诸如图像、文本、视频、声音等新的数据类型。这就要求将数据视为存在二维或更高维的空间中。在最近的二、三十年时间里，人们更多地是从事支持多维数据和多维查询的索引

25、方法的研究，提出了一些先进的索引结构，具体如下：1)网格文件1：一种对一维散列表进行多维扩展的索引结构。2)分段散列函数2：一种将散列表思想引入多维数据处理的索引结构。3)多键索引：属性A上的索引将引向另一属性B上的索引，对属性A的每个可能的值都有一个对应的属性B的索引。4)kd-tree3：一种将B-tree推广到点集的索引结构。5)四叉树（quadtree）4：结点中的每个子结点代表大空间中的一个象限的多元树。6)R-tree5：一种B-tree的推广，可适用于对区域集合的索引。1.1.2 移动对象和移动对象数据库移动对象是指对象的空间数据随时间的变化而连续变化的对象，它主要可以分为移动点

26、（moving point）和移动区域（moving region）6,7。移动点是指随时间而变化的空间对象的位置（position），例如人、坦克、火箭、导弹、潜水艇等等。在特定时间内对移动点的查询所返回的各个点描述了移动对象在那个时间内的存在位置。对移动点的查询主要是要确定移动对象的位置，而不是要确定移动对象的区域。移动区域是指随时间而变化的空间对象的位置及其形状。例如行政区域、森林的增长、暴风雪的影响、种族变化等等。在特定时间内对移动区域的查询所返回的各个区域描述了移动区域在那个时间内的存在位置与形状。对移动区域的查询主要是要确定在特定时间内移动对象的位置或形状。移动对象数据库是一个新兴

27、的研究领域。移动对象数据库（Moving Objects Databases, MOD）是指对移动对象（如车辆、飞机、移动用户等）及其位置进行管理的数据库。它主要可以用于民航管制、交通管理、军事指挥以及基于位置的信息服务等众多领域。例如，出租汽车公司可以根据5分钟后车辆可能的位置进行车辆调度；移动运营商可以向用户推送基于位置的广告或电子优惠券等。而移动对象索引技术则是移动对象数据库研究的关键技术之一，它对移动对象数据库模型的设计与建立、移动对象数据库管理系统的开发研制，特别是对移动对象数据库查询语言以及真正的移动对象数据库管理系统层次的研究等方面都具有重要的影响。移动对象数据库通常管理着数量非

28、常庞大的移动对象。在查询处理时如果逐个扫描所有的移动对象显然将会极大地影响系统的性能。为了减小搜索空间，就必须对移动对象进行索引。移动对象的索引方法通常借鉴于空间数据索引技术，不同之处在于移动对象的索引中有一维必然是时间维。目前在空间数据索引方面人们已经提出了许多方法，如R-tree及其变形树（R+-tree、R*-tree等）、四叉树（Quadtree）、X树、LSD树、Grid File等。这些方法对移动对象的索引具有很好的借鉴意义，但是它们并不能直接应用于移动对象索引。这是因为上述方法主要适用于静态的空间对象，并且更多地是考虑查询效率，而没有将索引的更新代价作为考虑的重点。但是在移动对象

29、数据库中，移动对象的位置会经常发生变化，移动对象频繁的位置更新会引起其索引结构频繁的动态变化，因此在对移动对象进行索引时必须要更多地考虑索引的更新性能。目前，主流的移动对象索引方法主要可分为R-tree及其变形树（如R+-tree、R*-tree等）、QUADTREE及其变形树、以及GRID FILE及其变形；并且通常将已提出的移动对象索引方法主要分为如下两类：1)索引移动对象过去与当前的位置：这一类主要是对移动对象的过去位置即移动对象过去的运动迹线进行索引，通常，将在D维空间中的对象运动转换成在D+1维空间（即D维空间+时间维）中的一个迹线。例如Pfoser等8提出的时空R树（Spatio-

30、Temporal R-tree, STR-tree）与迹线捆绑树（Trajectory-Bundle tree, TB-tree）；Tao和Papadias9提出的多版本三维R树（Multi Version 3D R-tree, MV3R-Tree）等。2)索引移动对象当前与将来的位置：这一类主要是对移动对象的当前位置进行索引，通常，用一个线形函数来描述一个移动对象的位置，并且仅仅当该线形函数的参数发生变化时，存储在数据库中的移动对象的位置才需要更新。例如Saltenis等10提出时参R树（Time-Parameterized R-tree, TPR-tree）；Kwon和Lee等11提出懒惰

31、的更新R树（Lazy Update R-tree, LUR-tree）等。1.1.3 基于R-tree的移动对象索引技术迄今为止，一些好的关于移动对象索引技术的综述已被给出。例如，Gaede等12给出了一个关于空间数据库中各种多维访问方法的综述；Mokbel等13给出了一个关于已有的各种时空访问方法的综述。根据各种时空访问方法所支持的查询类型与时间，Mokbel等将时空索引方法分成两类：索引过去、索引现在与预测将来位置，并对每类方法进行了简单讨论。另外，他们还简单地介绍了一些开放的并且可利用的索引工具，例如，数据库系统的通用查找树（Generalized Search Tree for Dat

32、abase Systems, GiST）和空间划分的通用查找搜索树（Space-partitioning Generalized Search Tree, SP-GiST）等，这些索引工具可以帮助我们实现各种不同的时空访问方法。最近，Manolopoulos等14系统性给出了一个基于R-tree及其变体的移动对象索引方法的综述。他们详细讨论了R-tree及其变体的适用性，精确的代价模型，诸如并发控制、恢复以及并行处理等的实现问题等，并且还介绍了由一些数据库开发商所实现的R-tree及其变体。虽然他们给出了一个好的基于R-tree及其它的变体的各种移动对象索引技术的综述，但是却没有考虑基于四叉树

33、（quadtree）的移动对象索引技术和其它的移动对象索引技术；下面我们将分别对三类移动对象索引技术及其各自相应的移动对象索引方法分别进行简单的讨论。(1) 索引过去3DR-tree 15：三维R树（3DR-tree）将时间看作一维，它与另外的二个空间维共同构成三维，故称为3DR-tree。3DR-tree可能是最简单的移动对象索引方法，并且比较容易实现。由于3DR-tree仅仅存储不同的移动对象版本而没有冗余的拷贝，所以它耗费的存储空间较低。又由于时间和空间属性紧密地集成在3DR-tree的结点中，所以一个时间间隔查询可以被看作是一个普通的窗口查询（Window Query, WQ），并且能

34、被有效的处理。然而，3DR-tree的时间片查询性能较低，因为此时的查询时间不再取决于查询时间戳内的活动记录（live entries），而是取决于所有的历史记录。另外，由于3DR-tree中的一个R-tree保持着整个时间区域（time range），所以随着时间的流逝，时间区域将逐渐增大，这使得3DR-tree的性能也逐渐地退化（降低）。STR-tree 16：Pfoser等提出的时空R树（Spatio-Temporal R-tree, STR-tree）可被用来索引移动对象的过去（或历史）信息与迹线（trajectory）信息。STR-tree有一个三维的最小界限盒（Minimum Bo

35、unded Box, MBB）结构，同时考虑了移动对象的空间属性与迹线保护。STR-tree处理基于迹线的查询效率高，并且索引的大小和空间的利用率都比R-tree要小。APR-tree 17：基于自适应划分技术（adaptive partitioning technique）的自适应分区R树（Adaptive Partitioned R-tree, APR-tree）可以自动调整时间片查询与时间间隔查询的工作量来合适的索引移动对象的过去（或历史）数据。APR-tree由多个3DR-tree组成，并且把自适应查询划分方法（query-adaptive partitioning method）引入

36、到3DR-tree中，每一棵3DR-tree来负责随查询工作量而变化的固定时间间隔查询。APR-tree的缺点是其容量大小与更新代价（成本）受到查询工作量的影响，即随着时间间隔查询比率的增加，APR-tree的大小与更新代价（成本）反而减少。另外，APR-tree的大小比3DR-tree稍大，但是其更新代价却几乎一样。MV3R-tree 18：Tao与Papadias结合多版本B树（MultiVersion B-tree, MVB-tree）与三维R树（3DR-tree）的思想而提出了MV3R-tree。它的主要设计思想是构建两棵树，其中一棵是MVR-tree用来处理时间片查询，而另一棵是构建

37、在MVR-tree的叶结点上的小型辅助的3DR-tree来处理长时间间隔查询。对于短时间间隔查询被最优化成可以根据一个阈值来检查究竟该使用哪一棵树来进行处理。虽然MV3R-tree结合了MVR-tree和3DR-tree的优点，可以有效的处理时间片查询与时间间隔查询，但是它却比3DR-tree需要更多的空间，并且也需要更高的管理代价。TB-tree 19：Pfoser等提出的迹线束树（Trajectory-Bundle tree, TB-tree）是一种严格保护移动对象迹线的索引方法，并且每个叶结点仅仅包括属于同一迹线的直线段。该索引方法处理区域查询的速度比较慢。TB-tree能有效的处理迹线

38、查询，但是对于涉及到大量移动对象的时间片查询与时间间隔查询的效率却相对较差，因为它没有考虑空间区别；同时该索引方法也引入了大量的重叠。另外与STR-tee相比较，处理面向迹线的查询性能要比STR-tee高；索引结构的大小也要比STR-tee小。而与R-tee相比较，TB-tree的索引大小、空间利用率以及查询性能均要高于R-tee。SETI 20：Chakka等提出一种称为可升级与有效的迹线索引（Scalable and Efficient Trajectory Index, SETI）结构，用来存储迹线数据集并且可以升级到大的迹线数据集。SETI提供了一个快速的插入算法，并在区域查询与时间片

39、查询上有良好的性能。它把空间维划分成静态的并且不重叠的单元，每个单元仅仅包括那些完全在该单元内的迹线片段。假如一个迹线片段跨越两个单元的边界，那么它就在边界处被分裂成两个迹线片段，并且分别插入到这两个单元中。另外，由于SETI直接使用目前已有的各种空间索引结构（如R-tree等）而不作任何修改，所以目前所有凡是支持R-tree索引结构的数据库管理系统都能很容易的实现该索引结构，使其成为一个索引迹线数据集的既实用又有效的索引方法。SEB-tree 21：开始/结束时间戳B树（Start/End timestamp B-tree, SEB-tree）扩展了基于分区的索引更新策略，并且它的索引结构具

40、有快速的插入与查询算法。SEB-tree的基本思想与SETI类似，它也是把空间划分成可以重叠的分区。每个分区都用SEB-tree来索引，但是它仅仅考虑移动对象的开始时间戳和结束时间戳。每个移动对象都用哈希法映射到相应的分区。SEB-tree与SETI的主要区别是SEB-tree没有迹线的概念，而仅仅能索引二维的空间点。(2) 索引现在与将来二元变换22：Kollios等使用二元变换（Duality transformation）把在时空域上的移动对象的迹线转换到二维空间上的点。该索引方法的主要设计思想是用方程式xt=at+b来表示一个二维空间中的点（a, b），其中a代表速度并作为水平维；而b

41、代表参考位置并作为垂直维。由于移动对象杂乱的分布在二元空间上，所以基于kd树（kd-tree）的空间索引方法被用来代替R-tree。由于在初始的时空空间里的矩形区域查询被转换成在二元速度位置空间里的多边形区域查询，所以由Goldstein等23提出的算法可被用来有效的处理区域查询。TPR-tree 24：Saltenis等提出了基于R*-tree的索引技术，称为时参R树（Time Parameterized R-tree, TPR-tree）。TPR-tree能有效的索引在一维，二维，三维空间中的移动点对象的现在与预测的将来位置。TPR-tree考虑移动对象的速度与方向来预测移动对象在不久将来

42、的大致位置。并且通过考虑在树结构中可计算的位置来减少时间函数的频繁更新问题。同时，TPR-tree的更新算法也能使其自动的调整以适应于一个动态变化的数据集。PR-tree 25：参数化R树（Parametric R-tree, PR-tree）与TPR-tree类似，但是PR-tree考虑用参数化矩形来表示移动对象的空间区域。每个参数化矩形都有一个时间间隔来表示移动对象运动的开始时间和结束时间。与TPR-tree考虑连续运动的对象不同，PR-tree还考虑移动对象的结束时间。因此，一个移动对象在空间上用一个多边形来表示而不是连续的运动迹线。给定运动的结束时间，一系列的移动对象可以用可计算的多边

43、形来表示。MP-tree 26：Lee等提出了一棵移动点树（Moving Point Tree, MP-tree），它是一个用来索引移动点对象数据的基于R-tree的索引方法。MP-tree使用投影操作（projection operation）来有效的支持诸如时间片查询与区域查询等的查询操作。但是使用投影操作带来的一个缺点就是当结点被输入时需要花费更多的时间来进行投影操作的存储，而优点则是能有效的处理分裂与查询操作，并且具有高效的空间利用率。另外，通过链表的使用，MP-tree还可以有效的处理基于迹线的查询。1.2 研究内容随着移动对象定位技术的进一步发展，移动对象轨迹的查询研究成为最近研究

44、方向的一个热点。但是对于历史移动对象轨迹的查询却并不多，已有的算法在CPU时间和I/O方面的消耗比较大。基于此，在本文中，我们拟开展以下方面内容的研究：1) 历史移动对象轨迹的非连续k最近邻居查询处理技术研究在历史移动对象轨迹上查询离静止查询点和移动轨迹的k个最近邻居。我们提出了基于最佳优先策略的两个算法，但是由于最佳优先策略采用了一个优先队列来保存记录以及记录离查询对象距离，每次对该优先队列的操作都将导致它重新按照记录的距离排序，为了进一步减少存储器消耗和CPU时间，我们还研究了怎样避免不包含最终结果的节点和不可能成为最终结果的迹线段被加入到队列中。另外，我们通过一系列的定义，定理证明了算法

45、的I/O最佳性。并从实验上分析和比较各种实现算法的性能。2) 历史移动对象轨迹的连续k最近邻居查询处理技术研究在历史移动对象轨迹上查询在任意时刻离静止查询点和移动轨迹的k个连续最近邻居，即连续k最近邻居查询算法。我们提出的两个算法同样是基于最佳优先策略的算法。由于连续kNN查询的最终结果集中保存得是任意时刻离查询对象最近的k个邻居，但是在以前的研究工作中没有对维护和更新最近结果集的探索，在我们的第五章里，我们详细的分析和描述了如何维护和更新最终结果集，并给出了算法。并且我们通过大量实验证明了更新算法的有效性和查询算法的优越性。3) 历史移动对象轨迹的受限k最近邻居查询处理技术应用已有的历史移动

46、对象轨迹的区域查询和k最近邻居查询处理技术，研究在带有约束查询区域的情况下历史移动对象轨迹的k最近邻居查询和连续k最近邻居查询问题，即受限k最近邻居查询。我们提出了一系列处理算法，其中包括两个“两步走”策略的算法和两个“一步走”策略的算法。在历史移动对象轨迹中判断在某一段时间范围内，一条轨迹是否穿过受限区域是一个难点。我们在第六章给出了判断并截取迹线段包含在受限区域内部的那一部分的算法，以及判断并截取时间在查询时间范围内，空间在受限区域中的节点的算法。通过一系列的实验，我们验证了判断与截取算法的正确性，并比较了几种不同受限查询算法的优劣。1.3 研究目标作为空间数据库和时空数据库中最重要的查询类型之一，k最近邻居（kNN）查询受到了数据库界的广泛关注。迄今为止，研究学者已经提出了大量的kNN查询处理技术。但对于移动对象轨迹的kNN查询问题的研究却很少。该查询问题的一般形式是“查找在查询