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

Rank Citing Paper Year Venue Pagerank
10,573 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 4.9793485e-05
10,576 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 4.9793485e-05
10,685 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.9793485e-05
10,812 A Practical Sublinear Approximation for Group Steiner Tree 2026 VLDB 4.9793485e-05
11,204 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9793485e-05
11,251 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.9793485e-05
11,263 Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints 2025 VLDB 4.9793485e-05
11,449 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.9793485e-05
11,551 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9793485e-05
11,580 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9793485e-05
11,752 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 4.9793485e-05
11,775 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.9793485e-05
12,032 SpeakNav: Voice-based Route Description Language Understanding for Template-driven Path Search 2021 VLDB 4.9793485e-05
12,076 BOOMER: A Tool for Blending Visual P-Homomorphic Queries on Large Networks 2020 SIGMOD 4.9793485e-05
12,154 Answering Why-questions by Exemplars in Attributed Graphs 2019 SIGMOD 4.9793485e-05
12,419 CANDS: Continuous Optimal Navigation via Distributed Stream Processing 2015 VLDB 4.9793485e-05
Previous Page 2 / 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