路网中基于四叉树的移动对象k近邻查询技术研究

发布时间：2020-07-18 06:16

【摘要】：移动通信设备的普及和无线定位技术的发展,使得基于位置的服务得到了广泛的应用。然而,随着这些服务应用的扩散,空间数据日益增多,空间数据结构日益复杂,空间数据库面临着越来越复杂的搜索查询问题。因此,对其中的移动对象建立快速有效的查询算法具有重要意义。k近邻查询一直是空间数据库中数据查询的基础技术之一,广泛应用于各种领域,引起了国内外众多学者的深入研究。但现有的研究方法大多是在特定环境下(如欧式空间)实现其功能目标的,充分考虑到道路网络连通性及移动对象特性等因素的研究较少。而道路网络环境下的k近邻查询往往更符合人们实际需求,具有更重要的研究意义。路网环境中数据量巨大、数据结构复杂、数据分布倾斜、数据更新频繁,这些情况使得移动对象k近邻查询的操作代价相当昂贵,因此如何提高其查询效率成为研究人员面临的一大挑战。为了应对这一挑战,解决在移动数据分布倾斜的路网环境下如何进行高效查询的问题,本文在分析总结国内外相关研究成果的基础上,提出了路网环境中移动对象k近邻查询的解决方案。本文主要研究工作有以下几个方面:(1)针对道路相对静止且移动对象分布倾斜的情况,本文采用R树和四叉树的双层索引结构分别索引道路网络和移动对象。用四叉树的每一个矩形存储该区域中移动对象的位置等信息,其层次结构能控制每个矩形中对象的数量,使得k近邻查询时能获取合适的搜索区域。采用R树对道路建立索引,查询R树中与搜索区域交叠的矩形,获取这些矩形的叶子结点中对应的道路,加载出搜索区域对应的局部道路。(2)建立四叉树矩形区域间的信息更新机制。四叉树矩形区域中存储的移动对象数量超过一定阈值时,矩形会划分或者合并,因此需要设计发生变化的矩形间的更新机制让这些矩形也能实现高效的近邻的查询。首先新矩形利用原矩形近邻信息来更新获取其近邻信息,然后新矩形再向其自身近邻矩形发送信息更新替代原矩形信息。(3)设计基于矩形更新机制的搜索区域增量扩展方法和基于此扩展方法的k近邻查询算法。为了实现高效的搜索区域扩展,得到合适的k近邻查询范围,设计搜索区域增量扩展算法,该算法需要先计算新搜索区域近邻的矩形。最后基于搜索区域增量扩展的方法,结合道路网络信息设计完整的路网中k近邻查询算法。(4)设计实验对比分析,本文采用两个不同的路网数据集,从查询效率和更新时间两方面对本文算法进行分析。实验结果表明,在移动对象分布不均的情况下,本文算法能高效地修剪掉大部分不必要的移动对象,使得其查询处理效率优于对比算法,并且本文算法具有一定的可伸缩性和可扩展性;从更新时间上看,本文算法的更新机制所需成本低,对频繁更新的移动对象有良好适应的能力。
【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TN929.5;TP311.13
【图文】：

简单网,索引,实体,网格

第 2 章相关概念及技术部分对应的网格分别增加新的记录来反映当前处理的实体单网格空间索引。有创建、重建、插入、删除和更新等关键操作。创建网格特征计算出一个合适的网格尺度，对每一个实体按网格进有网格中追加该实体记录，直到所有实体记录完毕。随着变，网格的统计特征可能会发生改变，这就需要重新统计适的网格尺度，重建网格。当插入空间实体时，首先计算格，并计算出空间要素的网格编码，然后在网格结构索引数据项。而删除实体记录需要删除所有该实体对应的索引以通过删除索引记录再添加索引记录来实现。

数据结构,叶子结点,空间对象

图 2-2 R 树索引数据结构示例图如图 2-2 所示为一个 R 树的索引结构，图左边是 11 个空间对象集合，右边对应的 R 树是一个平衡的 3 叉树，其叶子结点都在第二层。相邻的空间对象的 MBR进行框选聚集，形成一个父结点的 MBR，图中 6、8、9 的 MBR 构成了 C 的 MBR。当进行查询时，从根结点开始，首先查询 A、B、C，如果搜索区域与 A 或者 B或者 C 结点相交，则继续向下进行查询直到到达叶子结点，最后具体计算叶子结点中的数据。可以看到 R 树结构的一个重要特点是兄弟结点所对应的 MBR 可能相互交叠，使得 R 树容易进行插入或者删除等更新的操作。但另一方面，当在 R 树中进行插入或者删除的时候，出现下溢或者上溢的状况，则需要重新对结点内的数据进行调整，甚至需要对整个 R 树的层次结构进行调整，使得空间查询的效率下降，因此 R 树并不适合频繁进行动态更新的环境。但现实道路拓扑网络更新周期相对较长，整体上相对固定，利用平衡的 R 树索引是比较合适的，因此本文采用 R 树对路网拓扑进行索引。

路网模型,路段,道路网络

图 2-3 基于路段的路网模型示例图道路网络用加权有向图 G 来表示，令 G=(V,E)，其中，V 表示道路网络中顶点的集合 V=(v1，v2，v3，…vi)，顶点模拟道路的交叉口、起点、终点；E 表示道路网络中线段的集合，E=(e1，e2，e3，…ei),模拟起始点 vi和终点 vj两个顶点间的路段；边的权重 d 表示对应的路段长度，记作 e=(vi,vj,d)。路网建立对应路段模型后，建立起对路网线段的索引，即建立路段的 MBR。如图 2-4 所示，所框选的矩形部分为线段 e1、e2、e3的 MBR。

【参考文献】