Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement

Summary: Compares traversal-based and extension-based shortest-path methods on graphs, detailing space-time trade-offs and cost of augmented indexes. Proposes Monotonic Landmark Labeling (MLL) to bound index space and guarantee query-time, guiding method choice. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12940
Venue: VLDB
Year: 2022
Pagerank: 6.1246854e-05
Overall Rank: 5,678 | 61.05%
DOI: 10.14778/3551793.3551820

Incoming Non-self Citations Over Time

Authors

1. Junhua Zhang (University of Technology Sydney)
2. Wentao Li (University of Technology Sydney)
3. Long Yuan (Nanjing University)
4. Lu Qin (University of Technology Sydney)
5. Ying Zhang (University of Technology Sydney)
6. Lijun Chang (University of Sydney)

BibTeX Citation

@article{zhang_vldb22,
        title = {{Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement}},
        author = {Zhang, Junhua and Li, Wentao and Yuan, Long and Qin, Lu and Zhang, Ying and Chang, Lijun},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {11},
        pages = {2640--2652},
        doi = {10.14778/3551793.3551820},
        url = {https://doi.org/10.14778/3551793.3551820},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,911	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.3483178e-05
10,278	ORDER: Optimal Routing with Path Indexing in Exchange Graph [Data-Intensive & Data Science Application]	2026	SIGMOD	5.093636e-05
11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.093636e-05
11,272	Efficient kNN Search in Public Transportation Networks	2024	VLDB	5.093636e-05
11,285	Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013028107
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00011112799
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7229209e-05
4,977	Relational Approach for Shortest Path Discovery over Large Graphs	2012	VLDB	6.4166233e-05
5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.1686653e-05
5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	6.0896788e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB
2	1,598	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD
3	949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
4	4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD
5	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
6	7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
7	1,251	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB
8	5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD
9	352	On Graph Query Optimization in Large Networks	2010	VLDB
10	195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD