Count-Min Sketch

The probabilistic frequency tracker

Prerequisites

graph TD
  Bloom[Bloom Filters] --> CMS[Count-Min Sketch]
  Stream[Streaming / heavy hitters] --> CMS
  Hash[Hash functions] --> CMS

When to use

• High-volume event streams where you need approximate per-key counts (CDN requests, DDoS IPs, ad impressions) without storing every key.
• Top-K / heavy hitter pipelines that only need frequency estimates bounded by $ϵN$.
• Memory-bounded analytics when exact hash maps would blow the heap but a fixed-size matrix is acceptable.

When not to use

• You need exact counts or must detect a count of zero with certainty (use a hash map or a Bloom filter for membership).
• The stream is tiny or keys are few — a Counter is simpler and exact.
• You cannot tolerate one-sided error (CMS never underestimates; collisions only inflate estimates).

Lab

On the interactive Count-Min Sketch lab, scrub the Stream position slider to replay how the matrix fills, tune Error margin ε to resize width and depth, and query fruit keys to compare the CMS estimate against ground truth from the same stream prefix. Try the Collision hunt preset after predicting whether the sketch will overestimate or match.

Simple Fundamental Explanation

Imagine you manage a massive highway toll booth, and you want to know which car license plates pass through the most frequently.

You can’t afford to keep a giant database of every single license plate and its count—it would require too much memory and be too slow to update.

Instead, you set up a system of several small whiteboards. Every time a car passes, you have several different toll workers look at the license plate. Each worker uses their own secret rule (a hash function) to pick one square on their respective whiteboard, and they add a tally mark to that square.

Because the whiteboards are small, multiple different license plates will inevitably end up adding tally marks to the same square. This means the tally count in any given square might be artificially inflated by other cars.

When you want to know how many times “ABC-1234” passed through, you ask all the toll workers to check the square associated with “ABC-1234” on their whiteboards. They shout out their numbers: “10!”, “15!”, “12!”.

You know that the true count can never be lower than the actual number of times the car passed. Therefore, the lowest number shouted (the minimum) has the least amount of “noise” from other cars. You take the minimum count as your estimate.

This is the Count-Min Sketch. It tracks the frequency of events in a massive stream of data using very little memory. It overestimates sometimes, but it never underestimates.

---

Deep Dive: How It Works Under the Hood

A Count-Min Sketch is a 2D array (a matrix) of counters, with $d$ rows and $w$ columns. Every row has its own distinct hash function.

Updating the Frequency (Insertion)

When an item $x$ with a count of $c$ (usually 1) arrives in the data stream:

1. For each row $i$ (from 1 to $d$), calculate the hash: $j={\text{Hash}}_i(x)$.
2. The hash maps to a column index $j$ (between 1 and $w$).
3. Add $c$ to the cell at row $i$, column $j$: Matrix[i][j] += c.

Querying the Frequency

When you want to estimate the frequency of item $x$:

1. For each row $i$, calculate the same hash to find the column $j$: $j={\text{Hash}}_i(x)$.
2. Retrieve the count from every corresponding cell: Matrix[i][j].
3. Return the minimum of these retrieved values.

Visual Diagram

Initialization (d=3 rows, w=5 columns):
Row 1 (Hash 1): [ 0 | 0 | 0 | 0 | 0 ]
Row 2 (Hash 2): [ 0 | 0 | 0 | 0 | 0 ]
Row 3 (Hash 3): [ 0 | 0 | 0 | 0 | 0 ]

Update item "UserA" (+1):
Hash1("UserA") = 2, Hash2("UserA") = 4, Hash3("UserA") = 1
Row 1: [ 0 | 1 | 0 | 0 | 0 ]
Row 2: [ 0 | 0 | 0 | 1 | 0 ]
Row 3: [ 1 | 0 | 0 | 0 | 0 ]

