Count-Min versus Count Sketch

Two Tables, Two Different Error Stories

Suppose a service records events such as account increments, and must estimate any account frequency without storing every key. Hashing saves memory by letting keys share counters, but sharing creates collision noise. Count-Min Sketch (CMS) and Count Sketch use several independently hashed rows to control that noise. Their tables look similar; their error stories are different.

Think of estimating red marbles in shared boxes. CMS puts only positive quantities into a box. A box containing the red marbles reports the truth or too much, never too little, so the least contaminated box is useful. Count Sketch gives every key a reproducible plus or minus sign. Unrelated contributions can cancel, so a row may be high or low; the median rejects extreme rows.

Let \(f_a=5,f_b=2,f_c=1\). If a CMS row hashes \(a\) and \(b\) together, its estimate for \(a\) is \(7\). A second row isolating \(a\) gives \(5\), and the minimum is exact. In Count Sketch, suppose \(a\) has sign \(+1\) and colliding \(b\) has sign \(-1\). That row gives \(3\); another could give \(7\). Their errors are centered around \(5\), and the median across rows is the robust aggregator.

This deep dive builds on frequency estimation: a stream defines a frequency vector \(f\), and a sketch stores a compact summary. A cash-register stream has nonnegative increments. A strict turnstile stream allows deletions but keeps every current frequency nonnegative. A general turnstile stream permits signed frequencies. Standard CMS one-sided error needs nonnegative collision mass; Count Sketch naturally handles signed coordinates. Conservative update increments only CMS counters currently supporting the minimum and can improve empirical error, but it changes linearity and merge behavior. Signed hashing is Count Sketch's independent map \(s_r:U\to\{-1,+1\}\). An inner product \(\langle f,g\rangle=\sum_i f_i g_i\) connects signed sketches to similarity and second-moment methods.

Minimum Counters and Median Signed Rows

Let \(U\) be the key universe, \(f\) the final frequency vector, \(w\) the width, and \(d\) the depth. Row \(r\) has a bucket hash \(h_r:U\to\{0,\ldots,w-1\}\). CMS adds update \(\Delta\) to \(C_{r,h_r(i)}\). For a nonnegative vector, \[ C_{r,h_r(i)}=f_i+X_r,\qquad X_r=\sum_{j\ne i:h_r(j)=h_r(i)}f_j\ge0. \] Therefore \(\widehat f_i^{CMS}=\min_r C_{r,h_r(i)}\ge f_i\). With pairwise-independent uniform bucket hashes, \[ \mathbb E[X_r]\le\frac{\lVert f\rVert_1}{w}. \] Choose \(w=\lceil e/\varepsilon\rceil\). Markov's inequality gives \(\Pr[X_r\ge\varepsilon\lVert f\rVert_1]\le1/e\). Independent rows make the probability that all \(d\) rows fail at most \(e^{-d}\). With \(d=\lceil\ln(1/\delta)\rceil\), \[ f_i\le\widehat f_i^{CMS}\le f_i+\varepsilon\lVert f\rVert_1 \] with probability at least \(1-\delta\).

Count Sketch also has an unbiased sign hash \(s_r:U\to\{-1,+1\}\). It stores \(C_{r,h_r(i)}\leftarrow C_{r,h_r(i)}+s_r(i)\Delta\). The corrected row estimate is \[ Y_r=s_r(i)C_{r,h_r(i)} =f_i+\sum_{j\ne i:h_r(j)=h_r(i)}s_r(i)s_r(j)f_j. \] Suitable pairwise-independent signs make the collision terms mean zero, so \(\mathbb E[Y_r]=f_i\), and cross terms vanish: \[ \operatorname{Var}(Y_r)\le\frac{\lVert f_{-i}\rVert_2^2}{w}. \] For \(w=\lceil3/\varepsilon^2\rceil\), Chebyshev gives \(\Pr[|Y_r-f_i|\ge\varepsilon\lVert f_{-i}\rVert_2]\le1/3\). With an odd \(d=\Theta(\log(1/\delta))\) of independent rows, a Chernoff amplification shows that the median is accurate with probability at least \(1-\delta\). Exact depth constants depend on the selected tail bound and should be documented.

