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: 6014
Venue: SIGMOD
Year: 2020
Pagerank: 6.1686653e-05
Overall Rank: 5,571 | 61.78%
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,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.3165129e-05
5,678	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	6.1246854e-05
10,788	Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks	2025	SIGMOD	5.093636e-05
10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	5.093636e-05
11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.093636e-05
11,271	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	5.093636e-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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011664469
1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011566372
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,336	Query Preserving Graph Compression	2012	SIGMOD	0.00011118804
1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010615297
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
3,857	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	7.0678455e-05
6,940	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.7331991e-05
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05

Semantically Similar Papers

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