DEV Community

zeyad daowd
zeyad daowd

Posted on AI-assisted

Count-Min Sketch

#datastructures #algorithms

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
Enter fullscreen mode Exit fullscreen mode

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/δ⌉
Enter fullscreen mode Exit fullscreen mode
  • 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:

  1. The estimated frequency is never smaller than the true frequency.
  2. With probability at least 1 - δ, the estimate is at most ε × N larger than the true frequency, where N is 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).

Empty CMS Matrix

For each input, we do the following:

for row in 0..d-1:
    column = hash_i(element) % width
    matrix[row][column] += 1
Enter fullscreen mode Exit fullscreen mode

(Each row has its own independent hash function - hash_i refers to the hash function for row i.)

First Element Insertion

After some input entries, you might have the following matrix:

CMS Lookup

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
Enter fullscreen mode Exit fullscreen mode

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?

  1. Redis - Count-Min Sketch is implemented natively as part of Redis' core probabilistic data structures.
  2. Network analysis - tracking IP addresses to detect DDoS attacks.
  3. 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.

References

Top comments (0)