Probabilistic data structures
summary
Covers concrete implementations and tradeoffs: bloom filter uses M ≈ 9.5 million bits (~1.2 MB) and k = 7 to store 1M keys with 1% false positives; deletions are impossible. counting Bloom filter replaces bits with counters (8×–32× memory increase depending on type) so deletes work but risk overflow. cuckoo filter stores fingerprints, computes alternate bucket via XOR of hash and fingerprint, supports deletion, and aborts insertion after a fixed max kicks. Count‑Min Sketch uses d×w counters and returns the row‑minimum for frequency estimates. HyperLogLog estimates distinct counts from leading‑zero statistics and a harmonic‑mean correction.
AI-written summary · about
chapters (23)
- 0:00Probabilistic data structures intro
- 1:28Membership problems and Bloom basics
- 4:00Bloom filter with hash functions
- 9:04Bloom filter performance and false positives
- 12:16Bloom filter in neural circuits and code
- 13:43Bloom filter limitations and deletion
- 14:47Counting Bloom filter for deletion
- 17:14Memory trade-offs in Counting Bloom
- 18:45Cuckoo hashing and Cuckoo filter intro
- 23:05Cuckoo filter lookup and insertion
- 24:30Cuckoo filter probabilistic aspect
- 27:24Cuckoo filter code and failure handling
- 28:08Frequency problems and Count-Min Sketch
- 30:16Count-Min Sketch practical example
- 33:25Count-Min Sketch probabilistic counting
- 34:28Cardinality problems and HyperLogLog
- 35:52HyperLogLog intuition with binary
- 37:21HyperLogLog array and hash distribution
- 40:10HyperLogLog insertion and leading zeros
- 41:14Calculating cardinality with HyperLogLog
- 43:22HyperLogLog efficiency and outliers
- 43:43Resources and further study
- 44:12Q&A and implementations
related talks
41mProbabilistic Data Structures
39mAcceptably Inaccurate: Probabilistic Data Structures #bbuzz
51mProbabilistic Data Structures with Redis Bloom
37mWhen Probably is Good Enough
53mUnderstanding Probabilistic Data Structures with 112,092 UFO Sightings
01h 50mData sketching workshop
47mUnderstanding Probabilistic Data Structures with 112,092 UFO Sightings
25mUse counters to count things