10-605 · Randomized algorithms

The countmin sketch

A countmin sketch keeps t real vectors r₁,…,r_t of length m, one per hash function h_i. Increment(x,v) adds v to r_i[h_i(x)] in every row; Retrieve(x) returns the minimum of those t cells. Collisions can only add to a cell, so the estimate is never too small — and it is wrong only if x collides in every row. Step through a stream of cartoon characters below, and click any name to Retrieve it.

width m

rows t

characters

speed

stream

randomness

Stream of `Increment(x, v)` calls

The sketch: rows r_i, columns 0…m−1

Press Step to process the first Increment.

Hover a cell to see which characters were added into it.

Pseudo-code

Initialize(ε, δ):  m = ⌈e/ε⌉;  t = ⌈ln(1/δ)⌉  r₁ = … = r_t = 0^mIncrement(x, v):  for i = 1, …, t:    r_i[h_i(x)] = r_i[h_i(x)] + vRetrieve(x):  return min(r₁[h₁(x)], …, r_t[h_t(x)])

True a[x] vs. Retrieve(x)

x	a[x]	Retrieve	error

Click a row to Retrieve it. Grey rows were never incremented (a[x] = 0); a nonzero Retrieve for them is a Bloom-filter-style false positive.

Parameters & bounds

Cormode–Muthukrishnan: with m = ⌈e/ε⌉ and t = ⌈ln 1/δ⌉, Retrieve(x) ≥ a[x] always, and Retrieve(x) ≤ a[x] + ε‖a‖₁ with probability ≥ 1 − δ.

Stream of Increment(x, v) calls

The sketch: rows ri, columns 0…m−1

Pseudo-code

True a[x] vs. Retrieve(x)

Parameters & bounds

Stream of `Increment(x, v)` calls

The sketch: rows r_i, columns 0…m−1