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

Continuous reverse nearest k neighbors query processing on road network

现存的反向k近邻查询方案中,比较高效地研究大多集中在欧式空间,对于路网中的反向k近邻查询的研究相对较少。针对这一问题,考虑路网中移动查询点和移动数据对象的移动性,选用PMR四叉树来索引路网,基于安全区的概念提出一种反向k近邻(RkNN)查询算法,通过监控查询点和移动对象的安全区来处理路网更新。基于"初始化-维护更新"框架,采用Dijkstra搜索策略,设置验证监控区域来判定候选对象解的真假性。为了减少网络搜寻的工作量,提出了一系列剪枝规则来削减搜索空间。实验结果表明,该算法适用于路网中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.