TL;DR: Count-Min Sketch lets you estimate how many times something occurred in a massive stream, using a fixed-size matrix (~54KB) instead of a hashmap that could reach terabytes, with a small error that's bounded with high probability.
The Problem
Imagine the following leetcode-style problem:
You have a stream of visitors to a website, each visitor can visit your website multiple times. The target is relatively simple: you need to know how many times a specific person visited your website.
Looks easy - we can use a hashmap and increment the entry for the user by each visit. Lookups would be O(1), which is good, and you'd need O(n) memory, where n is the number of unique users - which looks good as well.
Where it breaks
Now imagine you are tracking post visibility for a social media application. We can just store a hashmap for each post - now the space complexity would be O(n * m), where m is the number of posts.
Imagine there are 1 million users and 1 million posts, and we want to keep an exact counter for every user/post pair. Even ignoring the storage required for the keys and the overhead of the hashmap itself, we'd need:
1 × 10^6 × 1 × 10^6 × 4 bytes = 4 × 10^12 bytes
That's more than 3.5 terabytes of memory.
Conclusion: hashmap storage explodes when trying to count over a lot of data. That's where Count-Min Sketch comes in.
Count-Min Sketch
Count-Min Sketch utilizes a fixed 2D matrix that doesn't grow with input size, with width W and depth D. The width and depth can be chosen by setting:
w = ⌈e/ε⌉
d = ⌈ln 1/δ⌉
-
e= 2.718 (Euler's constant) -
δ= probability of failure -
ε= error rate
Disclaimer: Count-Min Sketch is a probabilistic data structure - it doesn't provide the accurate answer (this was my first time hearing about probabilistic data structures). If you found that interesting take a look onto Hyperloglog and bloom filters
It guarantees the following:
- The estimated frequency is never smaller than the true frequency.
- With probability at least
1 - δ, the estimate is at mostε × Nlarger than the true frequency, whereNis the total number of observations.
true count ≤ estimated count ≤ true count + ε * N(with probability ≥1 - δ)
Now that we have a depth × width matrix, we'll also have some hash functions (equal to depth).
For each input, we do the following:
for row in 0..d-1:
column = hash_i(element) % width
matrix[row][column] += 1
(Each row has its own independent hash function - hash_i refers to the hash function for row i.)
After some input entries, you might have the following matrix:
Looking up a frequency
If you want to get the frequency of element E1, you look at the hashed values:
| Hash function | Hashed value % width | Matrix entry | Value |
|---|---|---|---|
hashFunction1(E1) |
1 | matrix[0][1] |
3 |
hashFunction2(E1) |
6 | matrix[1][6] |
2 |
hashFunction3(E1) |
3 | matrix[2][3] |
2 |
hashFunction4(E1) |
1 | matrix[3][1] |
2 |
result = min(3, 2, 2, 2) = 2
To get the final frequency, you take the minimum of the values in the corresponding matrix entries: 2.
Why the minimum?
Every counter we look at contains the true count of E1 plus any counts added by other elements that happened to collide with it. Therefore, collisions can only make a counter larger, never smaller. Taking the minimum across the rows gives us the best estimate among the counters.
Why give up exact answers?
At first, giving up exact answers might sound like a bad idea. But imagine you're trying to find the top 100 most-viewed posts out of billions of events. You probably don't care whether a post was viewed 1,002,341 or 1,002,350 times - you care that you can identify the posts being viewed a lot, without storing a counter for every possible item.
That's where the tradeoff becomes useful: a tiny amount of error in exchange for much less memory.
Example calculation for high accuracy
For failure probability δ = 0.01 (confidence = 99%) and error rate ε = 0.001:
- width ≈ 2,718
- depth = 5
- total matrix size =
5 × 2718 × 4 bytes= 54,360 bytes (< 54 KB)
The time complexity for retrieval is O(depth), which is a constant - so basically O(1) as well.
Where is this used in the industry?
- Redis - Count-Min Sketch is implemented natively as part of Redis' core probabilistic data structures.
- Network analysis - tracking IP addresses to detect DDoS attacks.
- Heavy hitters - finding items that occur more than a threshold of the stream.
So, next time a counting problem mentions "billions of events," you know there's a structure for exactly that.
