路网中基于Voronoi图的反向最近邻查询方法

针对已有的在路网中的反向最近邻(Reverse Nearest Neighbor,RNN)查询方法存在的不足,提出了利用网络Voronoi图(Network Voronoi Diagram,NVD)的NVD-RNN算法,该算法具有较好的效果,它把路网划分成小的Voronoi区域,并且采用了两个过程:过滤过程和精炼过程。过滤过程主要是提前存储可能的查询结果。精炼过程主要是从可能的结果集合中找到查询结果。并且进一步给出了处理新增加点的ADDNVD-RNN算法和处理删除点的DENVD-RNN算法。实验表明,该算法在处理路网中的反向最近邻问题时有明显的优势。

Reverse Nearest Neighbor Query Based on Voronoi Diagram for Road Network

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 network 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.