DBScholar

Back to papers

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)

Paper ID
ha3930dfdc8e44b3c
Venue
SIGMOD
Year
2013
Pagerank
0.00025584127
Overall Rank
197 | 98.68%
DOI
10.1145/2463676.2465315

Incoming Non-self Citations Over Time

Authors

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 66 citing papers.

Rank Citing Paper Year Venue Pagerank
937 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00012977594
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010973645
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010163696
1,621 Efficient Route Planning on Public Transportation Networks: A Labelling Approach 2015 SIGMOD 0.00010054061
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9953879e-05
1,648 Distance-generalized Core Decomposition 2019 SIGMOD 9.9863775e-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
2,734 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.0789676e-05
2,852 All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis 2014 PODS 7.9412916e-05
2,943 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8314485e-05
3,055 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.6979859e-05
3,348 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.3926236e-05
3,562 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.2046519e-05
3,687 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0955331e-05
4,488 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5781787e-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
4,783 Distributed Processing of k Shortest Path Queries over Dynamic Road Networks 2020 SIGMOD 6.4159993e-05
4,906 Diversified Top-k Route Planning in Road Network 2022 VLDB 6.3616468e-05
5,000 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3202341e-05
5,188 Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints 2020 VLDB 6.2370687e-05
5,336 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.1747873e-05
5,554 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.0858703e-05
5,703 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0303375e-05
5,717 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 6.0191048e-05
5,734 Cache-Efficient Fork-Processing Patterns on Large Graphs 2021 SIGMOD 6.0137932e-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
6,045 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.9054678e-05
6,177 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.8598586e-05
6,408 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7942038e-05
6,765 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 5.6872079e-05
6,811 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.6744946e-05
6,988 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6274541e-05
7,075 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.6064033e-05
7,302 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5602499e-05
7,752 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4595236e-05
8,063 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.3954994e-05
8,393 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3410533e-05
8,629 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.2994494e-05
9,166 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.2148514e-05
9,400 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 5.1845732e-05
9,543 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1614165e-05
9,613 MITra: A Framework for Multi-Instance Graph Traversal 2023 VLDB 5.1519021e-05
9,809 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1257999e-05
10,255 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 5.050482e-05
10,328 On Scalable Computation of Graph Eccentricities 2022 SIGMOD 5.0333462e-05
10,455 Fast Estimation of Pairwise Biharmonic Distance on Graphs 2026 SIGMOD 4.9793485e-05
10,564 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 4.9793485e-05
Previous Page 1 / 2 Next

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.

Previous Page 1 / 1 Next

Semantically Similar Papers