Back to blog

An Interactive Guide to Count-Min Sketch

4 min read
count-min-sketch
probabilistic data structure

Learn Count-Min Sketch: a probabilistic data structure for estimating item frequency in data streams, featuring an interactive guide and demo

An Interactive Guide to Count-Min Sketch

Introduction

A Count-Min Sketch is a probabilistic data structure that estimates the frequency of events or items in a massive data stream. While HyperLogLog estimates the total number of distinct items (cardinality), a Count-Min Sketch estimates how many times each specific item occurs (frequency). Even when you are processing an unbounded, massive stream of data where you cannot store every item, a Count-Min Sketch lets you track frequencies using fixed, sub-linear memory.

Working Principle

This blog is the third installment in my probabilistic data structures series. I have written similar interactive guides on Bloom Filter and HyperLogLog.

  • Structure of a Count-Min Sketch:

    • A 2D array of counters with d rows (depth) and w columns (width).

    • Each of the d rows has its own independent hash function (h1,h2,…,hdh_1, h_2, \dots, h_d).

  • Insert Operation (Adding an item):

    • For an item x, compute its hash value using all d hash functions.

    • For each row i, increment the corresponding counter at hash_i(x):

      Python
      count[i][hash_i(x)] += 1
  • Query Operation (Getting frequency estimate of x):

    • Hash x with the same d hash functions.

    • Fetch the counter values from each row at their respective hashed positions.

    • Return the minimum value among those d counters:

      Python
      estimate = min(count[0][h1(x)], count[1][h2(x)], ..., count[d-1][hd(x)])

Here is a small sketch you can work by hand. Its items are the digits 0 to 9, and each row's hash is simple enough to check in your head:

  1. Click a digit to add it to the stream. It's hashed once per row, and the counter it lands on in each row goes up by 1.
  2. Hover a digit to query it. Its cells light up, and the smallest of them (filled amber) is the estimate.
  3. Change the rows and columns. Everything you've added is replayed into the new shape, so you can compare.

Can you configure the parameters so the Count-Min Sketch always gets the estimate right? The badge above the last row turns green when all ten estimates are exact.

Try it · Count-Min Sketch
Rows (d), one hash each3
Columns (w)6
Add a digit to the stream · hover one to query it
h1 → 1
4
1
0
0
2
0
h2 → 1
0
1
4
0
2
0
h3 → 5
0
0
2
0
4
1
Estimate for 4: min(1, 1, 1) = 1. It was actually added 1 time, and at least one row kept it to itself, so the estimate is exact.
Every digit, actual vs. estimate
4 overestimated, none under
0
0 / 0
1
1 / 2
2
0 / 0
3
3 / 4
4
1 / 1
5
0 / 0
6
0 / 0
7
1 / 2
8
0 / 0
9
1 / 4
actual / estimate
Changing rows or columns replays everything you've added into a sketch of the new shape.

Key Insights

  • Why "Count-Min"? It counts frequencies and returns the minimum value across independent hash estimates. The "sketch" refers to a compact summary of a large dataset.

  • Sub-linear space complexity: It requires fixed memory proportional to d×wd \times w, regardless of how many billions of events stream in.

  • No underestimation: A Count-Min Sketch never underestimates the true frequency. Counters are only incremented, so hash collisions can only artificially inflate a counter, never decrease it. Taking the minimum across independent rows minimizes this collision noise.

  • Tuning d (Depth/Rows): Increasing d reduces the probability of high error because it provides more independent hash estimates, at the cost of slightly more hashing computation per item.

  • Tuning w (Width/Columns): Increasing w reduces the probability of hash collisions, leading to tighter error bounds at the cost of more memory.

Interactive Demo

Now for a real stream. This sketch counts 5,000 fruits drawn the way real traffic tends to arrive: a few items (apples, bananas) make up most of the stream and a long tail shows up rarely. Hit Start and watch:

  • The amber part of each bar is how far the sketch overestimates that fruit. It's never negative: the sketch never underestimates.

  • Rare fruits suffer most. A dozen extra counts are noise for apples and a big error for blueberries.

  • The worst overestimate stays under the bound εN (see below). Shrink the columns to 4 and it grows; widen them to 40 and errors nearly vanish.

Try it · Streaming fruit
Columns (w)10
Rows (d)3
Speed100/s
The stream will flow here…
Processed
0 / 5,000
Worst overestimate
+0
Error bound
≤ 0
εN, where ε = e / w
Underestimates
0
never, by design
The sketch · 3 × 10 = 30 counters
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Actual vs. estimated count
actual overestimate
🍎
0
🍌
0
🍊
0
🍇
0
🍓
0
🥭
0
🍉
0
🍍
0
🍑
0
🍒
0
🍋
0
🥝
0
🍐
0
🍈
0
🥥
0
🫐
0
Changing the sketch's shape starts the stream over. The bars are sorted by how often each fruit really appeared.

Mathematical Relationships

Error Bounds

  • The error in frequency estimation satisfies: Error≤ε⋅N\text{Error} \leq \varepsilon \cdot N with probability at least 1−δ1 - \delta.

  • Where:

    • ε\varepsilon = error factor (e.g., 0.0010.001 represents a 0.1%0.1\% error tolerance)

    • NN = total number of items processed in the stream

    • δ\delta = failure probability (e.g., 0.010.01 gives 99%99\% confidence)

Formula for Parameters

  • Width: w=⌈e/ε⌉w = \lceil e / \varepsilon \rceil (where e≈2.718e \approx 2.718)

  • Depth: d=⌈ln⁡(1/δ)⌉d = \lceil \ln(1 / \delta) \rceil

Use Cases

  1. Heavy Hitters / Top-K Elements: Identifying the most frequent items, trending hashtags, or most popular products in high-volume streams.

  2. DDoS and Anomaly Detection: Detecting IP addresses generating an abnormal volume of requests in network switches and firewalls.

  3. Search Engines: Tracking popular search terms and autocomplete suggestions in real-time without storing every individual query.

References