Reverse k Nearest Neighbor Queries in Time-Dependent Road Networks

摘要

Travel time becomes a unit of measure for time-dependent reverse k nearest neighbor queries in the road network. The existed algorithms are less efficient when the density of interest points is sparse or the k value is larger. In this paper, a grid-based reverse k nearest neighbor query algorithm mTD-SubG-Imp is proposed. 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 point of interests are verified in order to determine the results. The experimental results show that the response time of mTD-SubG-Imp is reduced by 73.7% compared with mTD-Eager algorithm and the number of traversal nodes is reduced by 57.9%.