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
4748
Venue
SIGMOD
Year
2013
Pagerank
0.00011664469
Overall Rank
1,205 | 91.74%
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,309 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00011210911
1,613 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 0.00010216983
2,097 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 9.1725037e-05
3,612 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.2579119e-05
4,541 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.6397712e-05
4,573 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 6.6226156e-05
4,786 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.5083151e-05
5,208 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.3165129e-05
5,571 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.1686653e-05
6,292 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9251728e-05
6,844 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.7566172e-05
7,226 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.6667372e-05
7,616 TAREEG: A MapReduce-Based Web Service for Extracting Spatial Data from OpenStreetMap 2014 SIGMOD 5.5811298e-05
9,229 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.3017894e-05
9,619 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.2434488e-05
9,632 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.2434488e-05
10,278 ORDER: Optimal Routing with Path Indexing in Exchange Graph [Data-Intensive & Data Science Application] 2026 SIGMOD 5.093636e-05
10,788 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 5.093636e-05
11,213 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 5.093636e-05
11,248 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 5.093636e-05
12,126 CANDS: Continuous Optimal Navigation via Distributed Stream Processing 2015 VLDB 5.093636e-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
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018532516
949 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013028107
968 Path Oracles for Spatial Networks 2009 VLDB 0.00012901559
1,251 Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011 VLDB 0.00011484136
1,386 On k-skip Shortest Paths 2011 SIGMOD 0.00010950754
3,637 Roads, Codes, and Spatiotemporal Queries 2004 PODS 7.2339626e-05
Previous Page 1 / 1 Next

Semantically Similar Papers