Competitive Data Structure Dynamization
summary
Problem: online dynamization for LSM-style stores where inserts (possibly with weights/timestamps) trigger building and merging static components, trading build cost (sum of weights) against query cost (number of components). Key claims: a weighted binary algorithm (a weight-based generalization of Bentley’s binary transform) obtains competitive ratio Theta(log n) and a matching lower bound; for k-component dynamization* deterministic algorithms are k-competitive and this is tight, with a primal–dual construction and recursive variants; randomized algorithms can slightly beat k (k − ε, ε tiny for k=2). Results apply to pure insertions and extend partially to lazy deletes/updates.
AI-written summary · about
chapters (8)
- 0:00Competitive data structure dynamization
- 1:26Online set-covering problem
- 7:22External memory data management
- 12:19Min-sum dynamization problem
- 17:19k-component dynamization constraint
- 19:02Main results and ratios
- 20:30Open problems in dynamization
- 28:30Closing questions
related talks
29mColor Coding-Related Techniques
01h 02mFine-Grained Counting Complexity I
27mAll-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
26mLower Bounds on the Running Time for Scheduling and Packing Problems
23mAn Algorithmic Bridge Between Hamming and Levenshtein Distances
20mA Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
38mLower Bounds on the Space Complexity of Dynamic Programming
01h 10mOn Algorithmic Game Theory II