Expert · Module 24
Probabilistic structures
Trade a little accuracy for huge savings: Bloom filters, sketches, HyperLogLog and skip lists.
Probabilistic structures trade exactness for state that fits in a fixed budget: membership answers without storing keys, frequencies without storing events, cardinalities without storing users, and search without maintaining balance. This module builds all four — Bloom filters, count-min sketch, HyperLogLog, and skip lists — and measures what each one promises, what it costs, and the guarantees it cannot make.
- 1Bloom filtersPro — members onlyA Bloom filter answers membership questions from a few kilobytes of bits: absence is always certain, presence is probably right, and the false positive rate is a number you choose. It is how databases skip reads they do not need.13 min
- 2Count-min sketchPro — members onlyThe count-min sketch compresses a stream into a few rows of counters: an update is a couple of increments, a query reads the smallest counter, and the answer can overshoot by a bounded amount but never undershoot.13 min
- 3HyperLogLogPro — members onlyHyperLogLog counts distinct items in fixed memory: every hash updates one tiny register by taking a maximum, and the pattern of register values estimates the cardinality within about 1.04/sqrt(m). It never stores an item and merges by taking per-register maximums.14 min
- 4Skip listsPro — members onlyA skip list keeps keys in one sorted list and gives each node extra forward lanes picked by coin flips at insert time. Search starts on the top lane and drops a lane whenever it runs out of room, giving O(log n) expected time with no rotations; deleting unlinks the node and stops.14 min