Count-Min Sketch, in depth: the error proof, and the queries beyond point lookups: ranges, quantiles, heavy-hitter recovery and join sizes

The structure in one paragraph

A Count-Min Sketch is d rows of w counters, with one hash function per row mapping keys to columns. To add c occurrences of key x, add c to one counter in every row. To estimate x's count, read its counter in every row and take the minimum. Each counter holds x's true count plus the counts of every other key that collided with it, so every row over-estimates and the minimum is the least-polluted row. With w = ceil(e / epsilon) and d = ceil(ln(1 / delta)), the estimate exceeds the true count by more than epsilon times N, the total count, with probability at most delta. For epsilon = 0.001 and delta = 0.01 that is 2,719 columns by 5 rows, 13,595 counters or about 53 KiB at 4 bytes each, whatever the number of distinct keys.

Why the bound holds, in four steps

1. Fix a key x and one row. The counter x hashes to holds f(x) plus the sum of f(y) over every other key y that hashes to the same column. Call that extra mass X; it is never negative while counts are non-negative.
2. With a pairwise-independent hash family, any other key lands in x's column with probability 1/w. By linearity of expectation, E[X] is at most N/w, and with w = e/epsilon that is epsilon N / e.
3. Markov's inequality on the non-negative X gives P(X >= epsilon N) <= E[X] / (epsilon N) <= 1/e.
4. The d rows use independent hash functions, so the minimum is bad only if every row is bad: probability at most e^(-d), which is delta when d = ln(1/delta).

Two consequences shape everything that follows. First, the error is additive in N, not relative to f(x). Frequent keys are estimated well relative to their size, while for rare keys the noise can dwarf the true count. On skewed data the bound is pessimistic: most of N sits in a few heavy keys, which collide with any given key rarely, so realised errors are usually far below epsilon N. Second, step 1 needs counts that never go negative. Deletions are fine as long as no key's count drops below zero, the strict turnstile model. If true counts can go negative, as with differences between two streams, the minimum is no longer valid; use the median of the rows, or a Count Sketch with random signs.

Range sums with dyadic intervals

Suppose keys are integers in [0, U) with U = 2^b, such as latencies in microseconds or IPv4 addresses, and you want the total count for keys in [lo, hi]. Summing point queries across the range adds one error term per key, which is hopeless for wide ranges. The fix is a hierarchy. Keep b + 1 sketches; sketch j counts the prefix x >> j, so its keys are dyadic intervals of width 2^j. Any range is the disjoint union of at most two such intervals per level, so a range query costs at most 2b point queries, whatever the width.

The price is in the error. Each of up to 2b reads carries its own over-estimate, so the bound becomes 2b epsilon N. To hit a target range error epsilon' you must size each level at epsilon = epsilon' / (2b): wider by a factor of 2b, and there are b + 1 levels. In practice, two optimisations recover most of that. Upper levels have few nodes; once a level has no more nodes than the sketch has counters, store it as an exact array. And queries aligned to the hierarchy, such as a time bucket or a network prefix, are a single node and pay only the point error.

Quantiles by binary search

With range sums, the rank of x is range(0, x), and the phi-quantile is the smallest x whose rank reaches phi N. Ranks only grow with x, so a binary search over the key space finds it in b steps, each one range query. Because range estimates only over-count, the returned key may sit slightly below the true quantile, with rank error bounded by the range error.

Be honest about the comparison. If all you need is quantiles over an insert-only stream, purpose-built summaries such as KLL or t-digest give better accuracy per byte. The dyadic Count-Min earns its place when you need several query types from one structure, or deletions under strict turnstile, which many quantile summaries do not support.

Recovering heavy hitters without a candidate list

A plain Count-Min can say how often a key occurred but cannot list keys; it stores none. The usual fix pairs it with a heap of candidates, as in Space-Saving style designs. The dyadic hierarchy gives another way, which also works with deletions. A key with count at least phi N has every ancestor prefix with count at least phi N. So start at the root and descend: at each level, expand only children whose estimate reaches phi N.

The one-sided error makes this safe. Estimates never undercount, so no true heavy hitter or heavy prefix is ever pruned. The search finds every heavy key, plus occasional false positives whose estimates were inflated, which you can filter with a final point query or an exact recount. Work is bounded too: at most 1/phi prefixes per level can be truly heavy, so each level evaluates at most twice that many children plus false positives. The same descent, stopped early, reports heavy prefixes such as busy subnets, which is the hierarchical heavy-hitters problem.

Inner products and join sizes

Two streams summarised with identical sketches, same w, same d and same hash functions, can be combined. For each row, multiply the two rows elementwise and sum; take the minimum over rows. The result estimates the inner product of the two frequency vectors, the sum over keys of f(x) times g(x). That is exactly the size of an equi-join on the key, which is why query optimisers and streaming engines care about it. Every collision adds non-negative products, so the estimate never undercounts, and the error is at most epsilon times N_f times N_g with probability 1 - delta.

That bound is loose for selective joins, the case optimisers care about most, and self-join size is better estimated with signed sketches such as AMS or Count Sketch, whose error scales with L2 norms. Use the Count-Min inner product when you already keep the sketches and want a cheap upper-biased estimate.

Reference implementation

