20.5 What is a count-min sketch?

At the door: The bouncer keeps three small tally boards, each with a few columns. For every person who walks in, they make a mark in one column on each board, picked from the person's name. Different people sometimes share a column, so every tally is at least the true count, sometimes more. To guess how often someone came, the bouncer reads their three columns and takes the smallest: the one least muddied by others.

In the system: A count-min sketch estimates how many times each item has appeared in a stream, in fixed memory:

• A grid of d rows × w columns of counters, with one hash function per row.
• Add an item: in each row, hash it to a column and add 1.
• Estimate an item: read its cell in every row and take the minimum.

Figure: other terms share cells, so every count is too high or exact; the smallest is the best guess.

Guarantees:

• Never undercounts. Collisions only add.
• Overcounts by at most ε × N (N = total items added) with probability at least 1 − δ, if you choose width w ≈ e ÷ ε and rows d ≈ ln(1 ÷ δ).

For the bookstore's search terms, ε = 0.1% and δ = 1% give 2,719 × 5 counters, about 13,600 numbers, however many distinct terms customers type. In the chapter's code, 100,000 searches over a skewed set of terms: no term is ever undercounted, and more than 99% are within 100 of the truth.

Where it's used:

• Search-term and hashtag counts for trending and autocomplete (Chapters 34 and 35).
• Heavy-hitter detection in networks: which IP is sending the most requests (useful for rate limiting, Chapter 25).
• Frequency estimates in databases and caches, for example deciding which keys are worth keeping in a cache.

It works best for frequent items, where an overcount of ε × N is small compared to the real count. For rare items, the error can swamp the answer.

Memory code: "Mark every board; trust the smallest tally."

---