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.00011336944
Overall Rank
1,252 | 91.59%
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.00025584127
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010973645
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010163696
1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9875545e-05
2,141 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9668034e-05
3,687 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0955331e-05
4,633 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4933316e-05
5,703 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0303375e-05
6,408 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7942038e-05
6,988 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6274541e-05
7,075 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.6064033e-05
7,302 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5602499e-05
9,809 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1257999e-05
11,204 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9793485e-05
11,311 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.9793485e-05
11,551 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9793485e-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.00022490994
303 Proximity Search in Databases 1998 VLDB 0.0002164278
382 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019485934
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018159715
990 Path Oracles for Spatial Networks 2009 VLDB 0.00012648672
1,426 On k-skip Shortest Paths 2011 SIGMOD 0.00010710481
Previous Page 1 / 1 Next

Semantically Similar Papers