Count-Min Sketch

Imagine a firehose of events rushing past: every URL clicked, every search typed, every packet on the network. You want one simple thing — how many times did each item appear? The honest answer is a giant table with one counter per distinct item, and at web scale that table simply does not fit in memory.

The Count-Min sketch, introduced by Graham Cormode and S. Muthukrishnan in 2005, gives up exactness to win on size. Instead of one counter per item, it keeps a small fixed grid of counters — a few kilobytes — and a handful of hash functions. Every item is hashed into one cell per row, and that cell is bumped by one.

To ask how often an item appeared, you look at the same cells and take the smallest of them. The magic property: the answer is never an underestimate. It may be a little too high when unrelated items collide into the same cells, but it can never be too low — a one-sided guarantee that turns out to be exactly what real systems need.

Below is a live Count-Min sketch with 4 rows and 8 columns — just 32 counters. Type an item and add it as many times as you like, or feed the random stream. Each item lights up one cell per row; querying takes the minimum of those cells.

<p class="hint">{{hint}}</p>
<div class="ctrl">
  <input id="item" type="text" value="apple" maxlength="14" />
  <button id="add" type="button">{{btn_add}}</button>
  <button id="add5" type="button">{{btn_add5}}</button>
  <button id="stream" type="button" class="ghost">{{btn_stream}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="grid" class="grid"></div>
<div class="query">
  <button id="q" type="button">{{btn_query_pre}}<span id="qname">apple</span>{{btn_query_post}}</button>
</div>
<div class="status" id="status">{{status_init}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ctrl { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; margin-bottom: .8rem; }
input { font: 600 14px ui-monospace, monospace; padding: .4rem .6rem; border: 1px solid #adb1b8;
        border-radius: 8px; width: 120px; }
.grid { display: grid; grid-template-columns: 64px repeat(8, 1fr); gap: 4px; margin: .4rem 0; max-width: 560px; }
.lbl { display: flex; align-items: center; font: 600 12px system-ui, sans-serif; color: #1d3557; }
.cell { aspect-ratio: 1; min-height: 34px; display: flex; align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; border-radius: 6px; background: #eef2f6;
        border: 1px solid #cdd9e3; color: #1d3557; transition: background .25s, color .25s; }
.cell.hot { background: #1d3557; color: #fff; border-color: #14233b; }
.cell.pick { outline: 3px solid #e9b949; outline-offset: -3px; }
.query { margin: .6rem 0; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status b { color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the two numbers when you query: the sketch's estimate and the true count it secretly tracks for comparison. The estimate is always $\ge$ the truth. Make the grid tiny or pour in many distinct items and collisions push the estimate above the truth — but never below it. Add more rows and the overestimate shrinks fast.

This is the same family of ideas behind Bloom filters and heavy hitters in streams: trade a sliver of accuracy for a colossal saving in memory.

The Count-Min sketch is not an open problem or an impossibility result — it is a solved, fully analyzed algorithm with clean guarantees, due to Cormode and Muthukrishnan (2005).

• Memory. You pick a width w and a depth d and store a $w \times d$ grid of counters. The size is completely independent of how long the stream is — a billion events fit in the same kilobytes as a thousand.
• Update and query cost. Adding an item touches one cell per row: $O(d)$ hash-and-increment operations. Querying takes the minimum over the same d cells: also $O(d)$. With d a small constant (often 4–8), both are effectively $O(1)$.
• One-sided error. The estimate is never below the true count. Collisions only ever add to a cell, so taking the minimum can only overshoot.
• Provable bound. Choosing $w \approx e/\varepsilon$ and $d \approx \ln(1/\delta)$, the overestimate is at most $\varepsilon \cdot N$ (where N is the total stream size) with probability at least $1 - \delta$. Want half the error? Double the width. Want it to fail ten times less often? Add a couple of rows.

That is the whole bargain, stated precisely: sublinear, often constant, memory; constant-time operations; and an error you dial in with two knobs. Unlike the intractable members of the P vs NP world, here the difficulty was understanding what to give up — exactness — and the math then makes the trade rigorous.

Anywhere a stream is too big to store but you still need per-item counts, the Count-Min sketch shows up:

• Network monitoring. Routers track which flows or IP addresses are sending the most traffic — spotting heavy hitters and possible DDoS sources — without a counter for every address on the internet.
• Trending and analytics. "Top search terms right now" or "most-viewed pages this minute" come straight from frequency sketches over a live event stream.
• Databases. Query planners estimate how many rows a value matches to choose a good plan; sketches give those frequency estimates cheaply over enormous tables.
• Natural language processing. Counting word and n-gram frequencies over web-scale corpora — the raw fuel for language models — fits in memory only with sketches.
• Rate limiting and security. Approximate per-user request counts catch abusers without a precise ledger for billions of users.

Combine it with Bloom filters for membership and you have the streaming toolkit: cheap answers to "have I seen this?" and "how often have I seen this?" over data you can never store in full.

The Count-Min sketch is a small idea with an outsized payoff: a fixed grid of counters, a few hash functions, and the discipline to take the minimum. In exchange for accepting that counts may run a touch high, you get a structure whose memory does not grow with the stream and whose error you set in advance with two dials.

It is a clean reminder that not every hard problem is about impossibility. Sometimes the win comes from asking a slightly humbler question — "approximately how often?" instead of "exactly how often?" — and discovering that the approximate answer is all the world ever needed. Keep exploring with heavy hitters in streams to see what these sketches make possible.