DBScholar

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
h9d4bc51ddb928c4f
Venue
SIGMOD
Year
2012
Pagerank
0.00011331798
Overall Rank
1,253 | 91.58%
DOI
10.1145/2213836.2213887

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{jin_sigmod12,
        title = {{A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs}},
        author = {Jin, Ruoming and Ruan, Ning and Xiang, Yang and Lee, Victor E.},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213887},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213887},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025572265
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.0001096845
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010158887
1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9828268e-05
2,143 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9625587e-05
3,689 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0921741e-05
4,636 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4902578e-05
5,705 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0274828e-05
6,411 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7914609e-05
6,991 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6247902e-05
7,053 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.6103309e-05
7,305 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5576178e-05
9,816 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1233734e-05
11,213 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9769913e-05
11,319 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.9769913e-05
11,557 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9769913e-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
274 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022480767
303 Proximity Search in Databases 1998 VLDB 0.00021632881
382 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019477423
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018151383
991 Path Oracles for Spatial Networks 2009 VLDB 0.00012642908
1,426 On k-skip Shortest Paths 2011 SIGMOD 0.00010705427
Previous Page 1 / 1 Next

Semantically Similar Papers