Efficient Shortest Path Counting on Large Road Networks
- Publisher:
- Association for Computing Machinery (ACM)
- Publication Type:
- Journal Article
- Citation:
- Proceedings of the VLDB Endowment, 2022, 15, (10), pp. 2098-2110
- Issue Date:
- 2022-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 realworld networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.
Please use this identifier to cite or link to this item: