Count-min Sketch to Infinity
summary
Implements Bloom Filter, Count‑Min Sketch, HyperLogLog and Heavy Keeper using Redis/RedisBloom/RediStack and .NET, and measures them against Postgres and naive Redis sets. Demo parses Moby Dick words: probabilistic structures insert in about 700 ms versus 3–5s for Postgres, use two orders of magnitude smaller memory (kilobytes vs megabytes), Count‑Min Sketch never undercounts but overcounts ≈2%, HyperLogLog undercounts ≈1%, deletes are unsupported; commands shown include BF.RESERVE, CMS.INCRBY, TOPK and PF (HyperLogLog) ops.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 2:08What is a probabilistic data structure
- 5:22History in Redis
- 8:52Set membership with Bloom filters
- 22:32Counting with Count-Min Sketch
- 32:29Cardinality with HyperLogLog
- 40:58Heavy hitters with Heavy Keeper
- 48:00Demo comparison
- 56:30Resources and closing
related talks
37mWhen Probably is Good Enough
51mProbabilistic Data Structures with Redis Bloom
10mDon’t forget to sketch! Running with large datasets
26mNo, Maybe and Close Enough! Probabilistic Data Structures with Python and Redis
25mHigh on Cardinality, Low on Memory
01h 00mHyper Speed: When Big Data Blooms
27mBehind the Keys: Redis Oyster Cult
28mBloom filters with redis