Count-Min Sketch Architecture in Depth

Why architecture matters here

A Count-Min Sketch answers one question - how many times have I seen this key? - in memory that does not depend on how many distinct keys exist. An exact counter is a hash map sized by distinct keys: 200 million source addresses at 50-60 bytes of key, count, and map overhead is 10-12 GB. A CMS for the same workload is a fixed rectangle of counters, kilobytes to a few megabytes, allocated once and never resized. The price is that it stores no keys - it can score a key you hand it, but cannot enumerate what it has seen. That also separates it from the membership family: Bloom and quotient filters answer seen at all in about a bit per element; CMS answers how often.

Two properties make it deployable. It never under-estimates, so "throttle when the count exceeds T" has no false negatives, though an innocent key colliding with a heavy one may cross a threshold it never earned. And it is linear: two sketches with the same geometry and seeds sum to exactly the sketch of the concatenated stream. What it cannot give you is the list of the heaviest keys - there is no key list to return - so for identity rather than lookup see Space-Saving and the top-k article.

The architecture: every step explained

The state is a matrix C of d rows by w columns of unsigned counters plus one hash function per row, mapping keys into [0, w). Nothing else is stored.

Update. To add c occurrences of key x: for every row i, compute j = h_i(x) and do C[i][j] += c. That is d hash evaluations, d increments, and - because rows are far apart in memory - d independent cache lines touched. No branching, no probing, no allocation.

Query. Read C[i][h_i(x)] for every row and return the minimum. That is right for an exact reason: each cell holds the true count of x plus the counts of every other key hashing to the same column, that extra mass is non-negative, so all d cells are upper bounds and the smallest is the tightest one available.

Why width and depth are different knobs. Widening rows spreads the same mass over more columns, shrinking expected noise per cell: width controls the magnitude of the error. Adding rows gives the key more chances to land somewhere quiet, and the estimate is bad only if every row is bad: depth controls the probability the bound is violated. Depth is cheap and width expensive, so it is tempting to buy accuracy with rows; it does not work.

The hash family. The analysis needs only pairwise independence, not cryptographic strength, so a fast non-cryptographic hash (MurmurHash3, xxHash) with a per-row seed suffices. Evaluating d full hashes per update is wasteful; the standard shortcut is the Kirsch-Mitzenmacher construction - one 64-bit hash split into halves a and b, with row i's column taken as (a + i * b) mod w. If a power-of-two w turns that modulo into a mask, finalize the hash first: masking exposes the low bits, the weakest bits of many hashes.

Where epsilon and delta come from

Let N be the total mass - the sum of every count ever inserted, not the number of distinct keys. The guarantee is that the estimate is never below the true count, and with probability at least 1 - δ exceeds it by at most εN. Both parameters are bought with geometry: w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉.

The derivation is three lines. Fix a row and a key x. The cell it lands in holds f(x) + X, where X is the summed count of every other key colliding with x in that row. Under a pairwise-independent hash each other key collides with probability 1/w, so E[X] = (N - f(x))/w ≤ N/w. Markov's inequality bounds the chance of the noise exceeding εN by (N/w)/(εN) = 1/(εw), and choosing w = e/ε makes that 1/e, about 0.368. Rows use independent hashes, so all d are bad simultaneously with probability (1/e)^d, and d = ln(1/δ) pushes that under δ.

The consequence that trips people up is that the error scales with total mass, not with the item's own count. In a stream of 10⁹ events at ε = 0.001, a key whose true count is 5 is bounded only to "between 5 and 1,000,005" - always upward, never below. It is accurate in relative terms only for keys carrying a meaningful fraction of the total. Two corollaries: since N only grows, a sketch that runs forever degrades forever; and δ is per query, so m queries cost a union-bound factor of m.

Sizing a sketch: concrete numbers

Because both formulas are closed-form, sizing is arithmetic rather than tuning. With 4-byte counters:

Read the shape before the values. Depth moves from 5 to 7 while the failure probability drops tenfold, because it is logarithmic; width moves by a factor of 1,000, because it is linear in 1/ε. Memory is governed by accuracy and barely at all by confidence, so a tuning session ending at d = 20 has misread which dial does what.

w = ceil(e / eps)          # columns  - controls error magnitude
d = ceil(ln(1 / delta))    # rows     - controls failure probability

def update(x, c):
    a, b = split64(hash64(x, seed))
    for i in range(d):
        C[i][(a + i * b) % w] += c

def estimate(x):
    a, b = split64(hash64(x, seed))
    return min(C[i][(a + i * b) % w] for i in range(d))

