Search tools and guides ⌘K
IV · Probabilistic structures

Count-Min sketch

Approximate frequencies, in tiny memory.

2003 · Graham Cormode & S. Muthukrishnan
The story

Bloom filter's cousin for counting: how many times has key X been seen? Cormode and Muthukrishnan gave a small grid of counters — query the minimum across rows. Overestimates only; never undercounts. Tunable error ε with probability 1−δ in O((1/ε) log(1/δ)) space.

How it works

A 2D array, d × w. Each row uses a different hash function; each cell is a counter. Insert: for each row, hash the key, increment that cell. Query: take the minimum count across all rows.

Where it lives

Network anomaly detection (top talker IPs). Twitter's trending topics. Spark's frequency aggregations. Distributed top-K analytics.

The key insight

Count-Min sketch is used wherever exact counts are unaffordable. The "elephant flow" detection in carrier networks — finding heavy hitters out of billions of packets — runs on Count-Min.

More in Probabilistic structures
Bloom filter A set, in a thousandth of the space. HyperLogLog Count distinct, in 12 KB. MinHash Set similarity, in a few hashes. t-digest Quantiles, fairly accurate, fully streaming.
Across the cabinet
V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor. VI Adjacency list Each node, its neighbours. VI Disjoint Set / Union-Find Track connected components, in a forest. VI Merkle tree Hash of hashes; tamper-evident. VI LSM-tree Append-only, merged in the background. VI DAG · directed acyclic graph Order without cycles.
← All data structures