Data sketching workshop
summary
Workshop demonstrates practical sketches: Bloom filter for approximate set membership with mergeable bitmaps and a false‑positive curve that climbs toward 1 as capacity fills; count‑min sketch for frequency estimates that overestimate (many items reach 5–10× error unless table size increases) and pairs with a top‑K heap for trending counts; HyperLogLog for cardinality via leading‑zero hashes and harmonic averaging; t‑digest for quantiles/CDFs with inverse‑transform sampling to generate synthetic marginals. All examples include runnable Jupyter notebooks and simple Python implementations.
AI-written summary · about
chapters (8)
- 0:00Start
- 1:58Mean and variance
- 17:27Set membership
- 23:49BLOOM FILTERS
- 47:26Event frequencies
- 48:54PRECISE STRUCTURES
- 49:55GENERALIZING THE BLOOM FILTER: COUNT-MIN SKETCH
- 53:19TOP-K ELEMENTS
related talks
47mData Sketches — How to Eat an Elephant Whole (Even If It's Infinite)
24mSketching Algorithms: Making Sense of Big Data in a Single Stroke
01h 24mStreaming, Sketching and Sufficient Statistics I
46mLearning-Augmented Sketches for Frequency Estimation
42mMergeable Summaries and the Data Sketches Library
33mApache DataSketches
48mProbabilistic data structures
41mProbabilistic Data Structures