Data Sketches — How to Eat an Elephant Whole (Even If It's Infinite)
summary
Introduces data sketching techniques for scalable data processing and analysis, focusing on algorithms like HyperLogLog, Bloom filters, and count-min sketches to estimate counts, cardinalities, and frequencies with low memory and compute costs. Explains trade-offs, error bounds, and how to apply these probabilistic data structures to handle very large or streaming datasets where exact answers are impractical.
AI-written summary · about
chapters (9)
- 0:00Introduction to data sketches
- 3:37Probabilistic algorithms theory
- 8:40Counting unique elements
- 15:12G-LogLog algorithm evolution
- 19:19Theta sketch for set operations
- 23:13Element frequency
- 28:14Count Min Sketch and Misra-Gries
- 32:30Quantiles and histograms
- 36:48Summary and applications
related talks
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
01h 50mData sketching workshop
41mProbabilistic Data Structures
31mAnswering Multi-dimensional Queries on Massive Datasets
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 13mSketching High-Dimensional Data
55mTheory of Data Streams
33mApache DataSketches