Finding shortest keyword covering routes in road networks

ABSTRACT

Millions of users rely on navigation applications to compute an optimal route for their trips. The basic functionality of these applications is to find the minimum cost route between a source and target node in the transportation network. In this paper, we address a variant of this problem, where the computed route is required to contain a set of Points of Interest of specific types. Our approach is based on the concept of keyword skyline. We formally define this concept, and we show how to compute the keyword skyline for the vertices of a given network and how to use it for computing the shortest keyword covering paths. We present different variants of this method, including an approximation algorithm, providing different trade-offs between preprocessing cost and execution time. Finally, we present an experimental evaluation of our approach using real-world datasets of different sizes, including also a comparison to the current state-of-the-art algorithm for this problem.

References

1. Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck. 2011. A hub-based labeling algorithm for shortest paths in road networks. In SEA. 230--241.
2. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling. CoRR abs/1304.4661 (2013).
3. Julian Arz, Dennis Luxen, and Peter Sanders. 2013. Transit node routing reconsidered. In SEA. 55--66.
4. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2015. Route planning in transportation networks. CoRR abs/1504.05140 (2015).
5. Paolo Bolzoni, Sven Helmer, Kevin Wellenzohn, Johann Gamper, and Periklis Andritsos. 2014. Efficient itinerary planning with category constraints. In SIGSPATIAL. 203--212.
6. Xin Cao, Lisi Chen, Gao Cong, and Xiaokui Xiao. 2012. Keyword-aware optimal route search. PVLDB 5, 11 (2012), 1136--1147.
7. Camila F. Costa, Mario A. Nascimento, José Antônio Fernandes de Macêdo, Yannis Theodoridis, Nikos Pelekis, and Javam C. Machado. 2015. Optimal time-dependent sequenced route queries in road networks. In SIGSPATIAL. 56:1--56:4.
8. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. 2013. Computing multimodal journeys in practice. In SEA. 260--271.
9. Daniel Delling and Giacomo Nannicini. 2012. Core routing on dynamic time-dependent road networks. INFORMS Journal on Computing 24, 2 (2012), 187--201.
10. Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. 2009. Engineering route planning algorithms. Algorithmics of Large and Complex Networks (2009), 117--139.
11. Edsger W Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269--271.
12. Jochen Eisner and Stefan Funke. 2012. Sequenced route queries: Getting things done on the way back home. In SIGSPATIAL. 502--505.
13. Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, and Grammati E. Pantziou. 2014. A survey on algorithmic approaches for solving tourist trip design problems. J. Heuristics 20, 3 (2014), 291--328.
14. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3 (2012), 388--404.
15. Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A* search meets graph theory. In SODA. 156--165.
16. Moritz Hilger, Ekkehard Köhler, Rolf H. Möhring, and Heiko Schilling. 2006. Fast point-to-point shortest path computations with arc-flags. (2006), 41--72.
17. Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. 2005. On trip planning queries in spatial databases. In SSTD. 273--290.
18. Michael N Rice and Vassilis J Tsotras. 2012. Exact graph search algorithms for generalized traveling salesman path problems. In SEA. 344--355.
19. Michael N Rice and Vassilis J Tsotras. 2013. Engineering generalized shortest path queries. In ICDE. 949--960.
20. Michael N. Rice and Vassilis J. Tsotras. 2013. Parameterized algorithms for generalized traveling salesman problems in road networks. In SIGSPATIAL. 114--123.
21. Mehdi Sharifzadeh, Mohammad Kolahdouzan, and Cyrus Shahabi. 2008. The optimal sequenced route query. VLDB J. 17, 4 (2008), 765--787.
22. SS Srivastava, Santosh Kumar, RC Garg, and Prasenjit Sen. 1969. Generalized traveling salesman problem through n sets of nodes. CORS journal 7 (1969), 97--101.
23. T Tsiligirides. 1984. Heuristic methods applied to orienteering. Journal of the Operational Research Society 35, 9 (1984), 797--809.
24. Lingkun Wu, Xiaokui Xiao, Dingxiong Deng, Gao Cong, Andy Diwen Zhu, and Shuigeng Zhou. 2012. Shortest path and distance queries on road networks: an experimental evaluation. PVLDB 5, 5 (2012), 406--417.
25. Bin Yao, Mingwang Tang, and Feifei Li. 2011. Multi-approximate-keyword routing in GIS data. In SIGSPATIAL. 201--210.

Index Terms

• Information systems

  • Data management systems

    • Data structures

  • Information systems applications

    • Spatial-temporal systems

      • Location based services