Database Paper Browser

Back to papers

A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs

Summary: Highway-Centric Labeling for shortest-path queries in large sparse graphs, with highway-structure and bipartite cover. Outperforms 2-hop in index size and query time, with exact distances and bounded-accuracy approximations; validated on synthetic/real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4545
Venue
SIGMOD
Year
2012
Pagerank
0.00012259478
Overall Rank
1,385 | 90.38%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030020929
1,653 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.0001098717
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
2,547 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.5600506e-05
4,194 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.3640644e-05
5,255 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 5.5991117e-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,595 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 4.9949537e-05
7,271 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 4.7764555e-05
7,439 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7256836e-05
9,496 Fast Network K-function-based Spatial Analysis 2022 VLDB 4.3300131e-05
10,524 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.1905499e-05
10,677 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.1905499e-05
11,005 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.1905499e-05
Previous Page 1 / 1 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.

Rank Cited Paper Year Venue Pagerank
186 Proximity Search in Databases 1998 VLDB 0.0003618341
280 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029092277
377 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025074538
434 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00023277433
946 Path Oracles for Spatial Networks 2009 VLDB 0.00015117675
1,052 On k-skip Shortest Paths 2011 SIGMOD 0.00014403922
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,606 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 5.4126223e-05
10,878 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.1905499e-05
7,444 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 4.7236107e-05
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7414979e-05
784 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016648392
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
9,472 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 4.3300131e-05
6,595 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 4.9949537e-05
2,206 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.2958349e-05