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