摘要
针对已有的在路网中的反向最近邻(Reverse Nearest Neighbor,RNN)查询方法存在的不足,提出了利用网络Voronoi图(Network Voronoi Diagram,NVD)的NVD-RNN算法,该算法具有较好的效果,它把路网划分成小的Voronoi区域,并且采用了两个过程:过滤过程和精炼过程。过滤过程主要是提前存储可能的查询结果。精炼过程主要是从可能的结果集合中找到查询结果。并且进一步给出了处理新增加点的ADDNVD-RNN算法和处理删除点的DENVD-RNN算法。实验表明,该算法在处理路网中的反向最近邻问题时有明显的优势。
In view of the shortage of exisiting reverse nearest neighbour（RNN）query method in road network, NVD- RNN algorithm making use of network Voronoi diagram（NVD） has good effect. The algorithm divides the road net- work into small Voronoi regions and adopts two processes：filtering and refining processes. The filtering process mainly stores possible query results in advance. The major task of refining process is to find query results from potential outcome sets, in addition it provides ADDNVD-RNN algorithm to dispose of newly increased points and DENVD-RNN algorithm to cope with deleted points any further. The experiment demonstrates that the algorithm has obvious advantages in dealing with reverse nearest neighbor in road network.
出处
《计算机科学》
CSCD
北大核心
2015年第8期231-235,258,共6页
Computer Science
基金
黑龙江省教育厅科学技术研究项目(12541128)资助
关键词
网络Voronoi图
反向近邻查询
路网环境
Network Voronoi diagram, Reverse nearest neighbor query, Road network environment
