Accelerating Shortest Path Counting on Road Networks
Authors:
- 19 May 2025
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3508-3521
Abstract
Counting the number of shortest paths between two query vertices on road networks has a wide range of applications and has recently drawn significant research attention. The state-of-the-art solution builds a tree-based index using the concept of tree decomposition. However, its performance deteriorates when the tree decomposition results in an unbalanced tree and may not perform well when the query vertices are close to each other. This paper aims to improve the efficiency of shortest path counting. We propose a novel indexing scheme that combines hub labeling with a balanced tree hierarchy. This approach significantly reduces the number of visited labels compared to the state-of-the-art solution. Furthermore, we introduce several optimizations to enhance the efficiency of index construction and minimize its size. Extensive experiments conducted on real-world road networks demonstrate that our method achieves up to 4.1 times higher query efficiency and reduces the index size by a factor of 2.35 compared to the state-of-the-art solution.Keywords
Funding Information
- ARC (DP230101445,DE240100668,LP210301046,DP210101393,DP230101445)
- NSFC (62302417)
This publication has 37 references indexed in Scilit:
- When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networksThe VLDB Journal, 2023
- Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled Graphs2022
- Hop-Constrained s-t Simple Path Enumeration in Large Uncertain Graphs2022
- Hierarchical Hub Labelings for Shortest Paths2012
- A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks2011
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks2008
- Treewidth: Characterizations, Applications, and Computations2006
- Dinitz’ Algorithm: The Original Version and Even’s Version2006
- Highway Hierarchies Hasten Exact Shortest Path Queries2005
- A note on two problems in connexion with graphsNumerische Mathematik, 1959