Acceptably Inaccurate: Probabilistic Data Structures #bbuzz
summary
Compares naive in-memory Java sets (≈264 MB heap for ~1M UUIDs) and multisets (≈234 MB) to compact probabilistic structures: Bloom filters via Guava give ~0.9 MB for a million entries with a default 3% false-positive rate (adjustable, more hashes raise cost); count‑min sketch via ClearSpring stores massive frequency counts in a few MB (example: 0.1% error, 0.99 confidence) instead of hundreds of MB; HyperLogLog estimates cardinality in kilobytes (authors quote ~5 KB) with ~3% error — used for caching, stream counts and unique‑visitor estimates.
AI-written summary · about
chapters (7)
- 0:00Introduction to probabilistic structures
- 3:14Why probabilistic data structures matter
- 8:48Bloom filters explained with Java demo
- 13:29Count Min sketch for frequency tracking
- 23:38Hyper Log Log for cardinality estimation
- 33:03Summary and use cases
- 33:47Q&A session
related talks
48mProbabilistic data structures
37mWhen Probably is Good Enough
53mUnderstanding Probabilistic Data Structures with 112,092 UFO Sightings
41mProbabilistic Data Structures
51mProbabilistic Data Structures with Redis Bloom
47mUnderstanding Probabilistic Data Structures with 112,092 UFO Sightings
40m"Gaining Constant time Lookup over Unorganized Data"
01h 50mData sketching workshop