# Count-min sketch

> Approximate per-key counts in fixed memory, for heavy hitters and trending topics.

Concept · Data structures for scale · https://levelcode.org/concepts/count-min-sketch

A count-min sketch estimates how many times each item has occurred in a stream, using a fixed amount of memory no matter how many distinct items there are. It never undercounts; it may overcount.

## How it works

The sketch is a table of **d** rows and **w** columns of counters, with one hash function per row.

- **Add x:** for each row, hash x to a column and increment that counter.
- **Estimate x:** for each row, read the counter x hashes to, and return the **minimum**.

Collisions only ever add counts from other items, so every row overestimates; taking the minimum keeps the error small. With width w ≈ e/ε and depth d ≈ ln(1/δ), the estimate exceeds the true count by at most ε × (total events) with probability 1 − δ.

```text
w = 2,000, d = 5   → 10,000 counters (~40 KB with 32-bit counters)
error ≤ 0.14% of the total count, with probability ~99.3%
```

## Uses

- **Heavy hitters and trending topics:** combine the sketch with a small heap of the current top-k items to find the most frequent hashtags, URLs or search queries in a stream.
- **Hot-key detection:** spot keys receiving disproportionate traffic before they overload a partition ([hot partitions](https://levelcode.org/concepts/hot-partitions)).
- **Rate limiting and abuse detection** at very high cardinalities, where exact per-key counters would be too large.
- **Cache admission:** TinyLFU uses a frequency sketch to decide whether a new item deserves a place in the cache ([eviction policies](https://levelcode.org/concepts/cache-eviction)).

## Limits

- Estimates are only good for **frequent** items; rare items' counts are dominated by collision noise.
- You can't enumerate items from the sketch; keep a separate top-k structure.
- Counts only grow, so for "trending now", use time windows (one sketch per minute) or decay old counts.

See [HyperLogLog](https://levelcode.org/concepts/hyperloglog) for distinct counts and [Bloom filters](https://levelcode.org/concepts/bloom-filters) for membership.