Count-Min Sketch

A d × w grid of counters that estimates how many times an item has appeared in a stream, using sub-linear memory relative to the number of distinct items.

How it works

The sketch is a grid with d rows and w columns. Each row has its own independent hash function mapping an item to one of the w columns. add(item) increments one cell per row: d increments total.

estimate(item) reads the same d cells and returns the minimum value across rows. Why the minimum? Hash collisions can only ever make a counter too high (by adding some other item's count into the same cell), never too low. So across d independent rows, the smallest observed value is the one least corrupted by collisions, giving an estimate that's always ≥ the true count, with bounded expected error.

Width w controls the error magnitude (ε ≈ e/w); depth d controls the confidence that the error bound holds (failure probability δ ≈ e-d). Add the same item many times below and compare the sketch's estimate to the true count tracked alongside it.

Interactive demo

Grid size4 × 16
Total increments0
Error bound (ε)±0.17 × N
Confidence98.2%
row 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
row 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
row 2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
row 3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new CountMinSketch(w, d)Allocate a d × w counter grid.O(w × d) space
add(item, amount?): voidIncrement one cell per row (d cells total).O(d) time
estimate(item): numberReturn the minimum across the d cells for item.O(d) time
widthForEpsilon(ε): numberWidth needed for error bound ε (ceil(e/ε)).O(1)
depthForDelta(δ): numberDepth needed for failure probability δ (ceil(ln(1/δ))).O(1)

References

Original papers

Library implementations

Real-world use cases