Reverse k Nearest Neighbor Queries in Time-Dependent Road Networks
Authors:
- Jiajia LiJLJiajia Li
- Yuxian LiYLYuxian Li
- Panpan ShenPSPanpan Shen
- Xiufeng XiaXXXiufeng Xia
- Chuanyu ZongCZChuanyu Zong
- Chenxi XiaCXChenxi Xia
- 1 June 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1064-1069
Abstract
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%.Keywords
This publication has 6 references indexed in Scilit:
- Minimal on-road time route scheduling on time-dependent graphsProceedings of the VLDB Endowment, 2017
- Effective indexing for approximate constrained shortest path queries on large road networksProceedings of the VLDB Endowment, 2016
- Monochromatic RkNN queries in time-dependent road networks2014
- Finding the cost-optimal path with time constraint over time-dependent graphsProceedings of the VLDB Endowment, 2014
- On the Complexity of Time-Dependent Shortest Paths2011
- Scalable network distance browsing in spatial databases2008