Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks

Summary: Hop Doubling Labeling for point-to-point distance querying on scale-free graphs; novel hop-doubling index for directed/undirected, unweighted networks. Bounds on index size, compute and I/O costs derived from scale-free properties; empirically outperforms state-of-the-art and scales to graphs orders of magnitude larger. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hfbb33f2caa5de42c
Venue: VLDB
Year: 2014
Pagerank: 0.00010158887
Overall Rank: 1,585 | 89.35%
DOI: 10.14778/2733004.2733012
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Minhao Jiang (Hong Kong University of Science and Technology)
2. Ada Wai-Chee Fu (Chinese University of Hong Kong)
3. Raymond Chi-Wing Wong (Hong Kong University of Science and Technology)
4. Yanyan Xu (Chinese University of Hong Kong)

BibTeX Citation

@article{jiang_vldb14,
        title = {{Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks}},
        author = {Jiang, Minhao and Fu, Ada Wai-Chee and Wong, Raymond Chi-Wing and Xu, Yanyan},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {12},
        pages = {1203--1214},
        doi = {10.14778/2733004.2733012},
        url = {https://doi.org/10.14778/2733004.2733012},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
937	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012971451
1,340	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.0001096845
1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.9906562e-05
2,190	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8832666e-05
2,944	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.8277412e-05
3,689	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0921741e-05
4,491	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.5750647e-05
5,004	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3172422e-05
5,705	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0274828e-05
5,804	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.9865208e-05
6,962	Towards Maximum Independent Sets on Massive Graphs	2015	VLDB	5.630587e-05
6,991	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6247902e-05
7,053	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6103309e-05
7,756	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4570169e-05
9,175	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2123828e-05
9,542	SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries	2017	VLDB	5.1612403e-05
10,575	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.9769913e-05
11,213	Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks	2025	SIGMOD	4.9769913e-05
11,586	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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.00025572265
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019477423
447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018151383
991	Path Oracles for Spatial Networks	2009	VLDB	0.00012642908
1,253	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011331798
1,426	On k-skip Shortest Paths	2011	SIGMOD	0.00010705427
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9828268e-05
2,731	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.0802025e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,770	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
2	3,936	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD
3	2,190	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD
4	9,806	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
5	6,180	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB
6	1,253	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
7	1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
8	1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB
9	4,491	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
10	11,586	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB