Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy

on YouTube ↗48m

" summary

Claims a locality-first strategy and builds Terrace, a hierarchical container that colocates low-degree neighbors in a shared PMA + standalone B-tree and uses a compressed packed memory array (CPMA) with Ligra-style vertex-scan primitives. Results show Terrace cuts query time vs Aspen (dynamic baseline) by about 2x on BFS/PageRank/CC and sometimes beats static Ligra; insertion throughput matches Aspen for most batch sizes. CPMA yields ~3–4× compression and fewer cache misses, improving both scan throughput and parallel scalability.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:34Problem: Developing Fast Graph Data Structures on Multicores
3. 2:29Optimizing Multicore Algorithms Requires Exploiting Parallelism and Locality
4. 4:23Dynamic Real-World Graphs Also Challenge Locality
5. 4:56Multicore Optimization Enables Fast Queries and Updates in Graph Data Structures
6. 9:53Dynamic Graph Data Structures and the Locality-First Strategy
7. 11:38Spatial Locality Determines Graph Query Performance
8. 13:16Choice of Graph Representation Determines Spatial Locality
9. 16:34Understanding Opportunities for Locality in Separate Per-Vertex Data Structure Design
10. 18:03Enhancing Spatial Locality by Collocating Neighbor Data Structures
11. 20:28Collocating Neighbor Data Structures Exploits Naturally-Occurring Skewness in Graphs
12. 21:23Insight: Further Optimizing for Locality with a Hierarchical Skew-Aware Design
13. 22:12Implementing the Hierarchical Skew-Aware Design with Cache-Optimized Data Structures
14. 22:40Selecting Data Structures for Dynamic Graphs asymptotically dominate Packed Memory Arrays
15. 26:07Terrace: Applying the Locality-First Strategy to Dynamic Graph Data Structures
16. 27:14Modern Dynamic Sets Support Batch Updates
17. 30:46CPMA: An Efficient Compressed Batch-Parallel Set Without Pointers
18. 34:34PMA Multi-Insert Relies on Batch Merge and Redistribute
19. 37:30Compression Improves Parallel Scalability Due to Memory Bandwidth Issues
20. 38:49Storing and Processing Dynamic Graphs With a Single CPMA