Count-min sketch

A count-min sketch estimates how many times each item has occurred in a stream, using a fixed amount of memory no matter how many distinct items there are. It never undercounts; it may overcount.

#How it works

The sketch is a table of d rows and w columns of counters, with one hash function per row.

• Add x: for each row, hash x to a column and increment that counter.
• Estimate x: for each row, read the counter x hashes to, and return the minimum.

Collisions only ever add counts from other items, so every row overestimates; taking the minimum keeps the error small. With width w ≈ e/ε and depth d ≈ ln(1/δ), the estimate exceeds the true count by at most ε × (total events) with probability 1 − δ.

w = 2,000, d = 5   → 10,000 counters (~40 KB with 32-bit counters)
error ≤ 0.14% of the total count, with probability ~99.3%

#Uses

• Heavy hitters and trending topics: combine the sketch with a small heap of the current top-k items to find the most frequent hashtags, URLs or search queries in a stream.
• Hot-key detection: spot keys receiving disproportionate traffic before they overload a partition (hot partitions).
• Rate limiting and abuse detection at very high cardinalities, where exact per-key counters would be too large.
• Cache admission: TinyLFU uses a frequency sketch to decide whether a new item deserves a place in the cache (eviction policies).

#Limits

• Estimates are only good for frequent items; rare items' counts are dominated by collision noise.
• You can't enumerate items from the sketch; keep a separate top-k structure.
• Counts only grow, so for "trending now", use time windows (one sketch per minute) or decay old counts.

See HyperLogLog for distinct counts and Bloom filters for membership.