Parallel Batch-Dynamic Graph Algorithms

on YouTube ↗41m

" summary

A parallel batch-dynamic k‑core algorithm maintains 2+ε approximation coreness values with amortized O(B log^2 n) work per batch and polylogarithmic span, implemented as a Parallel Level Data Structure (PLDS) and a tuned PLDSOpt. Experiments on mixed insert/delete batches and real graphs (some with 1B+ edges) use 30–48 core machines, show PLDSOpt reaches about 33x parallel speedup (PLDS ~26x), gives 2–3 orders magnitude speedups vs the sequential baseline and up to 25x over an exact parallel algorithm, and the code is public.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:38Graphs are becoming very large
3. 1:19Parallelism and Dynamic Algorithms for High Performance
4. 2:36Our Parallel Batch-Dynamic Algorithms
5. 8:29Applications of k-core Decomposition
6. 9:19Work-Span Model
7. 11:54Sequential Level Data Structure (LDS)
8. 14:23Difficulties with Parallelization
9. 15:26Our Parallel Batch-Dynamic Level Data Structure (PLDS)
10. 19:20Coreness Estimate
11. 21:23Proof of Our Approximation Factor: Upper Bound
12. 25:08Implementation Details
13. 28:41Complexity Analysis
14. 30:40Experimental Setup
15. 31:26Runtimes/Accuracy vs. State-of-the-Art Algorithms
16. 36:11Scalability vs. # Hyper-threads
17. 37:11Runtime vs. Batch Size
18. 37:33Runtime vs. Static Algorithms
19. 38:44Conclusion