Continuously Monitoring Optimal Routes with Collective Spatial Keywords on Road Networks
Jiajia Li, Zongbo Wang, Yifei Zhang, Liang Zhao, Lei Li, Chuanyu Zong · 2022
The keyword-aware route planning problem, which returns the best route satisfying all the user-specified keywords, has attracted more and more research attention. However, existing research work mainly focuses on improving the efficiency of snapshot queries, but does not consider continuously monitoring queries. This paper is the first to investigate the continuous Optimal Routes with Collective Spatial Keywords (ORCSK) problem, which continuously returns the optimal route that can collectively cover the required spatial keywords for the given path on which a user is travelling. The direct solution is to perform multiple snapshot queries, which is obviously inefficient and infeasible. Based on the state-of-the-art algorithm DAPrune for answering ORCSK, we Figure out the safe-region for queries based on two proposed theorem, which means that results do not change within this region. Moreover, when the user leaves the safe-region, the result has to be recalculated. To tackle this scenario, we also propose a baseline algorithm and an optimization algorithm based on DAPrune, which can make full use of previously computed useful information to efficiently update the results. Comprehensive experiments with different parameter settings on multiple real-world road networks show that our safe-region based method is superior to the competitors in orders of magnitude.