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.00011325987
Overall Rank
1,250 | 91.63%
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
192 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025740385
1,346 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010949128
1,577 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010155939
1,653 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9588776e-05
2,150 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9509559e-05
3,676 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0882436e-05
4,631 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4784075e-05
5,699 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0139119e-05
5,899 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9376618e-05
7,008 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6061911e-05
7,031 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.6000241e-05
7,323 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5392408e-05
9,850 Fast Network K-function-based Spatial Analysis 2022 VLDB 5.1064323e-05
11,271 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9605343e-05
11,373 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.9605343e-05
11,606 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9605343e-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
269 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00022625826
303 Proximity Search in Databases 1998 VLDB 0.00021577595
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019655871
449 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018112854
993 Path Oracles for Spatial Networks 2009 VLDB 0.00012620373
1,430 On k-skip Shortest Paths 2011 SIGMOD 0.00010676829
Previous Page 1 / 1 Next

Semantically Similar Papers