Count-Min sketch

A frequency counter that keeps no keys. Ask it how many times it has seen something and the answer is never too low — sometimes too high, by an amount you set in advance.

Where this is actually used

Network hardware and ad platforms use these to find the traffic that matters while it is still flowing past. Keeping a counter per IP address at line rate is impossible; keeping a fixed grid of counters is not, and the few sources sending the most still stand out in it.

The guarantee

The estimate is never below the true count. Every row can only overshoot, so taking the minimum means all d rows must overshoot for the answer to be wrong — which is why depth buys confidence and width buys precision.

How it works

d rows × w columns of counters. Update adds to one cell per row. An estimate is the minimum across rows.

Cormode & Muthukrishnan, J. Algorithms 55(1), 2005

Start hereSet the stream to Zipfian — real data is skewed, and heavy hitters only exist there. Then read the heavy-hitter table: every estimate sits at or above the true count, and never below it.

Stream

Distributionhow often items repeat — real data is never uniformRank r appears with probability ∝ 1/rˢ. Real data is skewed, and heavy hitters only exist here.

Distinct itemshow many different items exist to draw fromStream lengthhow many items go through the structureSkew (s)Seedchanges the hash, and therefore which items happen to collide

The link carries the stream and every parameter. No server, no account — the state travels in the URL.

Parameters

ε — error factorhow far over the truth an estimate may sit, as a share of the whole streamw = ⌈e/ε⌉δ — failure probabilityhow often it is allowed to be wronger than thatd = ⌈ln(1/δ)⌉

w — width

2,719

counters per row — more columns, tighter estimates

d — depth

independent rows — more rows, less often loose