DBScholar

Back to papers

Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice

Summary: Arterial Hierarchy (AH) bridges theory and practice for road-network distance and shortest-path queries. It yields O~(log alpha) distance queries and O~(k+log alpha) shortest-path queries with moderate preprocessing, validated on networks up to 20M nodes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hf80a855befd4830b
Venue
SIGMOD
Year
2013
Pagerank
0.0001141008
Overall Rank
1,232 | 91.72%
DOI
10.1145/2463676.2465277

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{zhu_sigmod13,
        title = {{Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice}},
        author = {Zhu, Andy Diwen and Ma, Hui and Xiao, Xiaokui and Luo, Siqiang and Tang, Youze and Zhou, Shuigeng},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465277},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465277},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank Citing Paper Year Venue Pagerank
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010973645
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9953879e-05
2,141 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9668034e-05
3,687 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0955331e-05
4,604 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.505032e-05
4,633 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4933316e-05
4,674 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 6.4750983e-05
5,336 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.1747873e-05
5,703 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0303375e-05
6,408 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7942038e-05
6,988 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6274541e-05
7,377 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5395908e-05
7,765 TAREEG: A MapReduce-Based Web Service for Extracting Spatial Data from OpenStreetMap 2014 SIGMOD 5.4560963e-05
9,407 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.1828314e-05
9,799 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.1257999e-05
9,809 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1257999e-05
10,490 ORDER: Optimal Routing with Path Indexing in Exchange Graph [Data-Intensive & Data Science Application] 2026 SIGMOD 4.9793485e-05
11,204 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9793485e-05
11,551 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9793485e-05
11,580 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9793485e-05
12,419 CANDS: Continuous Optimal Navigation via Distributed Stream Processing 2015 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018159715
953 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00012877507
990 Path Oracles for Spatial Networks 2009 VLDB 0.00012648672
1,269 Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011 VLDB 0.00011259535
1,426 On k-skip Shortest Paths 2011 SIGMOD 0.00010710481
3,704 Roads, Codes, and Spatiotemporal Queries 2004 PODS 7.0839867e-05
Previous Page 1 / 1 Next

Semantically Similar Papers