Count-Min Frequency Sketch

The Count-Min Sketch is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses hash functions to map events to frequencies, but unlike a hash table, it uses sub-linear space at the cost of overcounting some events due to collisions.

Theory

The sketch consists of a two-dimensional array of counters with d rows (depth) and w columns (width). For each element in the stream, we compute d different hash functions. Each hash function determines a column index for a specific row. We increment the counter at that position in every row.

To query the frequency of an element, we again compute the d hash functions to find the corresponding counters. Because collisions can only increase the counters (assuming nonnegative updates), the true frequency is always less than or equal to each of these counters. Therefore, we take the minimum of the d counters as our best estimate. The estimate is guaranteed to never underestimate the true count.

Worked example

Let us manually process the "Skewed" stream "ABAACADAB" with width 3 and depth 2 to see the exact counts.

Initialize a 2x3 grid of zeros.
For each character, calculate the column index using the fixed pre-modulo hashes and modulo width 3.
For 'A' (ID 0), row 0 hash is 0 (0 mod 3 = 0), row 1 hash is 4 (4 mod 3 = 1). Increment grid[0][0] and grid[1][1].
For 'B' (ID 1), row 0 hash is 1 (1 mod 3 = 1), row 1 hash is 1 (1 mod 3 = 1). Increment grid[0][1] and grid[1][1].
After processing all 9 characters (5 'A', 2 'B', 1 'C', 1 'D'), the final counts are:
Row 1: [5, 2, 2] (hash mod 3: A=0, B=1, C=2, D=0)
Row 2: [0, 7, 2] (hash mod 3: A=1, B=1, C=0, D=0)
Query 'A': row 0 col 0 has 5 (which includes 5 A's and 1 D), row 1 col 1 has 7 (which includes 5 A's and 2 B's).
The minimum of (5, 7) is the estimated count: 5.

Experiment

Let's verify this using the interactive tool. First, select the "Skewed" stream.

Set the Stream control to "Skewed" which sets the text "ABAACADAB".
Set the Width control to 3.
Set the Depth control to 2.
Notice the resulting Sketch Data Structure row displays update in real-time.
Observe the queried row counts and estimated count are exactly what we calculated manually.

Limitations

The Count-Min Sketch only supports nonnegative weight updates out-of-the-box. If negative weights are introduced (e.g., removing elements), the minimum-count logic is no longer a guaranteed upper bound, and counters can underestimate the true frequency. Furthermore, highly skewed streams with many heavy hitters can cause substantial collisions for low-frequency items, leading to large overestimation errors unless the sketch width is sufficiently large.

References

Graham Cormode and S. Muthukrishnan. (2005). "An improved data stream summary: the count-min sketch and its applications."
https://www.cs.ox.ac.uk/people/graham.cormode/pubs/html/CormodeMuthukrishnan04CMJalg.html

Count-Min Frequency Sketch