Count-Min Sketch — Part 1: Foundations & Core Concepts

maang.io System Design Series

---

What is this?

Picture the door of a wildly popular nightclub with three bouncers working side by side. The club wants to know, at the end of the night, roughly how many times each regular walked through the door — but nobody is going to keep a neat guest ledger with one line per person; there are millions of entries and no room for a book that big.

So each bouncer improvises the same trick. Every bouncer carries a rack of, say, 1,000 numbered tally-clickers. When a guest walks in, each bouncer glances at the guest's name and, using their own private quirky rule, picks one clicker from their rack and bumps it up by one. The three bouncers almost never pick the same numbered clicker for a given person — they each have a different rule — but each of them consistently picks the same clicker every time that same person appears.

Later you want to know: "How many times did Alice come in tonight?" You walk down the line and ask each bouncer for the number on Alice's clicker. Bouncer 1 says 47, Bouncer 2 says 31, Bouncer 3 says 52. Which do you believe? You believe the smallest one: 31. Here's the key insight — a clicker can only ever be too high, never too low, because other guests who happened to share Alice's clicker with that bouncer also bumped it. Nobody can ever make Alice's clicker go down. So the least-inflated answer — the minimum — is the closest to the truth.

That rack-of-clickers-per-bouncer is a Count-Min Sketch. It's a small, fixed-size grid of counters that estimates how many times each item appeared in a stream, using far less memory than counting exactly, and it is engineered so its answer is never an undercount.

The one-line idea: A Count-Min Sketch trades a little over-counting for enormous memory savings — it answers "how often did x occur?" over a massive stream using a tiny fixed grid of counters, and its estimate can be too high but is never too low.

We'll keep the three-bouncers-and-their-clickers picture running through all three chapters — it maps exactly onto the real structure, so hold onto it.

---

1. Why it exists — what was painful before

The obvious way to count occurrences is a hash map: Map<Item, Count>, +1 on each event. It's exact and simple, and for small key spaces it's the right answer. It falls apart on one specific shape of problem: counting frequencies over a huge, high-cardinality stream where you can't afford to store one entry per distinct key.

Concretely, imagine:

• Every URL clicked across a CDN — billions of events per hour, hundreds of millions of distinct URLs.
• Every source IP hitting an edge network, to spot the ones flooding you.
• Every search term typed into a site, to find what's trending right now.

An exact hash map here needs memory proportional to the number of distinct keys, plus the overhead of the map itself (pointers, hashing, resizing). Hundreds of millions of distinct 40-byte keys is gigabytes of RAM — per stream, per node — and it grows without bound as new keys appear. On a single machine ingesting a firehose, or inside a stream processor like Apache Flink or Apache Storm where thousands of these counters run in parallel, that's simply not affordable.

The painful realization is this: most of that memory is spent on keys you don't care about. You want the heavy hitters — the top URLs, the flooding IPs, the trending terms. You're happy to be approximate about the long tail of things that happened once or twice. Count-Min Sketch is the data structure that says: give up exactness, fix your memory budget up front regardless of how many distinct keys arrive, and accept a bounded, tunable over-count in return.

💡 This is the same bargain the Bloom Filter topic makes for membership ("have I seen x?") and that HyperLogLog makes for cardinality ("how many distinct things?"). Count-Min Sketch is the frequency member of that family — "how many times did I see x?" We'll line all three up in Section 5.

---

2. The mental model — a grid of counters

Strip the nightclub down to its structure. A Count-Min Sketch is a 2D array of counters with:

• d rows — one per hash function (the d bouncers). Each row has its own independent hash function.
• w columns — the counters in each row (the w clickers on each bouncer's rack).

So the whole thing is d × w integer counters and d hash functions, and that's the entire structure. Its size is fixed the moment you create it and never grows, no matter how many distinct items stream through.

Two operations, and both touch exactly d counters — one per row:

• Update / increment (x, c) — "item x occurred c more times." For each row i, compute h_i(x) to get a column, and add c to that one counter. (Usually c = 1 per event.)
• Estimate / query (x) — "roughly how many times did x occur?" For each row i, read the counter at h_i(x), then return the minimum across all d rows.

That's the whole API. Notice both operations are O(d) — constant, independent of stream length and of how many distinct items you've seen. d is small (typically 4–10), so this is blindingly fast and cache-friendly.

The two words in the name are literally the two halves of the query: you Count into the grid on update, and you take the Min on estimate. Count-Min.

2.1 Why the minimum, and why it never underestimates

This is the heart of the whole structure, so let's be precise about it. Consider any single counter. It holds the sum of the counts of every item that hashes to that cell in that row — the item you care about, plus any others that collided with it there. Collisions only ever add to a cell. Therefore:

Every counter for x is at least x's true count — it equals the true count plus whatever noise collided in. So each of the d readings is an over-estimate (or exactly right). The minimum of d over-estimates is the least contaminated reading, and it's still guaranteed ≥ the truth. The sketch can over-count but can never under-count — it's a one-sided error, exactly like a Bloom filter's "no false negatives."

That one-sidedness is what makes the structure trustworthy: when a Count-Min Sketch tells you an IP hit you at most 12 times, you can act on that upper bound. We'll put real error bounds on "how much over" in Part 2 — and they're tight and tunable.

---

3. How you actually use it

The API is tiny. Here's the shape in pseudocode (real libraries — Apache DataSketches, Redis's CMS.* commands via RedisBloom, Guava-style sketches — look just like this):

