# 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$:
1.  Hash $x$ using each of the $d$ hash functions.
2.  Each hash function maps $x$ to a specific column index in its respective row.
3.  Increment the counter at that position in the matrix.

### Querying Frequency (Point Query)
To estimate the frequency of $x$:
1.  Hash $x$ using the same $d$ hash functions to find the positions.
2.  Read the values at these positions.
3.  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]]