Answer questions about more data than you can store.
A Bloom filter, a Count-Min sketch and a HyperLogLog each answer one question about a stream of data — without keeping the data. This site runs them beside the exact structures, so you can watch both answers at once and see exactly what the shortcut costs.
An exact set of a billion URLs is tens of gigabytes and lives on disk. A filter answering questions about the same billion URLs is a few hundred megabytes and lives in memory. That is the whole trade, and it is made on purpose.
One item → three slots, addressed by three hashes. One of them was already set by an earlier item — which is why a “yes” is only ever a hint, and a “no” is proof.
- Exact set — modelled
- 76.29 MiB
- Bloom filter — allocated
- 1.14 MiB
1,000,000 URLs at a 1% false-positive rate, 7 hashes. The filter figure is what the sizing formula allocates; the exact figure is lib/exact’s per-entry model, and is labelled modelled because a Set’s real footprint belongs to the engine.
Structures
or pick one belowIs this in the set?
A membership test that keeps no members. Ask it whether something is in the set and it answers either “definitely not” or “probably yes” — and it is only ever wrong in the second direction.
The guarantee
Never a false negative. False positives at a rate you choose.
Open →Count-Min sketchHow many times have I seen this?
A frequency counter that keeps no keys. Ask it how many times it has seen something and the answer is never too low — sometimes too high, by an amount you set in advance.
The guarantee
Never underestimates. Overestimates bounded by ε·N with probability 1−δ.
Open →HyperLogLogHow many distinct items?
A counter of distinct things that keeps none of them. It answers “how many different?” to within about a percent, using an amount of memory that does not grow with the answer.
The guarantee
Standard error ≈ 1.04/√m, with no items stored at all.
Open →Cuckoo filterIs this in the set — and can I remove it?
A membership test like a Bloom filter, with one thing added: you can take items back out. The no-false-negative guarantee gains conditions in exchange, and they are worth reading.
The guarantee
Deletion, which Bloom cannot offer. The no-false-negative guarantee gains conditions in exchange.
Open →The bargain
Every one of these structures makes the same bargain: hash into a fixed-size array, accept that collisions cause bounded damage, and stop storing the items at all.
Memory stops growing with the data. The price is an error rate — calculable in advance, and therefore a design parameter rather than a defect.
Asymmetry
Each guarantee is one-sided, and the direction matters. A Bloom filter’s “no” is proof; its “yes” is a hint. That asymmetry is why a database can use one to skip disk reads safely — a wrong “yes” costs a wasted read, a wrong “no” would lose data, and a wrong “no” cannot happen.
Tools
Compare & merge
Two of these structures, built separately, can be combined into one — and the result is exactly the structure you would have got by feeding both streams to a single machine.
Calculator
Working backwards. Say how many items you expect and how much error you can live with, and this gives you the structure to build and what it will cost in memory.