A Count-Min SketchA probabilistic frequency table: a small grid of counters with one hash function per row. Adding an item bumps one cell per row; the estimate is the smallest of those cells, which can only ever overcount. answers "how many times have I seen this?" across a torrent of keys, in a grid that never grows. It never undercounts — it only overshoots a little, and rarely. Two knobs set the deal: width tightens the overshoot, depth makes the guarantee hold more often. One is dear, the other cheap.
A 2,719 × 5 grid of 4-byte counters estimates any key's count to within +10,000 (0.1% of 10M events), right 99% of the time — and stays 53.1 KiB however many distinct keys stream through.
Width is ⌈e/ε⌉, so memory scales with 1/ε: ten times tighter accuracy costs ten times the bytes. Accuracy is the expensive dimension — buy only as much as the answer needs.
| Confidence | Memory (at width 2,719) |
|---|---|
| 90%3 rows | 31.9 KiB |
| 99%5 rowsnow | 53.1 KiB |
| 99.9%7 rows | 74.3 KiB |
| 99.99%10 rows | 106 KiB |
| 99.999%12 rows | 127 KiB |
Depth is ⌈ln(1/δ)⌉ — each extra nine of confidence adds only ~2 rows, a near-flat memory cost. Confidence is the cheap dimension; buy plenty. (Each cell is a 4-byte counter — widen to 8 bytes if a single key can exceed ~4 billion.)
Want to set the grid directly instead? Read the error off a grid →