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

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
drows (depth) andwcolumns (width). -
Each of the
drows has its own independent hash function ().
-
-
Insert Operation (Adding an item):
-
For an item
x, compute its hash value using alldhash functions. -
For each row
i, increment the corresponding counter athash_i(x):Pythoncount[i][hash_i(x)] += 1
-
-
Query Operation (Getting frequency estimate of
x):-
Hash
xwith the samedhash functions. -
Fetch the counter values from each row at their respective hashed positions.
-
Return the minimum value among those
dcounters:Pythonestimate = 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:
- 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.
- Hover a digit to query it. Its cells light up, and the smallest of them (filled amber) is the estimate.
- 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.
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 , 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): Increasingdreduces 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): Increasingwreduces 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.
Mathematical Relationships
Error Bounds
-
The error in frequency estimation satisfies: with probability at least .
-
Where:
-
= error factor (e.g., represents a error tolerance)
-
= total number of items processed in the stream
-
= failure probability (e.g., gives confidence)
-
Formula for Parameters
-
Width: (where )
-
Depth:
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.