Dian Ouyang
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 hopbased solutions. However, the hierarchy-based solutions require a large search space for long-distance queries while the hop-based solutions result in a 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 destination based on the vertex hierarchy. We also propose an algorithm to construct the H2H-Index based on distance preserved graphs. The algorithm is further optimized by computing the labels based on the partially computed labels of other 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.
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Proc. of ISEA'11, pages 230--241, 2011. Google Scholar
Digital Library
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In Proc. of ESA'12, pages 24--35, 2012. Google ScholarDigital Library
- T. Akiba, Y. Iwata, K.-i. Kawarabayashi, and Y. Kawata. Fast shortest-path distance queries on road networks by pruned highway labeling. In Proc. of ALENEX'14, pages 147--154, 2014. Google ScholarDigital Library
- T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proc. of SIGMOD'13, pages 349--360, 2013. Google ScholarDigital Library
- T. Akiba, C. Sommer, and K.-i. Kawarabayashi. Shortest-path queries for complex networks: Exploiting low tree-width outside the core. In Proc. of EDBT'12, pages 144--155, 2012. Google ScholarDigital Library
- S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8(2):277--284, 1987. Google ScholarDigital Library
- S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8(2):277--284, 1987. Google ScholarDigital Library
- J. Arz, D. Luxen, and P. Sanders. Transit node routing reconsidered. In Proc. of SEA'13, pages 55--66, 2013.Google ScholarCross Ref
- H. Bast, D. Delling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. In Algorithm Engineering - Selected Results and Surveys, pages 19--80. 2016.Google ScholarCross Ref
- H. Bast, S. Funke, and D. Matijević. Transit: ultrafast shortest-path queries with linear-time preprocessing. In 9th DIMACS Implementation Challenge-Shortest Path, 2006.Google Scholar
- M. A. Bender and M. Farach-Colton. The lca problem revisited. In Proc. of LASTI'00, pages 88--94, 2000. Google ScholarDigital Library
- H. L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 11(1--2):1--21, 1993.Google Scholar
- H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305--1317, 1996. Google ScholarDigital Library
- H. L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Graph-Theoretic Concepts in Computer Science, pages 1--14, 2006. Google ScholarDigital Library
- L. Chang, J. X. Yu, L. Qin, H. Cheng, and M. Qiao. The exact distance to destination in undirected world. The VLDB Journal, 21(6):869--888, 2012. Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proc. of WEA'08, pages 319--333, 2008. Google ScholarDigital Library
- A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In Proc. of SODA'05, pages 156--165, 2005. Google ScholarDigital Library
- R. Halin. S-functions for graphs. Journal of Geometry, 8:171--186, 1976.Google ScholarCross Ref
- R. Hassin. Approximation schemes for the restricted shortest path problem. Math. Oper. Res., 17(1):36--42, 1992.Google ScholarCross Ref
- M. Jiang, A. W. Fu, R. C. Wong, and Y. Xu. Hop doubling label indexing for pointto- point distance querying on scale-free networks. PVLDB, 7(12):1203--1214, 2014. Google ScholarDigital Library
- S. Jung and S. Pramanik. An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng., 14(5):1029--1046, 2002. Google ScholarDigital Library
- A. M. C. A. Koster, H. L. Bodlaender, and S. P. M. van Hoesel. Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics, 8:54--57, 2001.Google ScholarCross Ref
- T. Maehara, T. Akiba, Y. Iwata, and K. Kawarabayashi. Computing personalized pagerank quickly by exploiting graph structures. PVLDB, 7(12):1023--1034, 2014. Google ScholarDigital Library
- S. Mozes and C. Sommer. Exact distance oracles for planar graphs. In Proc. of SODA'12, pages 209--222, 2012. Google ScholarDigital Library
- M. N. Rice and V. J. Tsotras. Graph indexing of road networks for shortest path queries with label restrictions. PVLDB, 4(2):69--80, 2010. Google ScholarDigital Library
- N. Robertson and P. D. Seymour. Graph minors iii: Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49--64, 1984.Google ScholarCross Ref
- H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In Proc. of SIGMOD'08, pages 43--54, 2008. Google ScholarDigital Library
- P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proc. of ESA'05, pages 568--579, 2005. Google ScholarDigital Library
- J. Sankaranarayanan and H. Samet. Query processing using distance oracles for spatial networks. IEEE Trans. Knowl. Data Eng., 22(8):1158--1175, 2010. Google ScholarDigital Library
- J. Sankaranarayanan, H. Samet, and H. Alborzi. Path oracles for spatial networks. PVLDB, 2(1):1210--1221, 2009. Google ScholarDigital Library
- S. Wang, W. Lin, Y. Yang, X. Xiao, and S. Zhou. Efficient route planning on public transportation networks: A labelling approach. In Proc. of SIGMOD'15, pages 967--982, 2015. Google ScholarDigital Library
- F. Wei. Tedi: efficient shortest path query answering on graphs. In Proc. of SIGMOD'10, pages 99--110. ACM, 2010. Google ScholarDigital Library
- H. Wu, Y. Huang, J. Cheng, J. Li, and Y. Ke. Reachability and time-based path queries in temporal graphs. In Proc. of ICDE'16, pages 145--156, 2016.Google ScholarCross Ref
- L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, and S. Zhou. Shortest path and distance queries on road networks: An experimental evaluation. PVLDB, 5(5):406-- 417, 2012. Google ScholarDigital Library
- Y. Xiang. Answering exact distance queries on real-world graphs with bounded performance guarantees. The VLDB Journal, 23(5):677--695, 2014. Google ScholarDigital Library
- A. D. Zhu, H. Ma, X. Xiao, S. Luo, Y. Tang, and S. Zhou. Shortest path and distance queries on road networks: Towards bridging theory and practice. In Proc. of SIGMOD'13, pages 857--868, 2013. Google ScholarDigital Library
Index Terms
- When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks
Recommendations
When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks
AbstractComputing 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 ...
Scaling Up Distance Labeling on Graphs with Core-Periphery Properties
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of DataIn indexing a graph for distance queries, distance labeling is a common practice; in particular, 2-hop labeling which guarantees the exactness of the query results is widely adopted. When it comes to a massive real graph with a relatively large ...
Efficient Shortest Distance Query Processing in Road Networks for Spatially Skewed Workloads
SIGSPATIAL '21: Proceedings of the 29th International Conference on Advances in Geographic Information SystemsShortest distance computing in road networks is an essential component in a range of applications. As a well-adopted method, 2-hop labeling assigns each vertex a label and enables the distance computation only by a sort-merge join on the labels. However,...
Comments