Database Paper Browser

Back to papers

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
12752
Venue
VLDB
Year
2022
Pagerank
4.5490743e-05
Overall Rank
8,256 | 42.57%
DOI
10.14778/3551793.3551820

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
10,957 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 4.1945683e-05
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
11,065 Efficient kNN Search in Public Transportation Networks 2024 VLDB 4.1945683e-05
11,079 Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030040036
331 The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018 VLDB 0.00027214222
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
1,170 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013511856
1,654 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.000109978
1,821 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010423565
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
1,838 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010349881
2,201 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.3048105e-05
2,639 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3975113e-05
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7470184e-05
5,215 Relational Approach for Shortest Path Discovery over Large Graphs 2012 VLDB 5.6228603e-05
5,932 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2670741e-05
6,138 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.1915368e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,654 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.000109978
1,555 Efficient Route Planning on Public Transportation Networks: A Labelling Approach 2015 SIGMOD 0.00011395261
1,170 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013511856
4,745 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD 5.9573154e-05
5,597 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 5.4178241e-05
7,444 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 4.7281454e-05
1,230 Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011 VLDB 0.00013150837
6,138 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.1915368e-05
506 On Graph Query Optimization in Large Networks 2010 VLDB 0.00021475362
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030040036