CMS uses positivity plus Markov and needs at least one good row. Count Sketch uses cancellation plus variance and needs a majority of good rows. Taking a minimum of signed estimates is a boundary-case error: more rows create more chances for a negative extreme. Using a median for ordinary CMS discards the standard “one clean row” argument and can retain unnecessary positive collision mass.

flowchart TD
    A[Frequency vector and point query] --> B{Collision mass nonnegative?}
    B -->|yes| C[CMS row is frequency plus noise]
    C --> D[Expected noise bounded by l1 over width]
    D --> E[Markov gives one good row]
    E --> F[Independent rows plus minimum]
    F --> G[One-sided epsilon l1 bound]
    B -->|no| H[Add independent random signs]
    H --> I[Count-Sketch row is unbiased]
    I --> J[Variance bounded by l2 squared over width]
    J --> K[Chebyshev gives good-row probability]
    K --> L[Independent rows plus median]
    L --> M[Two-sided epsilon l2 bound]
    B -->|ignored| N[Minimum may underestimate]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B navy;
    class C,D,E,F,G teal;
    class H,I,J,K,L,M purple;
    class N crimson;

One-Sided Bias versus Unbiased Noise

Let \(f_q=10\), with other frequencies \(6,3,1\). If \(q\) collides with the \(3\) and \(1\), one CMS row reports \(14\), an error of \(+4\). If Count-Sketch signs are \(s(q)=+1,s(3)=-1,s(1)=+1\), that row reports \(8\), an error of \(-2\). Fresh signs could report \(12\); over valid sign randomness, the errors cancel in expectation.

Count Sketch does not always dominate. For nonnegative traffic and a loose \(\ell_1\) budget, CMS uses width proportional to \(1/\varepsilon\), preserves a valuable upper-estimate invariant, and is simple. Count Sketch needs width proportional to \(1/\varepsilon^2\) for the basic point bound, but \(\ell_2\) may be far smaller than \(\ell_1\) for a heavy-tailed residual, and signed updates do not invalidate it.

Both guarantees are probabilistic. Weak hashes, adversarial knowledge of seeds, correlated rows, integer overflow, or inconsistent key encoding break their premises. Merge tables only when width, depth, hashes, seeds, counter type, and sign convention match. Standard tables are linear and merge by counterwise addition; conservative-update CMS is not generally linear, so separately built conservative sketches cannot be blindly added and treated as an equivalent stream sketch.

from hashlib import blake2b
from statistics import median

def u64(seed, row, domain, key):
    raw = f"{seed}|{row}|{domain}|{key}".encode()
    return int.from_bytes(blake2b(raw, digest_size=8, person=b"sketch-v1").digest(), "big")

class CountMin:
    def __init__(self, width, depth, seed=7):
        if width <= 0 or depth <= 0:
            raise ValueError("positive width and depth required")
        self.w, self.d, self.seed = width, depth, seed
        self.table = [[0] * width for _ in range(depth)]
    def bucket(self, r, key):
        return u64(self.seed, r, "bucket", key) % self.w
    def update(self, key, delta=1):
        for r in range(self.d):
            self.table[r][self.bucket(r, key)] += delta
    def query(self, key):
        return min(self.table[r][self.bucket(r, key)] for r in range(self.d))

class CountSketch:
    def __init__(self, width, depth, seed=7):
        if width <= 0 or depth <= 0 or depth % 2 == 0:
            raise ValueError("positive width and positive odd depth required")
        self.w, self.d, self.seed = width, depth, seed
        self.table = [[0] * width for _ in range(depth)]
    def bucket(self, r, key):
        return u64(self.seed, r, "bucket", key) % self.w
    def sign(self, r, key):
        return 1 if u64(self.seed, r, "sign", key) & 1 else -1
    def update(self, key, delta):
        for r in range(self.d):
            self.table[r][self.bucket(r, key)] += self.sign(r, key) * delta
    def query(self, key):
        values = [self.sign(r, key) * self.table[r][self.bucket(r, key)]
                  for r in range(self.d)]
        return median(values)

def build(cls, updates, width=257, depth=7):
    sketch, exact = cls(width, depth), {}
    for key, delta in updates:
        sketch.update(key, delta)
        exact[key] = exact.get(key, 0) + delta
    return sketch, exact

