Reverse k Nearest Neighbor Queries in Time-Dependent Road Networks

摘要

Travel time becomes a unit of measure for reverse k nearest neighbor queries in the time-dependent road network. The existed algorithms are inefficient when the density of interest points is sparse or the k value is large. In this paper, a grid-based algorithm is proposed to improve the efficiency. Firstly, the road network is divided into many grids, and the grids without points of interest are merged into many sub-graphs. Then, a pruning technology is used to reduce the search range of the road network. Finally, the found candidate interest points are verified in order to determine the results. The experimental results show that the response time of our proposed algorithm is reduced by 73.7% compared with the existed algorithm mTD-Eager and the number of traversal nodes is reduced by 57.9%.