Count min sketch: Definition & Examples

A Count-Min Sketch is a compact counter table that estimates how often a key appears in a stream. Its streaming algorithm hashes each update into several rows and estimates a key’s count from the smallest counter the key touches. A market-data monitor can use it to estimate trade messages per symbol while keeping the same number of counters as new symbols appear. Cormode and Muthukrishnan, §§3–4.1

Follow one symbol through the rows

Start with

d

rows of

w

zeroed counters. Each row has its own fixed hash function. For every incoming trade, add one to the bucket chosen for its symbol in each row. To query a symbol, use those same hashes to read one counter per row and take the minimum. This stores

wd

counters and uses

d

hash evaluations per update or query. Cormode, “Data Structure Description” and “Point Queries”

In a fictional stream, symbols $x$ , $y$ and $z$ trade 4, 5 and 2 times. The table assigns their bucket numbers to make the collisions visible.

Symbol	Trades	Row 1 bucket	Row 2 bucket
$x$	4	0	1
$y$	5	0	3
$z$	2	2	1

Two rows of four trade counters. The highlighted cell in row 1 is 9 from 4 x trades and 5 y trades. In row 2 it is 6 from 4 x trades and 2 z trades. The estimate for x is 6 and the true count is 4.

Each row has a different collision. The minimum uses the row with two extra trades and overcounts x by two.

Every queried counter contains all four

x

trades. With nonnegative increments, any collision can only add to the true count. A single collision-free row would give the exact count. For signed updates, the same upper-bound argument applies when every key’s net count at query time is nonnegative. A negative net count for a colliding key can pull the estimate below the true count. Cormode, “Update Procedure” and “Point Queries”

What width and depth buy

Let $f(x)$ be the true count for $x$ and $N$ the total number of trade messages so far. For $0<\epsilon,\delta<1$ , take $w=\lceil e/\epsilon\rceil$ and $d=\lceil\ln(1/\delta)\rceil$ . Draw the row hashes independently from a family that gives any two distinct keys a collision probability of at most $1/w$ . For a fixed input stream and one fixed key at one fixed query time, the estimate satisfies

\mathbb{P}\bigl(f(x) \le \hat f(x) \le f(x) + \epsilon N\bigr) \ge 1-\delta.

The lower inequality holds for every choice of hashes in this nonnegative setting. The upper inequality is probabilistic over the hash draws. A wider row lowers the bound on the expected extra count, which is at most

(N-f(x))/w

in one row. That lets Markov’s inequality bound the chance of more than

\epsilon N

extra trades by

1/e

when

N>0

. Extra rows help because all

d

independent rows must exceed the error threshold for the minimum to exceed it. Cormode and Muthukrishnan, Theorem 1

The tolerance $\epsilon N$ grows with the entire stream. A rare symbol can therefore have a large percentage error even when the additive bound holds. The assigned hashes in the example show how the estimate is formed. The probability guarantee comes from the random hash construction.

For the collision bound behind that construction, see the universal hashing section of Hash Tables: Chaining, Open Addressing, and Universal Hashing (full lesson with membership).

Follow one symbol through the rows

What width and depth buy

Sources