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: h23ee2e89e1d87ee2
Venue: VLDB
Year: 2025
Pagerank: 4.9605343e-05
Overall Rank: 11,315 | 24.16%
DOI: 10.14778/3734839.3734840
PDF: Download (CC BY-NC-ND 4.0)

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,757	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	4.9605343e-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
192	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025740385
696	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014671367
954	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00012856563
1,346	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00010949128
1,581	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010151896
2,201	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8626226e-05
2,242	Efficient Network-Aware Search in Collaborative Tagging Sites	2008	VLDB	8.7698066e-05
3,676	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0882436e-05
4,214	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7186746e-05
4,557	Incrementalizing Graph Algorithms	2021	SIGMOD	6.5264915e-05
4,631	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4784075e-05
4,944	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	6.3297928e-05
5,026	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.2965202e-05
5,357	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.1514562e-05
5,699	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0139119e-05
5,899	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD	5.9376618e-05
6,192	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8377174e-05
7,323	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.5392408e-05
8,416	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3208725e-05
10,290	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	5.031399e-05
11,634	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.9605343e-05

Semantically Similar Papers

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