Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Summary: Pruned Landmark Labeling for exact shortest-path queries on large networks; BFS with pruning reduces label sizes and search space. Bit-parallelism runs 32–64 BFSs simultaneously, enabling scalable, exact distances on graphs with hundreds of millions of edges and competitive query times. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Takuya Akiba (University of Tokyo)
- 2. Yoichi Iwata (University of Tokyo)
- 3. Yuichi Yoshida (National Institute of Informatics; Preferred Infrastructure, Inc)
BibTeX Citation
@inproceedings{akiba_sigmod13,
title = {{Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling}},
author = {Akiba, Takuya and Iwata, Yoichi and Yoshida, Yuichi},
series = {{SIGMOD} '13},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2463676.2465315},
url = {https://dl.acm.org/doi/10.1145/2463676.2465315},
year = {2013}
}
Incoming Citations (Sorted by Pagerank)
Showing 50 of 65 citing papers.
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 |
|---|---|---|---|---|
| 3 | Pregel: A System for Large-Scale Graph Processing | 2010 | SIGMOD | 0.0012250108 |
| 272 | BLINKS: Ranked Keyword Searches on Graphs | 2007 | SIGMOD | 0.00022695855 |
| 370 | TEDI: Efficient Shortest Path Query Answering on Graphs | 2010 | SIGMOD | 0.00019937972 |
| 1,232 | A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs | 2012 | SIGMOD | 0.00011566372 |
| 1,336 | Query Preserving Graph Compression | 2012 | SIGMOD | 0.00011118804 |
| 2,200 | Efficient Network-Aware Search in Collaborative Tagging Sites | 2008 | VLDB | 8.9664473e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,208 | Efficient Shortest Path Counting on Large Road Networks | 2022 | VLDB |
| 2 | 6,603 | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond | 2020 | VLDB |
| 3 | 7,211 | Toward a Distance Oracle for Billion-Node Graphs | 2014 | VLDB |
| 4 | 8,493 | Top-K Nearest Keyword Search on Large Graphs | 2013 | VLDB |
| 5 | 7,226 | Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach | 2022 | VLDB |
| 6 | 352 | On Graph Query Optimization in Large Networks | 2010 | VLDB |
| 7 | 1,232 | A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs | 2012 | SIGMOD |
| 8 | 2,152 | Scaling Distance Labeling on Small-World Networks | 2019 | SIGMOD |
| 9 | 5,784 | Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks | 2021 | SIGMOD |
| 10 | 5,678 | Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement | 2022 | VLDB |