Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs

Summary: M2HL: parallel maintenance of 2‑hop labels on dynamic small‑world graphs, handling edge insertions/deletions and concurrent update batches to eliminate prior time/memory bottlenecks. Provably correct and minimal; up to 10^4× faster, scalable and memory‑efficient. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14043
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,845 | 25.60%
DOI: 10.14778/3734839.3734840

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yuanyuan Zeng (Chinese University of Hong Kong)
2. Yixiang Fang (Chinese University of Hong Kong)
3. Kun Chen (Ant Financial)
4. Yangfan Li (Central South University)
5. Chenhao Ma (Chinese University of Hong Kong)

BibTeX Citation

@article{zeng_vldb25,
        title = {{Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs}},
        author = {Zeng, Yuanyuan and Fang, Yixiang and Chen, Kun and Li, Yangfan and Ma, Chenhao},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {7},
        pages = {2005--2017},
        doi = {10.14778/3734839.3734840},
        url = {https://doi.org/10.14778/3734839.3734840},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,498	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 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
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013028107
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
2,200	Efficient Network-Aware Search in Collaborative Tagging Sites	2008	VLDB	8.9664473e-05
3,612	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.2579119e-05
4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7229209e-05
4,443	Incrementalizing Graph Algorithms	2021	SIGMOD	6.7004839e-05
4,786	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.5083151e-05
4,903	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	6.4520708e-05
5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3883109e-05
5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.3165129e-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,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.824568e-05
7,158	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.6858492e-05
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05
10,748	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	5.093636e-05
11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD
2	9,619	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
3	5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD
4	11,097	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB
5	7,158	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD
6	1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
7	7,322	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
8	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
9	2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD
10	11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB