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 ( $h_1, h_2, \dots, h_d$ ).
Here, we hash an incoming item (e.g., 2) from the stream using each row's hash function to find which column in each row needs to be incremented.
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)])
```

I have created an interactive app that lets you visualize how a Count-Min Sketch operates:

Adjust the number of rows and columns.
Click to generate a random number. The number is hashed d times, finding the cell in each row that gets incremented by 1.
Querying follows a similar process: we hash the item, inspect all d matching cells, and take their minimum value to obtain the frequency estimate.

Can you configure the parameters so the Count-Min Sketch always gets the estimate right?

Cms Working

Open tool

Loading interactive demo...

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 \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

I have created an interactive demo that puts all the pieces together. In this demo, the sketch estimates the frequency of fruits in a stream of 5,000 items. Hit Start to watch the stream of fruits process in real-time, and observe how the sketch never underestimates the true count.

Count Min Sketch

Open tool

Loading interactive demo...

Mathematical Relationships

Error Bounds

The error in frequency estimation satisfies: $\text{Error} \leq \varepsilon \cdot N$ with probability at least $1 - \delta$ .
Where:
- $\varepsilon$ = error factor (e.g., $0.001$ represents a $0.1\%$ error tolerance)
- $N$ = total number of items processed in the stream
- $\delta$ = failure probability (e.g., $0.01$ gives $99\%$ confidence)

Formula for Parameters

Width: $w = \lceil e / \varepsilon \rceil$ (where $e \approx 2.718$ )
Depth: $d = \lceil \ln(1 / \delta) \rceil$

Use Cases

Heavy Hitters / Top-K Elements: Identifying the most frequent items, trending hashtags, or most popular products in high-volume streams.
DDoS and Anomaly Detection: Detecting IP addresses generating an abnormal volume of requests in network switches and firewalls.
Search Engines: Tracking popular search terms and autocomplete suggestions in real-time without storing every individual query.