Update item "UserB" (+1):
Hash1("UserB") = 2, Hash2("UserB") = 1, Hash3("UserB") = 5
Row 1: [ 0 | 2 | 0 | 0 | 0 ]  <-- Collision with UserA!
Row 2: [ 1 | 0 | 0 | 1 | 0 ]
Row 3: [ 1 | 0 | 0 | 0 | 1 ]

Query "UserA":
Hash1 -> Row 1, Col 2 = 2
Hash2 -> Row 2, Col 4 = 1
Hash3 -> Row 3, Col 1 = 1
Estimate = MIN(2, 1, 1) = 1. (Accurate, collision in Row 1 bypassed!)

---

Practical Example: Top-K and DDoS Detection

Content Delivery Networks (CDNs) process billions of requests per second. If an attacker launches a Distributed Denial of Service (DDoS) attack from a specific set of IPs, the CDN needs to identify the most frequent IP addresses instantly to block them.

Using a Count-Min Sketch, the CDN router adds +1 for every IP address it sees. To find the “Heavy Hitters” (the top $K$ IPs), the router maintains a small priority queue (a min-heap) alongside the sketch. Every time an IP is inserted, the sketch returns its estimated new count. If the count is higher than the lowest count currently in the Top-K heap, the IP is added to the heap.

This allows real-time DDoS mitigation in a streaming environment using only kilobytes of RAM.

---

The Mathematics: Equations and In-Depth Analysis

The Count-Min Sketch guarantees bounds on the estimation error. The estimated count ${\hat{f}}_x$ of item $x$ is related to its true count $f_x$ by:

$$f_x\le {\hat{f}}_x\le f_x+ϵN$$

Where:

• $N$ is the total sum of all counts inserted into the sketch.
• $ϵ$ is the acceptable error margin (e.g., 0.01 for 1% error).

This means the estimate is never less than the true value, and the overestimate is bounded by a fraction of the total traffic.

Configuring the Sketch Dimensions ($w$ and $d$)

The dimensions of the matrix are chosen based on two desired parameters:

• $ϵ$ (Error factor): The acceptable amount of overestimation.
• $\delta$ (Probability of failure): The probability that the estimate exceeds the error bound.

The parameters are calculated as:

$$w=\lceil \frac{e}{ϵ}\rceil$$ $$d=\lceil \ln (\frac{1}{\delta })\rceil$$

Where $e$ is Euler’s number ($\mathrm{2.718...}$).

Explanation of the Math

1. Width ($w$): The expected amount of “noise” added to a single cell in one row by other items is $N/w$. By setting $w=e/ϵ$, Markov’s inequality ensures the error in a single row is bounded with a specific probability.
2. Depth ($d$): Because hash functions are independent, the probability that all $d$ rows overestimate the value beyond the $ϵN$ bound decreases exponentially. Setting $d=\ln (1/\delta )$ ensures the probability of failure drops to the desired $\delta$.

If you want an error of $ϵ=0.001$ with a failure probability of $\delta =0.01$ (99% confidence): $w=e/0.001\approx 2718$ columns. $d=\ln (1/0.01)\approx 5$ rows. Total memory: $2718\times 5\times 4$ bytes (assuming 32-bit integers) $\approx 54$ KB.

Lab

Count-Min Sketch returns the minimum across hash rows — collisions can only inflate estimates, never deflate them. Same SHA-256 recipe as count_min_sketch.py.

Error margin ε1%

±1.0% of total stream mass

Stream position360 / 360

▶ Play⏮ Reset

Start of streamHeavy tailCollision hunt

Matrix sketch (3 rows × 272 columns) — showing 64 sampled columns

apple (100)banana (50)orange (10)grape (0)

Before revealing: for "apple" after 360 events, will the CMS estimate overestimate or match the ground truth?

Match ground truthOverestimate (due to collision noise)

Processed 360 events into a 3×272 matrix. Query "apple": estimate 105, actual 100.