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
11757
Venue
VLDB
Year
2018
Pagerank
0.0001098717
Overall Rank
1,653 | 88.52%
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.5600506e-05
2,643 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.3894193e-05
3,346 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.1903469e-05
4,194 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.3640644e-05
5,548 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4445937e-05
5,933 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2620152e-05
6,491 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.0368875e-05
6,796 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9195203e-05
6,972 The Simpler The Better: An Indexing Approach for Shared-Route Planning Queries 2020 VLDB 4.8737965e-05
7,439 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7256836e-05
7,444 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 4.7236107e-05
8,252 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.544713e-05
8,973 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4148296e-05
9,074 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 4.3965098e-05
9,496 Fast Network K-function-based Spatial Analysis 2022 VLDB 4.3300131e-05
9,680 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 4.3006524e-05
10,525 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.1905499e-05
10,592 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.1905499e-05
10,878 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.1905499e-05
11,005 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.1905499e-05
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
11,241 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 4.1905499e-05
11,266 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.1905499e-05
11,378 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 4.1905499e-05
11,503 Fast Augmentation Algorithms for Network Kernel Density Visualization 2021 VLDB 4.1905499e-05
11,536 SpeakNav: Voice-based Route Description Language Understanding for Template-driven Path Search 2021 VLDB 4.1905499e-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.00030020929
377 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025074538
1,173 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013501079
1,385 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012259478
1,694 Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013 SIGMOD 0.00010870205
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349
1,843 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010340277
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,595 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 4.9949537e-05
8,973 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4148296e-05
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349
2,206 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.2958349e-05
7,444 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 4.7236107e-05
1,385 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00012259478
9,472 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 4.3300131e-05
8,252 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.544713e-05
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
5,933 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2620152e-05