Count-Min 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 and consumes sub-linear space.
1. The Problem: Frequency Estimation
Imagine you are processing a stream of billions of packets passing through a router and you want to know:
- "How many times has IP address X appeared?"
- "What are the top 10 most frequent IP addresses?"
Storing a counter for every IP address (using a Hash Map) requires too much memory.
2. How it Works
The structure consists of a 2D array (matrix) with $d$ rows and $w$ columns, and $d$ independent hash functions.
Adding an Element (Increment)
To increment the count for an element $x$:
- Hash $x$ using each of the $d$ hash functions.
- Each hash function maps $x$ to a specific column index in its respective row.
- Increment the counter at that position in the matrix.
Querying Frequency (Point Query)
To estimate the frequency of $x$:
- Hash $x$ using the same $d$ hash functions to find the positions.
- Read the values at these positions.
- The estimated frequency is the minimum of these values.
3. Why Minimum?
Since multiple elements might hash to the same counter (collision), a counter's value is actually: $$ \text{True Count of } x + \text{Noise from collisions} $$
Because counts are always positive, the value in the sketch is always $\ge$ the true frequency. By taking the minimum of all the hashed positions, we get the value with the least amount of noise (closest to the truth).
- No False Negatives: It never underestimates the count.
- False Positives: It can overestimate the count.
4. Pros and Cons
- Pros:
- Space Efficient: Can count frequencies of distinct elements in massive streams using very little memory.
- Parallelizable: Updates can be done in parallel.
- Cons:
- Overestimation: Can report a higher frequency than reality.
- Not Reversible: You cannot retrieve the elements from the sketch, only query them.
5. Use Cases
- Heavy Hitters: Finding the most frequent items in a data stream (e.g., trending topics on Twitter).
- Network Traffic Analysis: Identifying IP addresses sending the most traffic.
- Natural Language Processing: Estimating word frequencies in huge corpora.
programming/bloom-filters programming/hyperloglog programming/hash-tables