Count-Min Sketch

Count-Min Sketch (CMS) estimates item frequencies in a stream using a d by w counter array.

For update (x, delta), add delta to C[j, h_j(x)] in every row. A point query returns:

estimate(x) = min over rows j of C[j, h_j(x)]

Classical one-sided guarantee

For the nonnegative cash-register model, choose:

w = ceil(e / epsilon)
d = ceil(ln(1 / delta))

Then estimate(x) is never below f(x), and with probability at least 1 - delta:

estimate(x) <= f(x) + epsilon * L1_mass

The error is additive in total stream mass, not a relative percentage of the queried item's count. The probability is over the hash choice under the paper's assumptions.

Merge contract

CMS is linear: compatible sketches over disjoint stream partitions can be merged by adding corresponding counters. Compatibility requires identical width, depth, ordered hash functions and seeds, counter width/signedness, update model, namespace, and epoch/window.

Merge retries are not idempotent. Adding the same partial sketch twice double-counts it, so use unique partition/epoch identities or exactly-once aggregation at the merge boundary.

Model boundaries

This lesson uses nonnegative increments. Turnstile streams with negative updates need a precisely selected variant and guarantee; blindly taking a minimum can lose the one-sided property. Counter wraparound or saturation also invalidates the theorem. Size counters for worst-case mass and surface overflow as a hard error.

Conservative update can improve empirical accuracy for positive streams but changes update behavior and merge properties; do not mix it with plain CMS without a proved contract.

Decision use

CMS is useful for candidates and telemetry, not sole authority for money, authorization, or irreversible rate-limit denial. Near a threshold, verify against exact or sampled state and include the uncertainty policy.

Diagram scenarios

The animation covers updates, min-of-rows queries, the exact epsilon/delta bound, compatible merge with replay risk, and fail-closed unsupported states.

Related concept

Interactive scenarios