Parallel Batch-Dynamic Graph Representations

on YouTube ↗53m

" summary

Describes a concrete system called Apsen that extends Ligra and a compressed, block-based purely-functional representation called the CPAM framework; claims these store the WebDataCommons hyperlink graph (3.5B vertices, 128B edges) in about 700 GB (≈2× dynamic overhead) versus ~7 TB for naïve persistent trees and ~350 GB static, and give work-efficient batch updates with polylog depth. Implementation uses parlaylib, sustains ≈80k single-thread updates/sec with ~3% query-latency impact, and supports batch-dynamic primitives (Euler-tour trees) while integration with practical dynamic connectivity is ongoing.

AI-written summary · about

" chapters (15)

1. 0:00Start
2. 5:41Shared-memory graph systems are feasible Shared-Memory Machines
3. 7:39The Graph-Based Benchmark Suite (GBBS)
4. 18:50Static Setting: Summary
5. 26:37Streaming Graph Processing
6. 28:57What goes wrong when we just run updates and queries concurrently using in-place mutation?
7. 30:24Purely-functional trees enable snapshots via path-copying
8. 34:01Purely-Functional Trees are Safe for Concurrency
9. 35:51Challenges of using plain-old functional trees
10. 42:15Batch Update Performance vs. STINGER
11. 44:04Question 1: Space-Efficient Dynamic Graph Algorithms
12. 45:16Space-efficient HDT: integrate level information into the graph representation
13. 46:27Pick problems practitioners care about
14. 48:35Rent or buy a multicore server
15. 49:17Build implementations that can run on very large datasets