Sketching Algorithms: Making Sense of Big Data in a Single Stroke
summary
Sketching algorithms produce approximate answers orders of magnitude faster than exact queries by keeping a few kilobytes of state, processing each item in a single pass, and returning results with provable error bounds (examples used: 90% confidence, 1% relative error). Demonstrated sketches include Count-Min Sketch, HyperLogLog and reservoir sampling; shown tooling: Quix Streams/Cloud, Kafka, Debezium and the Python bindings of Apache DataSketches — mergeable sketches that enable real-time approximate uniques and top-K without heavy shuffling.
AI-written summary · about
chapters (27)
- 0:00intro
- 0:20preamble
- 0:30hello
- 1:12quix
- 1:52quix streams
- 2:06quix cloud
- 2:44what is a sketch?
- 3:20approximate answers
- 3:42sketch characteristics
- 4:24sketch components
- 5:37why exact == slow
- 6:17unique word count
- 7:19massively parallel processing (mpp)
- 7:31shuffling is slow
- 8:00latency numbers every programmer should know
- 8:28why sketches == fast
- 9:08sketch design
- 9:51sublinear data structure growth
- 10:21mergability
- 11:03unique counts are non-additive
- 11:29non-additive challenges solved
- 12:40types of sketches
- 13:57count min sketch
- 19:10open source sketches
- 19:24apache datasketches (java, c++, python)
- 22:26datasketch extensions
- 23:14thank you
related talks
47mData Sketches — How to Eat an Elephant Whole (Even If It's Infinite)
31mAnswering Multi-dimensional Queries on Massive Datasets
01h 50mData sketching workshop
01h 24mStreaming, Sketching and Sufficient Statistics I
33mApache DataSketches
01h 13mSketching High-Dimensional Data
55mTheory of Data Streams
25mSketching Volume Capacities in Deduplicated Storage