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: 4606
Venue: SIGMOD
Year: 2012
Pagerank: 0.00011566372
Overall Rank: 1,232 | 91.55%
DOI: 10.1145/2213836.2213887

Incoming Non-self Citations Over Time

Authors

1. Ruoming Jin (Kent State University)
2. Ning Ruan (Kent State University)
3. Yang Xiang (Ohio State University)
4. Victor E. Lee (Kent State University)

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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
2,097	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	9.1725037e-05
3,612	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.2579119e-05
4,786	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.5083151e-05
5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.1686653e-05
6,292	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD	5.9251728e-05
6,844	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.7566172e-05
6,940	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.7331991e-05
7,158	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.6858492e-05
9,632	Fast Network K-function-based Spatial Analysis	2022	VLDB	5.2434488e-05
10,788	Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks	2025	SIGMOD	5.093636e-05
10,918	Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks	2025	VLDB	5.093636e-05
11,213	LION: Fast and High-Resolution Network Kernel Density Visualization	2024	VLDB	5.093636e-05

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.00022786599
301	Proximity Search in Databases	1998	VLDB	0.00022032878
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
968	Path Oracles for Spatial Networks	2009	VLDB	0.00012901559
1,386	On k-skip Shortest Paths	2011	SIGMOD	0.00010950754

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
2	11,097	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB
3	7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
4	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
5	4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
6	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
7	11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
8	9,619	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
9	6,292	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD
10	1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD