一个高效的连续k近邻查询改进算法

作     者：孙圣力 林硕 Sun Shengli;Lin Shuo

作者机构：北京大学软件与微电子学院北京102600 北京大学软微学院无锡基地江苏无锡214125 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2013年第50卷第S1期

页      面：80-89页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

基　　金：江苏省自然科学基金项目(BK2010139) 

主　　题：空间数据库 连续k近邻 IMA改进 内结构迭代变更法 数据对象树 

摘      要：连续k近邻查询是空间数据库一直以来的热点问题.但大多数研究成果都是在欧式空间上的.IMA?GMA算法是少有的几种基于道路网的连续k近邻查询算法之一,同时也是比较优秀的算法.但是IMA算法仍然存在不足之处.在针对IMA算法的不足进行充分讨论后,提出了内结构迭代变更法和数据对象树,分别弥补了IMA在数据更新频繁和扩展树生成时表现出的性能缺陷.内结构迭代变更法在数据更新后对扩展树内结构进行快速调整,避免了对树的大规模剪枝以提高扩展树的利用率,从而提高在数据频繁更新时的性能.数据对象树用于快速获取子树上所有数据对象的有序集合,以辅助新查询利用已有查询的扩展子树结构.理论分析和仿真实验都证明了改进的IMA算法比原IMA算法更能适应多种情况,性能表现更为优异.