Count-Min Sketch: The "How Often?" Question

The Frequency Problem

You are running Twitter's trending algorithm and need to know the top 10 hashtags right now. You cannot keep an exact counter for every hashtag ever created — there are hundreds of millions of them, and the memory cost would be enormous. You need a way to estimate the frequency of any given item in a stream using bounded memory.

Count-Min Sketch (CMS) is a probabilistic structure that estimates the frequency of events in a data stream. It uses a fixed amount of memory regardless of how many distinct items appear in the stream.

How it Works

Think of CMS as a 2D grid of integer counters with d rows and w columns. You also have one independent hash function per row.

Adding an item: When hashtag "#cats" arrives:
- Hash "#cats" with the function for Row 0 to get column index c0. Increment grid[0][c0].
- Hash "#cats" with the function for Row 1 to get column index c1. Increment grid[1][c1].
- Repeat for all d rows.

Querying frequency: To estimate how many times "#cats" has appeared:
- Hash "#cats" for each row to find the column indices it incremented.
- Read the counter values at grid[0][c0], grid[1][c1], ..., grid[d-1][c_{d-1}].
- Return the minimum value across all rows.

Why the Minimum?

Different items will sometimes hash to the same column in the same row — a collision. When this happens, the counter for that cell is incremented by both items. This means any individual counter is always greater than or equal to the true frequency of the item — it can only be inflated, never deflated.

By taking the minimum across all rows, we pick the counter least affected by collisions. With enough rows (typically 5–10), the probability that all rows have a collision for the same item becomes very small, and the minimum is a tight upper bound on the true frequency.

Sizing a Count-Min Sketch

• Width w controls accuracy: a wider grid means fewer collisions. Setting w = ⌈e/ε⌉ (where e is Euler's number and ε is the desired error as a fraction of total stream size) gives the standard accuracy guarantee.
• Depth d controls confidence: more rows mean a lower probability of the estimate being wrong. Setting d = ⌈ln(1/δ)⌉ (where δ is the acceptable failure probability) is standard.

A typical configuration of w=2000, d=7 uses about 56,000 integer counters — roughly 224 KB for 32-bit counters — and can estimate frequencies across billions of events with error bounded at 0.1% of total stream volume with 99% confidence.