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.00025740385
Overall Rank
192 | 98.72%
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 67 citing papers.

Rank Citing Paper Year Venue Pagerank
942 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00012936571
1,346 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010949128
1,577 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010155939
1,581 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 0.00010151896
1,613 Distance-generalized Core Decomposition 2019 SIGMOD 0.00010057822
1,624 Efficient Route Planning on Public Transportation Networks: A Labelling Approach 2015 SIGMOD 0.00010028661
2,201 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.8626226e-05
2,616 Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks 2017 VLDB 8.2017758e-05
2,744 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.0484475e-05
2,789 All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis 2014 PODS 7.996482e-05
2,794 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.987154e-05
3,066 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.6714389e-05
3,357 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.3652047e-05
3,555 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.1877332e-05
3,676 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0882436e-05
4,214 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7186746e-05
4,624 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.4807585e-05
4,631 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4784075e-05
4,805 Distributed Processing of k Shortest Path Queries over Dynamic Road Networks 2020 SIGMOD 6.3917568e-05
4,931 Diversified Top-k Route Planning in Road Network 2022 VLDB 6.3376097e-05
5,026 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.2965202e-05
5,215 Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints 2020 VLDB 6.2135023e-05
5,357 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.1514562e-05
5,409 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1320768e-05
5,571 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.0628752e-05
5,699 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0139119e-05
5,732 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.9963673e-05
5,735 Cache-Efficient Fork-Processing Patterns on Large Graphs 2021 SIGMOD 5.9957538e-05
5,893 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.9394451e-05
5,899 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9376618e-05
6,061 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.8831543e-05
6,192 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.8377174e-05
6,786 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 5.6657191e-05
6,829 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.6556888e-05
7,008 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6061911e-05
7,031 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.6000241e-05
7,323 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5392408e-05
7,769 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4391973e-05
8,085 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.3751128e-05
8,416 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3208725e-05
8,655 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.2794257e-05
9,200 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.1951474e-05
9,434 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 5.1649835e-05
9,578 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1419143e-05
9,649 MITra: A Framework for Multi-Instance Graph Traversal 2023 VLDB 5.1324359e-05
9,679 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 5.1258854e-05
9,850 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1064323e-05
10,290 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 5.031399e-05
10,361 On Scalable Computation of Graph Eccentricities 2022 SIGMOD 5.014328e-05
10,414 Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs 2027 SIGMOD 4.9605343e-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