Document Open Access Logo

Algorithms for Landmark Hub Labeling

Author Sabine Storandt

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.5.pdf
  • Filesize: 0.63 MB
  • 17 pages

Document Identifiers

Author Details

Sabine Storandt
  • Universität Konstanz, Germany

Cite As Get BibTex

Sabine Storandt. Algorithms for Landmark Hub Labeling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.5

Abstract

Landmark-based routing and Hub Labeling (HL) are shortest path planning techniques, both of which rely on storing shortest path distances between selected pairs of nodes in a preprocessing phase to accelerate query answering. In Landmark-based routing, stored distances to landmark nodes are used to obtain distance lower bounds that guide A* search from node s to node t. With HL, tight upper bounds for shortest path distances between any s-t-pair can be interfered from their stored node labels, making HL an efficient distance oracle. However, for shortest path retrieval, the oracle has to be called once per edge in said path. Furthermore, HL often suffers from a large space consumption as many node pair distances have to be stored in the labels to allow for correct query answering. In this paper, we propose a novel technique, called Landmark Hub Labeling (LHL), which integrates the landmark concept into HL. We prove better worst-case path retrieval times for LHL in case it is path-consistent (a new labeling property we introduce). Moreover, we design efficient (approximation) algorithms that produce path-consistent LHL with small label size and provide parametrized upper bounds, depending on the highway dimension h or the geodesic transversal number gt of the graph. Finally, we show that the space consumption of LHL is smaller than that of (hierarchical) HL, both in theory and in experiments on real-world road networks.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Hub Labeling
  • Landmark
  • Geodesic
  • Hitting Set
  • Highway Dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Vc-dimension and shortest path algorithms. In International Colloquium on Automata, Languages, and Programming, pages 690-699. Springer, 2011. Google Scholar
  2. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension and provably efficient shortest path algorithms. Journal of the ACM (JACM), 63(5):1-26, 2016. Google Scholar
  3. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato Fonseca F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Proc. 10th Int. Symp. Experimental Algorithms (SEA '11), volume 6630 of Lecture Notes in Computer Science, pages 230-241. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20662-7_20.
  4. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato Fonseca F. Werneck. Hierarchical hub labelings for shortest paths. In Proc. 20th Ann. Europ. Symp. Algorithms (ESA '12), volume 7501 of Lecture Notes in Computer Science, pages 24-35. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_4.
  5. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proc. ACM SIGMOD Int. Conf. Management of Data (SIGMOD '13), pages 349-360. ACM, 2013. URL: https://doi.org/10.1145/2463676.2465315.
  6. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In Proc. 23rd Int. Conf. World Wide Web (WWW '14), pages 237-248. ACM, 2014. URL: https://doi.org/10.1145/2566486.2568007.
  7. Maxim A. Babenko, Andrew V. Goldberg, Haim Kaplan, Ruslan Savchenko, and Mathias Weller. On the complexity of hub labeling (extended abstract). In Proc. 40th Int. Symp. Mathematical Foundations of Computer Science (MFCS '15), volume 9235 of Lecture Notes in Computer Science, pages 62-74. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48054-0_6.
  8. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. Route planning in transportation networks. In Algorithm engineering, pages 19-80. Springer, 2016. Google Scholar
  9. Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner. Preprocessing speed-up techniques is hard. In International Conference on Algorithms and Complexity, pages 359-370. Springer, 2010. Google Scholar
  10. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645:112-127, 2016. Google Scholar
  11. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. Journal of Experimental Algorithmics (JEA), 15:2-1, 2010. Google Scholar
  12. Johannes Blum. Hierarchy of transportation network parameters and hardness results. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  13. Zitong Chen, Ada Wai-Chee Fu, Minhao Jiang, Eric Lo, and Pengfei Zhang. P2H: efficient distance querying on road networks by projected vertex separators. In Proc. 2021 Int. Conf. Management of Data (SIGMOD '21), pages 313-325. ACM, 2021. URL: https://doi.org/10.1145/3448016.3459245.
  14. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5):1338-1355, 2003. URL: https://doi.org/10.1137/S0097539702403098.
  15. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Robust distance queries on massive networks. In Proc. 22th Ann. Europ. Symp. Algorithms (ESA '14), volume 8737 of Lecture Notes in Computer Science, pages 321-333. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_27.
  16. Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko, and Renato F. Werneck. Hub labels: Theory and practice. In Proc. 13th Int. Symp. Experimental Algorithms (SEA '14), volume 8504 of Lecture Notes in Computer Science, pages 259-270. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07959-2_22.
  17. Daniel Delling, Andrew V Goldberg, and Renato F Werneck. Hub label compression. In Proc. 12th Int. Symp. Experimental Algorithms (SEA '13), volume 7933 of Lecture Notes in Computer Science, pages 18-29. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_4.
  18. Daniel Delling and Giacomo Nannicini. Core routing on dynamic time-dependent road networks. INFORMS Journal on Computing, 24(2):187-201, 2012. Google Scholar
  19. Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. Highway hierarchies star. In The Shortest Path Problem, pages 141-174, 2006. Google Scholar
  20. Daniel Delling and Dorothea Wagner. Landmark-based routing in dynamic graphs. In International Workshop on Experimental and Efficient Algorithms, pages 52-65. Springer, 2007. Google Scholar
  21. Alexandros Efentakis and Dieter Pfoser. Optimizing landmark-based routing and preprocessing. In Proceedings of the Sixth ACM SIGSPATIAL International Workshop on Computational Transportation Science, pages 25-30, 2013. Google Scholar
  22. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, 2012. URL: https://doi.org/10.1287/trsc.1110.0401.
  23. Andrew V Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In SODA, volume 5, pages 156-165. Citeseer, 2005. Google Scholar
  24. Andrew V Goldberg, Haim Kaplan, and Renato F Werneck. Better landmarks within reach. In International Workshop on Experimental and Efficient Algorithms, pages 38-51. Springer, 2007. Google Scholar
  25. Andrew V Goldberg and Renato Fonseca F Werneck. Computing point-to-point shortest paths from external memory. In ALENEX/ANALCO, pages 26-40, 2005. Google Scholar
  26. Daniel Harabor and Peter Stuckey. Forward search in contraction hierarchies. In International Symposium on Combinatorial Search, volume 9(1), 2018. Google Scholar
  27. Famei He, Yina Xu, Xuren Wang, and Anran Feng. Alt-based route planning in dynamic time-dependent road networks. In Proceedings of the 2019 2nd International Conference on Machine Learning and Machine Intelligence, pages 35-39, 2019. Google Scholar
  28. Samir Khuller and Barna Saha. On finding dense subgraphs. In International colloquium on automata, languages, and programming, pages 597-608. Springer, 2009. Google Scholar
  29. Adrian Kosowski and Laurent Viennot. Beyond highway dimension: small distance labels using tree skeletons. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1462-1478. SIAM, 2017. Google Scholar
  30. Lei Li, Sibo Wang, and Xiaofang Zhou. Time-dependent hop labeling on road network. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 902-913. IEEE, 2019. Google Scholar
  31. Paul Manuel, Boštjan Brešar, and Sandi Klavžar. The geodesic-transversal problem. Applied Mathematics and Computation, 413:126621, 2022. Google Scholar
  32. Dian Ouyang, Lu Qin, Lijun Chang, Xuemin Lin, Ying Zhang, and Qing Zhu. When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks. In Proc. 2018 Int. Conf. Management of Data (SIGMOD '18), pages 709-724. ACM, 2018. URL: https://doi.org/10.1145/3183713.3196913.
  33. Genaro Peque, Junji Urata, and Takamasa Iryo. Implementing an alt algorithm for large-scale time-dependent networks. In 22nd International Conference of Hong Kong Society for Transportation Studies: Transport and Society, HKSTS 2017, pages 515-522. Hong Kong Society for Transportation Studies Limited, 2017. Google Scholar
  34. Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. Fast shortest path distance estimation in large networks. In Proceedings of the 18th ACM conference on Information and knowledge management, pages 867-876, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact