Theory of Data Streams
summary
Describes two concrete streaming primitives and what they actually achieve: Count-Min Sketch uses O(1/ε · log(1/δ)) counters, O(log(1/δ)) update time, and returns answers with one-sided error at most true value plus ε·(total volume), so space is independent of N and a few thousand counters suffice in practice to find heavy hitters; L0 sampling yields uniform picks from nonzero coordinates and powers a dynamic graph connectivity algorithm by collapsing components via sketch addition; also sketches give fast L2 estimates, compressed‑sensing style approximations, sparse DFT in ~K log N time, and practical implementations.
AI-written summary · about
chapters (13)
- 0:00Introduction to puzzles
- 2:42Median estimation in streams
- 6:11The count-min sketch
- 10:40Analyzing count-min sketch
- 14:23Lower bounds and linearity
- 20:40Heavy hitters and applications
- 26:23L0 sampling and graph sketches
- 30:09Dynamic graph connectivity
- 33:45L2 norm estimation
- 36:24Numerical linear algebra
- 40:03Fourier transforms and learning
- 43:50Privacy and cryptography
- 48:09Future directions and conclusion
related talks
01h 21mAn Overview on Data Streams Algorithms
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 26mStreaming, Sketching and Sufficient Statistics II
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
01h 13mSketching High-Dimensional Data
01h 04mNew Algorithms for Heavy Hitters in Data Streams
39mModel Counting Meets Distinct Estimation
01h 09mSketching High-Dimensional Data