论文部分内容阅读
连续反最近邻查询技术是空间数据库领域中的一个重要研究课题。连续反最近邻查询是指连续检索将查询点作为最近邻的所有对象。随着定位装置的广泛应用和定位服务的发展,道路网络中连续反最近邻查询现已应用于决策支持、交通网络、资源分配等各种领域,并逐渐成为空间数据库领域的热点课题。本文在对国内外反最近邻查询技术的研究现状进行综合分析的基础上,从一个全新的角度对道路网络环境下的连续反最近邻查询方法进行了研究。首先,为了有效表示和存储道路网络,在综合分析和研究已有的道路路网的近邻查询方法基础上,提出了用过渡矩阵及一个标志位来模拟路口转向限制以及路段是否可用状况,从而表示了简单受限路网。接着提出了一个道路网络数据两层存储模式,将网络数据与兴趣数据集分开存储,并讨论了其各个组件的具体功能。其次,为了解决道路网络反最近邻查询不能处理连续查询的问题,在一个道路网络数据两层存储模式基础上,给出并证明了查询空间修剪定理,提出了基于网络扩展的连续反k最近邻查询算法,并对算法的正确性进行了证明,给出了实例分析。再次,针对R树是严格按照欧式距离来组织数据对象的问题,采用M树索引结构有效组织道路网络对象。针对网络距离计算代价高的问题,利用道路网络嵌入技术将道路网络映射到m维向量空间,采用棋盘距离L_∞近似表示网络距离。在此基础上,提出了基于M树和道路网络嵌入技术的连续反k最近邻查询算法,给出了该算法的时间复杂度。最后,基于上述研究成果,对提出的算法进行了实验验证和结果分析。