Counter width is a separate decision from geometry. A 32-bit counter saturates near 4.29 billion, and silent wraparound turns an over-estimate into an arbitrarily wrong number - use 64-bit or saturating adds. In the other direction, packet-rate and cache-admission workloads run 8-bit or 4-bit counters with periodic halving, trading range for a sketch that fits in cache.

Store the matrix as one flat array indexed i * w + j. Each update touches d effectively random locations, so that memory traffic, not the hash function, is the throughput ceiling - compute all d indices up front so they can be prefetched.

Conservative update and count-mean-min

Two well-known variants attack the over-estimation bias from opposite ends, and both give something up.

Conservative update

On an increment of one, first compute the current estimate m, then set each cell to max(cell, m + 1) instead of incrementing it. A query can return at most m + 1 afterwards anyway, so raising any cell above that adds noise that helps nobody and hurts every key sharing those cells. On skewed streams this cuts observed over-estimation substantially at identical memory. The costs: the update becomes a read-modify-write of d cells, and it is not linear in the input stream, so conservatively updated sketches cannot be merged and cannot support decrements.

Count-mean-min

Here you estimate the noise instead of hoping the minimum dodges it. Per row, take the cell value v, subtract (N - v)/(w - 1) - the average mass per other column - then report the median of the d residuals, clamped to never exceed the plain minimum. On skewed data this removes most of the systematic upward bias, but the corrected estimator can under-estimate, forfeiting the one-sided guarantee: if a decision is safe only because the count is never too low, keep the plain minimum. It also needs N at query time.

Merging, windows, and deletions

Because a plain CMS is a linear sketch, merging two is element-wise addition of their matrices, and the result is exactly the sketch the concatenated stream would have produced - same ε, same δ, with N the combined mass. Shards can therefore sketch independently and a combiner adds them. But the merge is valid only if both share w, d, and the same seeds in the same row order, and adding two integer matrices cannot detect a mismatch: a seed disagreement silently produces an arbitrarily wrong sketch rather than an error. Put w, d, seed, counter width, and N in the serialization header and reject mismatched merges explicitly.

Time is the other axis. Since the error grows with N, the fix for a permanently running sketch is to bound the mass, not the runtime. The clean approach is a ring of sketches, one per time bucket - say twelve buckets of five minutes - where updates hit the current bucket, a query sums the window (legal because the sketch is linear), and expiry zeroes the oldest. The cheaper alternative is decay: periodically halve every counter. Caffeine's W-TinyLFU frequency sketch does this, with 4-bit counters that saturate at 15 and a halving pass once total increments cross a threshold. Decay biases estimates downward, so the never-under-estimate property then holds only against the decayed stream.

Deletions are where the structure quietly stops working. Subtracting is mechanically possible, but the minimum is correct only because collision noise is non-negative; once negative updates exist a cell can sit below the true count and the estimate can under-shoot without bound. For a real turnstile stream, use a Count Sketch.

Operational failure modes

Saturation. Export the fill ratio - the fraction of non-zero counters per row. A sketch whose rows are essentially fully populated has become a mass-spreading device: every query on a rare key returns the ambient noise floor, and the numbers look plausible while carrying no signal at all. Fill ratio and N are the two values worth graphing: N passing the value you sized for is the moment εN stopped being the error you agreed to.

A single dominant key. One key carrying a large share of the mass inflates a cell in every row, and anything colliding with it in all d rows inherits an enormous over-estimate. The standard production shape is a hybrid: an exact map for a few hundred known-hot keys, with the sketch counting only the tail. That keeps the sketch's mass low, which shrinks εN for everyone else.

Adversarial collisions. With compile-time constant seeds, an attacker who chooses keys can search offline for ones colliding with a victim key in all d rows, then push traffic through them until the victim's estimate crosses your throttling threshold - a targeted denial of service that leaves no trace in exact counters. Seed the hash family from a per-process random value and keep the seed secret.

When to use it, and what to use instead

Reach for a Count-Min Sketch when the key space is unbounded, memory must be a fixed contract, you already know which key you want to ask about, and counts may need merging across shards or time buckets. Rate limiters, per-tenant quota screens, cache admission, and network flow monitoring sit in that envelope.

Reach elsewhere when the question differs. If the distinct keys fit comfortably in memory - a few million is ordinary - an exact hash map is simpler, always right, and needs no error analysis; approximation answers a memory constraint, not a default. If you need the identity of the busiest keys, see Space-Saving or the top-k article. Distinct counts are HyperLogLog's job; plain membership is a Bloom, quotient, cuckoo, or ribbon filter's. Against Count Sketch the choice is the error norm: Count-Min's error scales with the L1 norm and is one-sided, Count Sketch's with the much smaller L2 norm but in both directions.