Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation

Summary: Comprehensive, side-by-side evaluation of spatial-coherence-based and vertex-importance-based shortest-path and distance queries. Real road networks up to 20M vertices; analyzes preprocessing time, space, and query efficiency, revealing trade-offs and guidelines for method selection. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h35efc8448a16a425
Venue: VLDB
Year: 2012
Pagerank: 0.00012877507
Overall Rank: 953 | 93.60%
DOI: 10.14778/2140436.2140442

Incoming Non-self Citations Over Time

Authors

1. Lingkun Wu (Nanyang Technological University)
2. Xiaokui Xiao (Nanyang Technological University)
3. Dingxiong Deng (Fudan University)
4. Gao Cong (Nanyang Technological University)
5. Andy Diwen Zhu (Nanyang Technological University)
6. Shuigeng Zhou (Fudan University)

BibTeX Citation

@article{wu_vldb12,
        title = {{Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation}},
        author = {Wu, Lingkun and Xiao, Xiaokui and Deng, Dingxiong and Cong, Gao and Zhu, Andy Diwen and Zhou, Shuigeng},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {5},
        pages = {406--417},
        doi = {10.14778/2140436.2140442},
        url = {https://doi.org/10.14778/2140436.2140442},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,232	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.0001141008
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
2,188	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8874739e-05
2,602	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.2325477e-05
3,687	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0955331e-05
4,175	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.757832e-05
4,540	Incrementalizing Graph Algorithms	2021	SIGMOD	6.5508191e-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
5,336	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.1747873e-05
5,803	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.9893561e-05
5,896	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.9555883e-05
5,966	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB	5.9325005e-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
8,693	QARTA: An ML-based System for Accurate Map Services	2021	VLDB	5.2905577e-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
11,025	Are We There Yet? A Grand Tour of ETA Queries	2026	VLDB	4.9793485e-05
11,251	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.9793485e-05
11,311	Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks	2025	VLDB	4.9793485e-05
11,997	Optimizing Bipartite Matching in Real-World Applications by Incremental Cost Computation	2021	VLDB	4.9793485e-05
12,014	A Demonstration of QARTA: An ML-based System for Accurate Map Services	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
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
3,704	Roads, Codes, and Spatiotemporal Queries	2004	PODS	7.0839867e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,141	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB
2	5,966	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB
3	2,943	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD
4	7,377	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
5	4,906	Diversified Top-k Route Planning in Road Network	2022	VLDB
6	1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
7	1,269	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB
8	447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD
9	5,336	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
10	1,232	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD