关键词: 路网, 网络线段Voronoi图, 反k最近邻

Abstract: To remedy the defects that existing methods can not deal with the line segment reverse k nearest neighbor (RkNN) query in road network, this paper puts forward the line segment RkNN query method in road network. The query method is mainly used to assess the scope of query object. Based on the characteristics of road network and Voronoi diagram, the network line Voronoi diagram (NLVD) concept is proposed. According to the property of NLVD, the STA_RVLRkNN is given in static line segment set environment, the query includes two parts: filtering and refining processes. Further, DYN_RVLRkNN method is given in dynamic line segment set environment, this query is divided into two parts of adding and deleting space segment objects, then the corresponding algorithm is proposed for different situations and new query result set is obtained. The theatrical study and experimental results show that the algorithm can effectively deal with the line segment RkNN query in road network.

Key words: road network, network line Voronoi diagram (NLVD), reverse k nearest neighbor