Database Paper Browser

Back to papers

An Experimental Study on Hub Labeling based Shortest Path Algorithms

Summary: Comprehensive experimental study of state-of-the-art hub labeling (HL) techniques for shortest-path queries, examining efficiency, effectiveness, and applicability. Introduces Significant path based Hub Pushing (SHP), a lightweight method that drastically reduces indexing time while preserving fast query throughput, with extensive HL vs. alternative methods benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
11756
Venue
VLDB
Year
2018
Pagerank
0.000109978
Overall Rank
1,654 | 88.50%
DOI
10.1145/3164135.3164141

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank Citing Paper Year Venue Pagerank
2,547 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.5683079e-05
2,639 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3975113e-05
3,342 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.197276e-05
4,193 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.37019e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
5,932 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2670741e-05
6,494 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.0417258e-05
6,795 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9242446e-05
6,973 The Simpler The Better: An Indexing Approach for Shared-Route Planning Queries 2020 VLDB 4.878479e-05
7,441 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7302202e-05
7,444 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 4.7281454e-05
8,256 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.5490743e-05
8,967 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4190656e-05
9,078 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 4.400728e-05
9,495 Fast Network K-function-based Spatial Analysis 2022 VLDB 4.3341665e-05
9,680 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 4.3047774e-05
10,516 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.1945683e-05
10,584 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.1945683e-05
10,874 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.1945683e-05
11,002 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.1945683e-05
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
11,239 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 4.1945683e-05
11,264 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.1945683e-05
11,376 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 4.1945683e-05
11,499 Fast Augmentation Algorithms for Network Kernel Density Visualization 2021 VLDB 4.1945683e-05
11,532 SpeakNav: Voice-based Route Description Language Understanding for Template-driven Path Search 2021 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030040036
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
1,170 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013511856
1,378 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012294512
1,690 Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013 SIGMOD 0.00010904736
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
1,838 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010349881
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,594 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 4.999751e-05
8,967 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4190656e-05
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
2,201 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.3048105e-05
7,444 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 4.7281454e-05
1,378 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012294512
9,470 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 4.3341665e-05
8,256 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.5490743e-05
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
5,932 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2670741e-05