What is a Count-Min Sketch and How Does It Estimate Frequencies?
Learn what a Count-Min Sketch is, how it estimates item frequencies in streams, and why its error is one-sided.
Expected Interview Answer
A Count-Min Sketch is a probabilistic data structure that estimates how many times each item has appeared in a stream using a small, fixed amount of memory, at the cost of occasionally overestimating (never underestimating) the true count.
It is implemented as a 2D array of counters with d rows, each paired with an independent hash function, and w columns. To record an occurrence of an item, it is hashed by each of the d hash functions and the counter at the resulting column in each row is incremented. To estimate an item’s count, the same d hash functions are computed and the minimum value across the d corresponding counters is returned, since taking the minimum cancels out most of the effect of hash collisions from other items landing in the same cell. Because different items can collide into the same counter, the estimate is always greater than or equal to the true count, never less — this one-sided error is what makes the structure usable for approximate top-K and frequency analysis at massive scale, as used in Twitter’s and Redis’s stream analytics.
- Uses sublinear memory regardless of how many distinct items pass through the stream
- Gives frequency estimates with a guaranteed one-sided error (only overestimates, never underestimates)
- Supports constant-time O(d) updates and queries independent of stream size
- Enables approximate heavy-hitter / top-K detection over unbounded streams in real time
AI Mentor Explanation
A Count-Min Sketch is like several independent scorers each keeping a compact tally grid of how often each shot type occurs, using shorthand codes that occasionally collide between two different shot types. To estimate how often a “cover drive” happened, you check each scorer’s tally at that shot’s code and take the smallest number reported, since a low count from any one scorer means less collision noise affected it. The estimate can only be too high, never too low, because a collision can only add extra counts, not remove real ones. That compact, minimum-of-many-estimates approach is exactly how a Count-Min Sketch tracks approximate frequencies.
Step-by-Step Explanation
Step 1
Allocate the 2D counter grid
Create a d-by-w array of counters initialized to zero, with d independent hash functions, one per row.
Step 2
Update on each occurrence
For each item seen in the stream, hash it with all d functions and increment the counter at each resulting (row, column) position.
Step 3
Query an item’s estimated count
Hash the item with the same d functions and read the counter at each resulting position across all rows.
Step 4
Take the minimum
Return the smallest of the d counter values as the frequency estimate, since it is least affected by hash collisions from other items.
What Interviewer Expects
- Explains the d-by-w counter grid and multiple hash functions accurately
- States that estimates are always greater than or equal to the true count (one-sided error)
- Explains why taking the minimum across rows reduces the impact of collisions
- Names a real use case: stream analytics, approximate top-K / heavy hitters, network traffic monitoring
Common Mistakes
- Confusing Count-Min Sketch with a Bloom filter (Bloom filters answer membership, not frequency)
- Claiming the estimate can be an undercount (it cannot, by construction)
- Forgetting that increasing width (w) and depth (d) reduces error but costs more memory
- Not mentioning that it is built for unbounded/streaming data where storing exact counts is infeasible
Best Answer (HR Friendly)
“A Count-Min Sketch is a compact structure that gives you an approximate answer to “how many times has this happened” without storing an exact counter for every possible item. It might occasionally tell you a count is a bit higher than reality, but it will never tell you it is lower, which makes it useful for tracking trends in huge, fast-moving streams of data cheaply.”
Code Example
import hashlib
class CountMinSketch:
def __init__(self, width=2000, depth=5):
self.width = width
self.depth = depth
self.table = [[0] * width for _ in range(depth)]
def _positions(self, item):
for row in range(self.depth):
h = hashlib.sha256(f"{row}:{item}".encode()).hexdigest()
yield row, int(h, 16) % self.width
def add(self, item, count=1):
for row, col in self._positions(item):
self.table[row][col] += count
def estimate(self, item):
# minimum across rows cancels most collision noise
return min(self.table[row][col] for row, col in self._positions(item))
cms = CountMinSketch()
for event in stream_of_page_views():
cms.add(event.page_id)
approx_views = cms.estimate("page_123") # always >= true countFollow-up Questions
- Why does taking the minimum across rows reduce the estimation error compared to using a single hash function?
- How does a Count-Min Sketch differ from a Bloom filter in what problem it solves?
- How would you use a Count-Min Sketch to build an approximate top-K "heavy hitters" list?
- How do width (w) and depth (d) affect the accuracy and confidence of the frequency estimate?
MCQ Practice
1. What kind of error can a Count-Min Sketch produce?
Hash collisions can only add extra counts to a cell, so estimates are always greater than or equal to the true frequency, never less.
2. Why does a Count-Min Sketch take the minimum across its d rows when estimating a count?
Each row can be inflated by unrelated items colliding into the same cell; the row least affected by collisions gives the tightest (smallest) estimate.
3. What is the main practical use case for a Count-Min Sketch?
Count-Min Sketch is designed to approximate frequency counts over large or unbounded streams using sublinear memory.
Flash Cards
What is a Count-Min Sketch? — A probabilistic structure that estimates item frequencies in a stream using a d-by-w counter grid and hashing.
Can the estimate be too low? — No — Count-Min Sketch estimates are always greater than or equal to the true count, never less.
Why take the minimum across rows? — Because it is the row least distorted by hash collisions from other items.
Count-Min Sketch vs Bloom filter? — Bloom filter answers “is it in the set”; Count-Min Sketch answers “approximately how many times has it occurred.”