Count–Min Sketch
Frequency estimates in fixed space, demoing the p/moul/x/daily/countminsketch library.
The workload
195 events over 123 distinct keys: three heavy hitters and a long tail of one-offs.
A generously sized sketch (1024 × 4)
| key | true | estimate |
|---|---|---|
alice |
40 | 40 |
bob |
25 | 25 |
carol |
10 | 10 |
user0 |
1 | 1 |
never-seen |
0 | 0 |
Exact here, and never-seen reads 0 — a zero estimate is definitive: that key was never added.
A deliberately tiny one (8 × 2)
Only 16 counters for 123 distinct keys, so collisions are guaranteed:
| key | true | estimate | error |
|---|---|---|---|
alice |
40 | 54 | +14 |
bob |
25 | 39 | +14 |
carol |
10 | 24 | +14 |
user0 |
1 | 16 | +15 |
Every error is positive. That is the guarantee: the sketch may overcount, never undercount, so an estimate is an upper bound — "at most this often", never "exactly this often".
Where the collisions are
Row 0 of the tiny sketch, and the column each key lands in:
| column | counter |
|---|---|
| 0 | 15 |
| 1 | 25 ← carol |
| 2 | 16 |
| 3 | 15 |
| 4 | 54 ← alice |
| 5 | 16 |
| 6 | 15 |
| 7 | 39 ← bob |
Taking the minimum across rows is what limits the damage: an overestimate needs a collision in every row at once.
Why bother
| exact map | sketch (1024 × 4) | |
|---|---|---|
| storage | one entry per distinct key, unbounded | 4096 counters, fixed |
| answer | exact | upper bound |
On chain the second row is the point: storage driven by user input is a liability, and a sketch sized once cannot be made to grow.
