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

摘要： 为了弥补现有的研究成果无法有效地处理路网环境下基于线段的反k最近邻问题的不足，提出了在路网环境下线段反k最近邻查询方法。该查询方法主要应用于评估查询对象的影响范围。根据路网及Voronoi图的特点提出了网络线段Voronoi图的概念。在静态数据集情况下利用网络线段Voronoi图的性质提出了STA_RVLRkNN算法，查询包括过滤过程和精炼过程两大部分。进一步，在动态数据集的情况下提出了DYN_ RVLRkNN算法，查询分为空间线段对象增加和删除两种情况，并对不同的情况给出了相应的算法，得到查询结果集。理论研究和实验表明，所提算法能有效地处理路网中基于线段的反k最近邻问题。

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