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.00011404678
Overall Rank
1,234 | 91.71%
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.0001096845
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9906562e-05
2,143 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9625587e-05
3,689 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0921741e-05
4,606 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.5019526e-05
4,636 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4902578e-05
4,676 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 6.4725032e-05
5,343 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.1718642e-05
5,705 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0274828e-05
6,411 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7914609e-05
6,991 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6247902e-05
7,379 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5369684e-05
7,774 TAREEG: A MapReduce-Based Web Service for Extracting Spatial Data from OpenStreetMap 2014 SIGMOD 5.4535136e-05
9,416 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.180378e-05
9,806 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.1233734e-05
9,816 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1233734e-05
10,501 ORDER: Optimal Routing with Path Indexing in Exchange Graph [Data-Intensive & Data Science Application] 2026 SIGMOD 4.9769913e-05
11,213 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9769913e-05
11,557 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9769913e-05
11,586 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9769913e-05
12,425 CANDS: Continuous Optimal Navigation via Distributed Stream Processing 2015 VLDB 4.9769913e-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.00018151383
953 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00012871412
991 Path Oracles for Spatial Networks 2009 VLDB 0.00012642908
1,270 Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011 VLDB 0.00011254207
1,426 On k-skip Shortest Paths 2011 SIGMOD 0.00010705427
3,704 Roads, Codes, and Spatiotemporal Queries 2004 PODS 7.0806334e-05
Previous Page 1 / 1 Next

Semantically Similar Papers