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
4784
Venue
SIGMOD
Year
2013
Pagerank
0.00025813775
Overall Rank
195 | 98.67%
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 65 citing papers.

Rank Citing Paper Year Venue Pagerank
927 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00013161079
1,309 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00011210911
1,553 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.0001037809
1,598 Efficient Route Planning on Public Transportation Networks: A Labelling Approach 2015 SIGMOD 0.00010242826
1,613 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 0.00010216983
1,640 Distance-generalized Core Decomposition 2019 SIGMOD 0.00010153865
2,152 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 9.0778596e-05
2,555 Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks 2017 VLDB 8.4184379e-05
2,700 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.2411888e-05
2,792 All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis 2014 PODS 8.1191853e-05
2,871 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 8.0110616e-05
3,018 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.8473755e-05
3,278 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.5712342e-05
3,545 Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning 2021 VLDB 7.3249967e-05
3,612 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.2579119e-05
4,403 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7229209e-05
4,541 Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs 2014 VLDB 6.6397712e-05
4,685 Distributed Processing of k Shortest Path Queries over Dynamic Road Networks 2020 SIGMOD 6.5628805e-05
4,786 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.5083151e-05
4,807 Diversified Top-k Route Planning in Road Network 2022 VLDB 6.4992836e-05
5,044 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3883109e-05
5,071 Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints 2020 VLDB 6.3761034e-05
5,208 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.3165129e-05
5,415 Making Graphs Compact by Lossless Contraction 2021 SIGMOD 6.2255551e-05
5,571 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.1686653e-05
5,590 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 6.1557283e-05
5,612 Cache-Efficient Fork-Processing Patterns on Large Graphs 2021 SIGMOD 6.1501992e-05
5,678 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1246854e-05
5,784 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 6.0896788e-05
5,938 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 6.0343238e-05
6,292 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9251728e-05
6,603 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.824568e-05
6,728 BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks 2018 SIGMOD 5.7898807e-05
6,844 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.7566172e-05
6,940 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.7331991e-05
7,158 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.6858492e-05
7,322 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 5.644647e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-05
7,976 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.5152959e-05
8,911 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.3483178e-05
9,003 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.3345443e-05
9,118 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3201316e-05
9,334 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 5.2884486e-05
9,364 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.2798829e-05
9,432 MITra: A Framework for Multi-Instance Graph Traversal 2023 VLDB 5.2701501e-05
9,632 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.2434488e-05
10,101 On Scalable Computation of Graph Eccentricities 2022 SIGMOD 5.1488731e-05
10,240 Fast Estimation of Pairwise Biharmonic Distance on Graphs 2026 SIGMOD 5.093636e-05
10,366 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 5.093636e-05
10,376 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 5.093636e-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