Hub Labeling for Shortest Path Counting

Summary: Hub labeling for counting shortest paths via hub pushing; index size reduced by graph-reduction techniques. Theoretical results for select graph classes; empirical study shows query times in hundreds of microseconds on graphs with hundreds of millions of edges. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5251df28e91a50a6
Venue: SIGMOD
Year: 2020
Pagerank: 6.0303375e-05
Overall Rank: 5,703 | 61.66%
DOI: 10.1145/3318464.3389737

Incoming Non-self Citations Over Time

Authors

1. Yikai Zhang (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{zhang_sigmod20,
        title = {{Hub Labeling for Shortest Path Counting}},
        author = {Zhang, Yikai and Yu, Jeffrey Xu},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389737},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389737},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,336	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.1747873e-05
5,803	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.9893561e-05
11,204	Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks	2025	SIGMOD	4.9793485e-05
11,251	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.9793485e-05
11,580	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.9793485e-05
11,599	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019485934
1,232	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.0001141008
1,252	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011336944
1,340	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00010973645
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010877488
1,506	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010452205
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010163696
1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.9953879e-05
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9875545e-05
2,188	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8874739e-05
3,934	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.9172713e-05
7,075	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6064033e-05
7,323	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.5524474e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,803	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB
2	1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB
3	11,580	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
4	11,251	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB
5	11,204	Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks	2025	SIGMOD
6	1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
7	197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD
8	1,252	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
9	5,336	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
10	1,340	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB