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: 10676
Venue: VLDB
Year: 2012
Pagerank: 0.00013028107
Overall Rank: 949 | 93.50%
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 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011664469
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
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
2,555	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.4184379e-05
3,612	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.2579119e-05
4,135	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.8814581e-05
4,443	Incrementalizing Graph Algorithms	2021	SIGMOD	6.7004839e-05
4,541	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.6397712e-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,678	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	6.1246854e-05
5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	6.0896788e-05
5,851	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB	6.0659596e-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
8,525	QARTA: An ML-based System for Accurate Map Services	2021	VLDB	5.4119882e-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
10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	5.093636e-05
10,918	Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks	2025	VLDB	5.093636e-05
11,692	Optimizing Bipartite Matching in Real-World Applications by Incremental Cost Computation	2021	VLDB	5.093636e-05
11,710	A Demonstration of QARTA: An ML-based System for Accurate Map Services	2021	VLDB	5.093636e-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
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
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
3,637	Roads, Codes, and Spatiotemporal Queries	2004	PODS	7.2339626e-05

Semantically Similar Papers

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