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

Reverse Nearest Neighbor Query Based on Voronoi Diagram for Road Network

作　　者：张丽平[1] 经海东 李松[1] 崔环宇[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机科学》2015年第8期231-235,258,共6页Computer Science

基　　金：黑龙江省教育厅科学技术研究项目(12541128)资助

摘　　要：针对已有的在路网中的反向最近邻(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.

关 键 词：网络Voronoi图 反向近邻查询 路网环境 

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