路网中连续反向k近邻查询处理

摘要

现存的反向k近邻查询方案中，比较高效地研究大多集中在欧式空间，对于路网中的反向k近邻查询的研究相对较少。针对这一问题，考虑路网中移动查询点和移动数据对象的移动性，选用PMR四叉树来索引路网，基于安全区的概念提出一种反向k近邻（RkNN）查询算法，通过监控查询点和移动对象的安全区来处理路网更新。基于“初始化-维护更新”框架，采用Dij kstra搜索策略，设置验证监控区域来判定候选对象解的真假性。为了减少网络搜寻的工作量，提出了一系列剪枝规则来削减搜索空间。实验结果表明，该算法适用于路网中k值不固定的连续RkNN查询。%In the field of reverse k nearest neighbor query,many efficient algorithms had been proposed in Euclidean spaces while only a few algorithms on road network.Based on the mobility of the moving query points and the moving obj ects in road net-work,the PMR quad-tree was chosen to build the road network and a novel algorithm was proposed for reverse nearest k neigh-bors (RkNN)query by adopting the concept of the safe region which was used to monitor the update.The algorithm based on the framework of“initial computing-continuous monitoring”adopted the strategy of Dij kstra and verified the candidate obj ects by checking the verifying-regions.To simplify the monitoring,a series of pruning rules were presented.The results of the experi-ment showed that the algorithm was scalable in processing continuous RkNN query in road network for which the value of k was not fixed.