Abstract
Computing the shortest distance between two vertices is a fundamental problem in road networks. Since a direct search using the Dijkstra’s algorithm results in a large search space, researchers resort to indexing-based approaches. State-of-the-art indexing-based solutions can be categorized into hierarchy-based solutions and hop-based solutions. However, the hierarchy-based solutions require large search space for long-distance queries, while the hop-based solutions result in high computational waste for short-distance queries. To overcome the drawbacks of both solutions, in this paper, we propose a novel hierarchical 2-hop index (H2H-Index) which assigns a label for each vertex and at the same time preserves a hierarchy among all vertices. With the H2H-Index, we design an efficient query processing algorithm with performance guarantees by visiting part of the labels for the source and the destination based on the hierarchy. We propose a novel algorithm to construct the H2H-Indexbased on distance preserved graphs. We also extend the H2H-Indexand propose a set of algorithms to identify the shortest path between vertices. We conducted extensive performance studies using large real road networks including the whole USA road network. The experimental results demonstrate that our approach can achieve a speedup of an order of magnitude in query processing compared to the state-of-the-art while consuming comparable indexing time and index size.
Similar content being viewed by others
References
Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths in road networks. In Proc. of ISEA’11, pages 230–241, (2011)
Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In Proc. of ESA’12, pages 24–35, (2012)
Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.F.: Highway dimension, shortest paths, and provably efficient algorithms. In M. Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 782–793. SIAM, (2010)
Akiba, T., Iwata, Y., Kawarabayashi, K.-i., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. In Proc. of ALENEX’14, pages 147–154, (2014)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algeb. Discret. Methods 8(2), 277–284 (1987)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algeb. Discret. Methods 8(2), 277–284 (1987)
Arz, J., Luxen, D., Sanders, P.: Transit node routing reconsidered. In Proc. of SEA’13, pages 55–66, (2013)
Bast, H., Delling, D., Goldberg, A.V., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks. In Algorithm Engineering - Selected Results and Surveys, pages 19–80. (2016)
Bast, H., Funke, S., Matijević, D.: Transit: ultrafast shortest-path queries with linear-time preprocessing. In 9th DIMACS Implementation Challenge—Shortest Path, (2006)
Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM, (2007)
Bender, M.A., Farach-Colton, M.: The lca problem revisited. In Proc. of LASTI’00, pages 88–94, (2000)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1–2), 1–21 (1993)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In Graph-Theoretic Concepts in Computer Science, pages 1–14, (2006)
Chang, L., Yu, J.X., Qin, L., Cheng, H., Qiao, M.: The exact distance to destination in undirected world. VLDB J. 21(6), 869–888 (2012)
Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In D. Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 937–946. ACM/SIAM, (2002)
Feldmann, A.E., Fung, W.S., Könemann, J., Post, I.: A (1+\(\epsilon \))-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J. Comput. 47(4), 1667–1704 (2018)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proc. of WEA’08, pages 319–333, (2008)
Goldberg, A.V., Harrelson, C.: Computing the shortest path: A search meets graph theory. In Proc. of SODA’05, pages 156–165, (2005)
Halin, R.: S-functions for graphs. J. Geom. 8, 171–186 (1976)
Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029–1046 (2002)
Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. Electron. Notes Discrete Math. 8, 54–57 (2001)
Li, Y., U, L.H., Yiu, M.L., Kou, N.M.: An experimental study on hub labeling based shortest path algorithms. Proc. VLDB Endow., 11(4):445–457, (2017)
Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In Proc. of SODA’12, pages 209–222, (2012)
Ouyang, D., Qin, L., Chang, L., Lin, X., Zhang, Y., Zhu, Q.: When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks. In SIGMOD, pages 709–724, (2018)
Robertson, N., Seymour, P.D.: Graph minors iii: Planar tree-width. J. Comb. Theory, Ser. B 36(1), 49–64 (1984)
Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In Proc. of SIGMOD’08, pages 43–54, (2008)
Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In Proc. of ESA’05, pages 568–579, (2005)
Sankaranarayanan, J., Samet, H.: Query processing using distance oracles for spatial networks. IEEE Trans. Knowl. Data Eng. 22(8), 1158–1175 (2010)
Sankaranarayanan, J., Samet, H., Alborzi, H.: Path oracles for spatial networks. PVLDB 2(1), 1210–1221 (2009)
Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. PVLDB 5(5), 406–417 (2012)
Zhu, A.D., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path and distance queries on road networks: Towards bridging theory and practice. In Proc. of SIGMOD’13, pages 857–868, (2013)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Ouyang, D., Wen, D., Qin, L. et al. When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks. The VLDB Journal 32, 1263–1287 (2023). https://doi.org/10.1007/s00778-023-00789-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-023-00789-x