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

A Improved Algorithm For Efficient Continuous KNN Queries

作　　者：孙圣力[1] 林硕[2] 

机构地区：[1]北京大学软件与微电子学院,北京102600 [2]北京大学软微学院无锡基地,江苏无锡214125

出　　处：《计算机研究与发展》2013年第S1期80-89,共10页Journal of Computer Research and Development

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

摘　　要：连续k近邻查询是空间数据库一直以来的热点问题.但大多数研究成果都是在欧式空间上的.IMA?GMA算法是少有的几种基于道路网的连续k近邻查询算法之一,同时也是比较优秀的算法.但是IMA算法仍然存在不足之处.在针对IMA算法的不足进行充分讨论后,提出了内结构迭代变更法和数据对象树,分别弥补了IMA在数据更新频繁和扩展树生成时表现出的性能缺陷.内结构迭代变更法在数据更新后对扩展树内结构进行快速调整,避免了对树的大规模剪枝以提高扩展树的利用率,从而提高在数据频繁更新时的性能.数据对象树用于快速获取子树上所有数据对象的有序集合,以辅助新查询利用已有查询的扩展子树结构.理论分析和仿真实验都证明了改进的IMA算法比原IMA算法更能适应多种情况,性能表现更为优异.Continuous nearest neighbor search is one of the hot problems in the field of spatial databases.But most of the researches focus on C-kNN assuming the Euclidean distance metric.IMA/GMA algorithm is one of the few excellent algorithms discuss about C-kNN on road network.IMA algorithm,however,has some drawbacks.One is weakness for data updating frequently.Another is weakness for expansion tree growing.This paper fully analyzes drawbacks of IMA,and then comes up with inner structure iterative changing algorithm and object tree for making up the tow drawbacks separately.Inner structure iterative changing algorithm promotes performance of data updating by changing expansion tree structure rapidly to avoid large-scale pruning.Object tree assists that new query utilizes subtrees of existing queries through retrieving the ordered objects on the subtree quickly.Both theoretical analysis and simulation experiment show that improved IMA performs better than raw IMA in many cases.

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]