Streaming, Sketching and Sufficient Statistics I

on YouTube ↗01h 24m

" summary

Sketching algorithms use low-independence hash functions and linear sketches to compress massive update streams into small summaries that support merge by addition. The lecture shows concrete estimators: the AMS sketch for F2 (uses 4‑wise hashing, per-row variance O(F2^2/W), W = Θ(1/ε^2), amplify with O(log 1/δ) repetitions) and the k‑minimum values algorithm for F0 (store T = Θ(1/ε^2) minima, O(1) update time, space Θ((1/ε^2) log M)). Practical refinements (HyperLogLog, Bloom variants) squeeze constants and extend to ranges and intersections.

AI-written summary · about

" chapters (41)

1. 0:00Introduction to streaming
2. 0:28Core ideas of streaming
3. 2:06Defining a data summary
4. 3:56Streaming computation workflow
5. 5:27Computer science approach
6. 7:13Resources and constraints
7. 9:24Pessimistic analysis
8. 11:02Concentration and randomness
9. 13:01Practical considerations
10. 14:15Streaming models
11. 16:00Outline of techniques
12. 17:12Advanced topics preview
13. 18:07Frequency distributions
14. 20:07Concentration bounds
15. 22:00Sketching techniques
16. 23:52Hash functions
17. 24:50Vector equality testing
18. 28:21Count-min sketch
19. 30:37Analyzing sketch accuracy
20. 33:27Collision handling
21. 35:36Finding heavy hitters
22. 37:26Compressed sensing
23. 40:08Chebyshev inequality
24. 41:43AMS sketch for F2
25. 42:51AMS sketch implementation
26. 45:29Median trick
27. 48:21Chernoff bound
28. 52:02Randomness optimization
29. 55:16Count sketch
30. 58:58F0 estimation
31. 1:00:14K-minimum values algorithm
32. 1:02:54F0 analysis
33. 1:05:43Estimator error bounds
34. 1:09:13Chebyshev application
35. 1:11:52Hyperloglog algorithm
36. 1:14:01Union and intersection
37. 1:15:31Bloom filters
38. 1:17:07Higher frequency moments
39. 1:18:41Composing sketches
40. 1:20:17Range efficient sketching
41. 1:21:57Conclusion

" related talks

• 55mTheory of Data StreamsS. Muthu Muthukrishnan · Symposium on Visions of the Theory of Computing 2013
• 01h 13mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 24mSketching Algorithms: Making Sense of Big Data in a Single StrokeTun Shwe · Conf42 Python 2024
• 01h 21mAn Overview on Data Streams AlgorithmsAndrew McGregor · Sublinear Algorithms Boot Camp 2024
• 01h 06mData Streams IMichael Kapralov · Foundations of Data Science Boot Camp 2018
• 01h 10mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 50mData sketching workshopWilliam Benton, Erik Erlandson · DevConf.CZ 2019
• 46mLearning-Augmented Sketches for Frequency EstimationPiotr Indyk · Sublinear Algorithms and Nearest-Neighbor Search