Back to papers
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
- 13856
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.1905499e-05
- Overall Rank
- 10,592 | 26.39%
- DOI
-
10.14778/3734839.3734840
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
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 |
| 260 |
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling |
2013 |
SIGMOD |
0.00030020929 |
| 1,000 |
Effective Community Search for Large Attributed Graphs |
2016 |
VLDB |
0.00014714977 |
| 1,173 |
Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation |
2012 |
VLDB |
0.00013501079 |
| 1,653 |
An Experimental Study on Hub Labeling based Shortest Path Algorithms |
2018 |
VLDB |
0.0001098717 |
| 2,009 |
Efficient Network Aware Search in Collaborative Tagging Sites |
2008 |
VLDB |
9.8098536e-05 |
| 2,206 |
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks |
2018 |
SIGMOD |
9.2958349e-05 |
| 2,643 |
Scaling Distance Labeling on Small-World Networks |
2019 |
SIGMOD |
8.3894193e-05 |
| 4,194 |
Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks |
2022 |
SIGMOD |
6.3640644e-05 |
| 5,035 |
Scaling Up Distance Labeling on Graphs with Core-Periphery Properties |
2020 |
SIGMOD |
5.7414979e-05 |
| 5,255 |
Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks |
2020 |
SIGMOD |
5.5991117e-05 |
| 5,266 |
Incrementalizing Graph Algorithms |
2021 |
SIGMOD |
5.5949839e-05 |
| 5,274 |
A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery |
2022 |
SIGMOD |
5.5919087e-05 |
| 5,548 |
Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs |
2021 |
VLDB |
5.4445937e-05 |
| 5,606 |
Efficient Shortest Path Counting on Large Road Networks |
2022 |
VLDB |
5.4126223e-05 |
| 5,933 |
Hub Labeling for Shortest Path Counting |
2020 |
SIGMOD |
5.2620152e-05 |
| 6,595 |
Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks |
2023 |
SIGMOD |
4.9949537e-05 |
| 6,796 |
Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond |
2020 |
VLDB |
4.9195203e-05 |
| 7,439 |
BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale |
2022 |
SIGMOD |
4.7256836e-05 |
| 9,086 |
Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs |
2024 |
SIGMOD |
4.3947639e-05 |
| 10,477 |
Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs |
2025 |
SIGMOD |
4.1905499e-05 |
| 11,041 |
Distributed Shortest Distance Labeling on Large-Scale Graphs |
2024 |
VLDB |
4.1905499e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 5,035 |
Scaling Up Distance Labeling on Graphs with Core-Periphery Properties |
2020 |
SIGMOD |
5.7414979e-05 |
| 9,472 |
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks |
2025 |
SIGMOD |
4.3300131e-05 |
| 5,933 |
Hub Labeling for Shortest Path Counting |
2020 |
SIGMOD |
5.2620152e-05 |
| 10,878 |
A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks |
2025 |
VLDB |
4.1905499e-05 |
| 7,439 |
BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale |
2022 |
SIGMOD |
4.7256836e-05 |
| 2,206 |
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks |
2018 |
SIGMOD |
9.2958349e-05 |
| 7,430 |
DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs |
2022 |
VLDB |
4.7275494e-05 |
| 1,822 |
Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks |
2014 |
VLDB |
0.00010404349 |
| 2,643 |
Scaling Distance Labeling on Small-World Networks |
2019 |
SIGMOD |
8.3894193e-05 |
| 11,041 |
Distributed Shortest Distance Labeling on Large-Scale Graphs |
2024 |
VLDB |
4.1905499e-05 |