normal = [("hot", 1000)] + [(f"k{i}", i % 7 + 1) for i in range(500)]
cms, exact = build(CountMin, normal)
assert all(cms.query(k) >= v for k, v in exact.items())

assert CountMin(17, 3).query("absent") == 0
assert CountSketch(17, 3).query("absent") == 0

signed = [("a", 20), ("b", 9), ("a", -7), ("debt", -11), ("b", -4)]
cs, truth = build(CountSketch, signed)
assert all(abs(cs.query(k) - v) <= 4 for k, v in truth.items())

bad = CountMin(1, 3)
bad.update("target", 5)
bad.update("collider", 40)
assert bad.query("target") == 45

try:
    CountSketch(16, 4)
    raise AssertionError("even depth should be rejected")
except ValueError:
    pass

print("CMS:", cms.query("hot"), "exact:", exact["hot"])
print("signed:", {k: cs.query(k) for k in truth})
print("forced collision:", bad.query("target"))

Choosing for Heavy Tails and Signed Updates

For teaching positive word counts, CMS makes the direction of error visible: collisions only add, and a minimum chooses the least polluted row. Pair it with an exact dictionary so learners can label collision mass.

For professional telemetry with additions and retractions, Count Sketch is preferable if coordinates may become negative. Compatible regional tables add counterwise, representing the sum of streams. In a heavy tail, its residual \(\ell_2\) scale may remain useful even when total absolute traffic is enormous. The deployment must version width, depth, seeds, hash algorithm, sign convention, key encoding, and counter width.

CMS can be preferable when a network guardrail wants an upper estimate of nonnegative request counts and false positives are safer than false negatives. Exact follow-up can verify alerts. Conservative update may reduce false positives centrally, but should be rejected if arbitrary linear merging is required.

An attacker who learns fixed hashes can manufacture colliding keys. A theorem over random hashes does not protect against adaptive inputs after bucket mappings are exposed. Keyed hashing, seed rotation, rate limiting, exact follow-up, and collision telemetry belong at the trust boundary. Systematic normalized bias, excessive empirical failures, correlated rows, counter saturation, or header mismatch are evidence to reject or resize the design.

flowchart TD
    A[Define query and cost of error] --> B{Can a frequency be negative?}
    B -->|yes| C[Evaluate Count Sketch]
    B -->|no| D{Need one-sided upper estimate?}
    D -->|yes| E[Evaluate CMS]
    D -->|no| F[Compare l1 and l2 budgets]
    F --> C
    F --> E
    C --> G[Choose dimensions hashes and counters]
    E --> G
    G --> H[Validate on exact sampled windows]
    H --> I{Bias failures and memory acceptable?}
    I -->|no| J[Reject resize or change method]
    I -->|yes| K[Version contract and deploy]
    K --> L[Monitor drift correlation and saturation]
    L --> M{Assumptions hold?}
    M -->|yes| L
    M -->|no| J
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,D,F navy;
    class C,E,G purple;
    class H,K,L teal;
    class I,J,M crimson;

Cross-Check Count-Min and Count Sketch

Mastery means reconstructing each estimator from its collision decomposition. First define the three stream models, collision noise, signed hashing, and conservative update. Then manually update two rows for four keys and label every collision. Derive CMS expected noise and identify where nonnegativity and row independence enter. Expand Count-Sketch variance and justify why cross terms disappear. Finally compare many deterministic simulation seeds with an exact oracle.

For debugging, reuse the same hash in every row, use an unsigned Count-Sketch counter, force overflow, and merge different seeds. Name the broken invariant in each case. For comparison, construct flat and heavy-tailed vectors with equal \(\ell_1\) norm, compute their residual \(\ell_2\) norms, and compare useful error scales. For extension, prove counterwise merge linearity and investigate inner-product estimation; contrast this with conservative CMS.

Completion is measurable: formulas name their probability space; bounds state \(\varepsilon,\delta,w,d\); experiments have exact oracles; merges verify metadata; and production recommendations name evidence that would reverse them. This bridges frequency estimation to heavy hitters, second moments, inner products, and turnstile algorithms.