Designing Parallel Data structures
summary
Provides a parallel k-d tree that builds λ levels together by sampling and sieves points into subtrees, cutting I/O to near-optimal and achieving polylog span and work/I/O bounds matching sorting. Implements partial rebuilds for batch updates (scapegoat-style) so insert/delete batches on million-point 3D workloads run orders of magnitude faster than rebuild-or-log-n alternatives, and billion-element construction outperforms prior baselines by about 4–10×; also shows leaving leaves unsorted gives up to ~8× speedup versus 1D-sorted p-tree variants.
AI-written summary · about
chapters (8)
- 0:00Parallel data structures intro
- 2:35Concurrent vs parallel
- 9:46Design goals
- 11:15k-d tree challenges
- 15:57Relaxed balancing for k-d tree
- 24:15pkd-tree results
- 31:38Summary and open questions
- 32:00Q&A
related talks
01h 05mThink Parallel
39mThe best multicore-parallelization refactoring you've never heard of
01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel Algorithms
49mStriving to Make Things Simple and Fast
01h 02m“Beyond the Issaquah Challenge: High-Performance Scalable Complex Updates"
56mParallelizing the C++ Standard Template Library
40mImmutable Data Structures in C++
21mEvery Data Structure Deserves Lock-Free Memory Reclamation