# Create a sketch sized for your accuracy target (the ε/δ math is in Part 2).
cms = CountMinSketch(width=2719, depth=5)   # 5 rows × 2719 cols

# --- Ingest a stream: one increment per event ---
for url in click_stream:
    cms.update(url, 1)          # +1 in each of the 5 rows

# --- Query any item's estimated frequency, anytime ---
cms.estimate("/pricing")        # e.g. returns 84_213  (≥ true count)

A couple of properties that matter in practice and that interviewers probe:

• Mergeable. Two sketches of the same dimensions and same hash functions merge by adding them cell-by-cell. So each node in a distributed system keeps its own local sketch, and you sum them to get a global one — no re-scanning the stream. This is why Count-Min Sketch is a natural fit for map-reduce and for per-partition stream operators. (Contrast with an exact hash map, where merging means unioning key sets and re-summing.)
• Increment by any amount. update(x, c) with c > 1 lets you fold in pre-aggregated batches, or even weight events. There's a conservative-update variant (Part 2) that only raises the smallest cells, cutting error further.
• Deletes need care. Plain Count-Min supports update(x, -1) only if you can guarantee counts never go negative and you never query mid-stream in a way that breaks the "never underestimates" guarantee — which is why plain CMS is used for strictly-increasing counts. There's a symmetric variant, the Count-Median Sketch (a.k.a. Count Sketch), that supports signed updates and takes a median instead of a min; reach for it when you need decrements.

That's genuinely it. The subtlety isn't in the API — it's in sizing the grid (w and d) for the accuracy you need, which is Part 2's job.

---

4. When to reach for it — and when not

Reach for a Count-Min Sketch when all of these are true:

• You need per-item frequency (or the top-K heavy hitters), not just membership or distinct-count.
• The stream is huge / unbounded and the key space is high-cardinality, so an exact map is too big.
• You can tolerate a bounded over-count — the answer is a decision input, not an audit-grade ledger. (Trending topics, rate/anomaly detection, cache admission, query-frequency stats.)
• You value fixed memory and fast, mergeable counters over exactness.

Do not reach for it when:

• You need exact counts (billing, financial ledgers, "did this coupon get used exactly once?") — use an exact store.
• The key space is small — a plain hash map is smaller, simpler, and exact. CMS only wins when the distinct-key count is large.
• You mostly care about rare items — CMS's error is proportional to the total stream volume, so low-frequency items can be swamped by noise. It shines for the heavy hitters, not the whisper-quiet tail.
• The question is really membership ("have I seen this?") → Bloom Filter, or cardinality ("how many distinct?") → HyperLogLog. Right family, wrong member.

Here's the family at a glance — the same probabilistic-sketch bargain, three different questions:

💡 Rule of thumb: if you'd otherwise build a Map<Key, int> counter and it's about to eat all your RAM because the key space is enormous, that's the Count-Min Sketch shape. If you'd build a Set<Key> for "seen it?", that's Bloom. If you'd build a Set<Key> just to call .size(), that's HyperLogLog.

---

5. Key takeaways

1. A Count-Min Sketch estimates how often each item appears in a stream using a fixed d × w grid of counters and d hash functions — memory is capped up front and never grows with the number of distinct keys.
2. Update adds to one counter per row (d cells); estimate reads one counter per row and returns the minimum. Both are O(d), independent of stream size.
3. Collisions only inflate counters, so every reading is ≥ the truth and the min is the least-inflated: the sketch over-counts but never under-counts — a one-sided error, like a Bloom filter's no-false-negatives.
4. It's mergeable (add cell-by-cell), making it ideal for distributed/streaming aggregation across nodes and windows.
5. Reach for it for heavy hitters and frequency over high-cardinality streams you can be approximate about; not for exact counts, small key spaces, rare-item accuracy, membership (Bloom Filter), or cardinality (HyperLogLog).

Next, Part 2 opens the grid up: the exact hash-and-increment write path, the min-query read path, the ε/δ error math that tells you how to size w and d, a fully worked numeric example, and the tuning knobs and failure modes a Staff engineer must know.