Abstract
The current widespread use of location-based services and GPS technologies has revived interest in very fast and scalable shortest path queries. We introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid shortest path (e.g., dynamically restricting the type of roads or modes of travel which may be considered in a multimodal transportation network). We formalize this problem as a specific variant of formal language constrained shortest path problems, which we call the Kleene Language Constrained Shortest Paths problem. To efficiently support this type of dynamically constrained shortest path query for large-scale datasets, we extend the hierarchical graph indexing technique known as Contraction Hierarchies. Our experimental evaluation using the North American road network dataset (with over 50 million edges) shows an average query speed and search space improvement of over 3 orders of magnitude compared to the naïve adaptation of the standard Dijkstra's algorithm to support this query type. We also show an improvement of over 2 orders of magnitude compared to the only previously-existing indexing technique which could solve this problem without additional preprocessing.
- C. L. Barrett, K. Bisset, M. Holzer, G. Konjevod, M. V. Marathe, and D. Wagner. Engineering label-constrained shortest-path algorithms. In AAIM, pages 27--37, 2008. Google Scholar
- C. L. Barrett, K. Bisset, R. Jacob, G. Konjevod, and M. V. Marathe. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the transims router. In ESA, pages 126--138, 2002. Google Scholar
- C. L. Barrett, R. Jacob, and M. V. Marathe. Formal-language-constrained path problems. SIAM J. Comput., 30(3):809--837, 2000. Google Scholar
- R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. In WEA, pages 303--318, 2008. Google Scholar
- D. Delling and D. Wagner. Landmark-based routing in dynamic graphs. In WEA, pages 52--65, 2007. Google Scholar
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.Google Scholar
- R. Geisberger. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Master's thesis, Institut fur Theoretische Informatik Universitat Karlsruhe, 2008.Google Scholar
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA, pages 319--333, 2008. Google Scholar
- A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In SODA, pages 156--165, 2005. Google Scholar
- A. V. Goldberg and R. F. Werneck. Computing point-to-point shortest paths from external memory. In ALENEX/ANALCO, pages 26--40, 2005.Google Scholar
- P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. In IEEE Transactions on System Science and Cybernetics, volume 4, 1968.Google Scholar
- M. Holzer, F. Schulz, and D. Wagner. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics, 13, 2008. Google Scholar
- S. Knopp, P. Sanders, D. Schultes, F. Schulz, and D. Wagner. Computing many-to-many shortest paths using highway hierarchies. In ALENEX, 2007.Google Scholar
- P. Sanders and D. Schultes. Engineering highway hierarchies. In ESA, pages 804--816, 2006. Google Scholar
- P. Sanders, D. Schultes, and C. Vetter. Mobile route planning. In ESA, pages 732--743, 2008. Google Scholar
- D. Schultes and P. Sanders. Dynamic highway-node routing. In WEA, pages 66--79, 2007. Google Scholar
Index Terms
- Graph indexing of road networks for shortest path queries with label restrictions
Recommendations
Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs
SIGMOD '16: Proceedings of the 2016 International Conference on Management of DataA variety of applications spanning various domains, e.g., social networks, transportation, and bioinformatics, have graphs as first-class citizens. These applications share a vital operation, namely, finding the shortest path between two nodes. In many ...
Processing time-dependent shortest path queries without pre-computed speed information on road networks
Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations ...
Generalization of Shortest Path Map
ITNG '10: Proceedings of the 2010 Seventh International Conference on Information Technology: New GenerationsWe consider the problem of constructing shortest path maps in two dimensions under angle constraint. Shortest path maps are used for planning short length paths from a fixed source point s to varying goal points. In the standard shortest path map the ...
Comments