Accelerating Shortest Path Counting on Road Networks

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

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.

Author Affiliations

@inproceedings{chen2025accelerating,
  title = {Accelerating Shortest Path Counting on Road Networks},
  author = {Chen, Zebin and Chen, Kaiyu and Wen, Dong and Yang, Zhengyi and Li, Wentao and Zhang, Ying},
  url = {http://dx.doi.org/10.1109/ICDE65448.2025.00262},
  doi = {10.1109/icde65448.2025.00262},
  booktitle = {2025 IEEE 41st International Conference on Data Engineering (ICDE)},
  publisher = {IEEE},
  year = {2025},
  month = May,
  pages = {3508-3521}
}