What Does Dynamic Optimality Mean in External Memory?
summary
Defines external-memory dynamic optimality for update-heavy workloads, builds a new Jello tree and proves it is statically optimal and competitive against any buffer-propagated tree whose restructuring budget is limited to B^{ε} speed, i.e., spends at most a 1/k fraction of cost on shape changes. Uses buffer propagation (nodes with fanout F, edge buffers of size B/F) to show updates amortize by B/F (e.g., F = √B gives √B faster updates), and shows Jello succeeds under the speed-limited adversary.
AI-written summary · about
chapters (12)
- 0:00Intro
- 2:35COULD THERE BE A SINGLE "BEST" TREE? A binary search tree is dynamically optimal against the class
- 5:38THE EXTERNAL-MEMORY MODEL
- 7:12THE CLASSIC DATA STRUCTURE: B-TREES
- 9:25DYNAMIC OPTIMALITY FOR MERGE-SPLIT TREES
- 10:55ROTATION-BASED B-TREES
- 12:16B-TREES ARE SUB-OPTIMAL FOR INSERTIONS/DELETIONS/UPDATES
- 13:14BUFFER-PROPAGATED TREES WITH FANOUT B
- 16:59IDEA: ADAPTIVE BUFFER-PROPAGATED TREES
- 20:52OUR SECOND RESULT: A CONTINUUM BETWEEN STATIC AND DYNAMIC OPTIMALITY
- 23:15TWO WAYS TO THINK ABOUT SPEED LIMITATION
- 25:33OPEN QUESTIONS
related talks
01h 07mEmerging Embdedded Memories and Storage
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
16mJohnny Cache: the End of DRAM Cache Conflicts (in Tiered Main Memory Systems)
16mControlling Memory Footprint of Stateful Streaming Graph Processing
06mEarly experience of Utilizing Persistent Memory for Database... (Work-in-Progress Report)
52mChanging shared_buffers on the fly
15mImproving Performance of Flash Based Key-Value Stores Using Storage Class Memory...
20mSymbiosis: The Art of Application and Kernel Cache Cooperation