The code below implements all four queries. It derives the d columns from one BLAKE2b digest by double hashing, a cheap standard substitute for d independent hashes, and seeds each level separately. On 200,000 Pareto-distributed 16-bit keys, with width 679 and depth 5 per level, the range [10, 1000], the median, the 99th percentile and the eight heavy hitters at phi = 1% all came out exact, and two 50,000-item sketches estimated their join size within 0.0001%. Skewed inputs are the friendly case, so test on your own distribution.

import hashlib

class CountMin:
    def __init__(self, width, depth, seed=0):
        self.w, self.d = width, depth
        self.rows = [[0] * width for _ in range(depth)]
        self.seed = seed
        self.n = 0

    def _cols(self, key):
        h = hashlib.blake2b(f"{self.seed}:{key}".encode(), digest_size=16).digest()
        a, b = int.from_bytes(h[:8], "little"), int.from_bytes(h[8:], "little") | 1
        return [(a + i * b) % self.w for i in range(self.d)]   # double hashing: d columns from one digest

    def add(self, key, c=1):              # strict turnstile: true counts must never go negative
        for row, col in zip(self.rows, self._cols(key)):
            row[col] += c
        self.n += c

    def query(self, key):                 # never below the true count
        return min(row[col] for row, col in zip(self.rows, self._cols(key)))

    def inner(self, other):               # needs identical width, depth and seed
        return min(sum(x * y for x, y in zip(r1, r2)) for r1, r2 in zip(self.rows, other.rows))


class DyadicCMS:
    """One Count-Min per level of a binary tree over integer keys in [0, 2**bits)."""
    def __init__(self, bits, width, depth):
        self.bits = bits
        self.levels = [CountMin(width, depth, seed=j) for j in range(bits + 1)]

    def add(self, x, c=1):
        for j, cms in enumerate(self.levels):
            cms.add(x >> j, c)            # level j counts the prefix x >> j

    def range(self, lo, hi):              # inclusive bounds
        total, j = 0, 0
        while lo <= hi:
            if lo & 1:
                total += self.levels[j].query(lo); lo += 1
            if not hi & 1:
                total += self.levels[j].query(hi); hi -= 1
            lo, hi, j = lo >> 1, hi >> 1, j + 1
        return total

    def quantile(self, phi):              # smallest x whose prefix count reaches phi * n
        target, lo, hi = phi * self.levels[0].n, 0, (1 << self.bits) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.range(0, mid) >= target:
                hi = mid
            else:
                lo = mid + 1
        return lo

    def heavy_hitters(self, phi):         # walk down, expanding only heavy prefixes
        threshold, frontier = phi * self.levels[0].n, [0]
        for j in range(self.bits, 0, -1):
            frontier = [child for p in frontier for child in (2 * p, 2 * p + 1)
                        if self.levels[j - 1].query(child) >= threshold]
        return frontier

Worked example: per-source traffic on a 100M-packet window

A network team wants per-source-IP packet counts for each one-minute window of about 100 million packets, to answer three questions: how much traffic came from a given address, how much from a given /16 subnet, and which addresses or subnets sent more than 1% of packets. Keys are IPv4 addresses, so b = 32 and there are 33 levels.

Size each level at epsilon = 0.001 and delta = 0.01: 2,719 by 5, 13,595 counters. Levels 19 through 32 have at most 8,192 nodes each, fewer than the counters, so they are stored exactly; together they hold 16,383 counters, about 65 KB. Levels 0 through 18 are sketches, 19 times 13,595 counters at 4 bytes, about 1.03 MB. The whole window is about 1.1 MB, and an update is 19 sketch updates plus 14 array increments.

Now the answers. A single address is one level-0 query, at most 100,000 packets too high (0.1% of N) with probability 0.99. A /16 subnet is a single node at level 16, so it has the same point error. That is the aligned-query optimisation at work: an arbitrary address range could need up to 64 node reads, of which at most 38 hit sketched levels, for a worst-case bound of 3.8 million packets. Heavy hitters at phi = 1% (one million packets) descend 32 levels with at most 100 truly heavy prefixes per level plus a few false positives. An hourly view is the counter-wise sum of sixty same-seed sketches, and its absolute error bound grows sixty-fold with N.

Failure modes

Trade-offs

The Count-Min family wins when you need mergeable, fixed-size summaries that support several query types and strict-turnstile deletions, with errors that only over-count. It loses to specialised structures on any single job: Space-Saving for top-k lists, KLL or t-digest for quantiles, HyperLogLog for distinct counts, and Count Sketch for second-moment and signed-update work. The dyadic extension multiplies memory and update cost by the number of levels, which is cheap for 32-bit keys and expensive for 64-bit ones.

What to do next

1. Write down the queries you need: point, range, quantile, heavy hitters or join size. If it is only one, consider the specialised structure first.
2. For point queries, size w and d from epsilon and delta, and check that epsilon N sits well below the smallest count you will report.
3. For ranges, map keys to integers of b bits, budget 2b reads per range, and store upper levels exactly once they fit.
4. Align common queries to dyadic boundaries, such as time buckets or network prefixes, so they cost one read.
5. Confirm that counts never go negative; if they can, switch to a median or Count Sketch estimator.
6. Run the reference code on a sample of your real stream and compare every query type against exact counts before trusting the bounds.