Exact counting feels innocent right up to the moment the keyspace refuses to fit in memory.

Then a frequency table becomes a negotiation. Keep every key and pay the memory bill, or compress the stream and accept a contract weaker than exactness but stronger than a shrug.

The Count-Min Sketch is one of the cleanest contracts in streaming algorithms: for nonnegative updates, the estimate of a key is never below its true count, and with enough rows and columns the overcount is bounded with high probability.1

That sentence is dangerously easy to say too quickly.

The sketch is not a small dictionary. It does not remember which keys exist. It does not make collisions disappear. It keeps several hashed counter arrays and asks whether at least one row was lucky enough to avoid too much collision mass.

A frequency estimate becomes a receipt for shared buckets.

Counter Contract

Create a table with \(d\) rows and \(w\) columns. Each row has its own hash function. When item \(x\) appears with positive increment \(c\), add \(c\) to one bucket in every row:

\[C_{i,h_i(x)} \leftarrow C_{i,h_i(x)} + c.\]

To estimate the frequency of \(x\), read the \(d\) buckets touched by \(x\) and take the minimum:

\[\hat f(x) = \min_i C_{i,h_i(x)}.\]

Every bucket contains the true count of \(x\) plus counts from other keys that collided with \(x\) in that row. For positive streams, collision mass can only add. Therefore

\[\hat f(x) \ge f(x).\]

The minimum is the escape hatch. If one row had fewer harmful collisions than the others, the min chooses that row.

With width \(w=\lceil e/\epsilon\rceil\) and depth \(d=\lceil \ln(1/\delta)\rceil\), the classic Count-Min guarantee says the point-query estimate is at most \(f(x)+\epsilon \|f\|_1\) with probability at least \(1-\delta\), under the usual hash-independence assumptions.1

The table has \(wd\) counters.

That is the bargain:

memory buys a collision budget, not exact identities

Collision Bench

The lab below builds a deterministic Zipf-like stream, sketches it, and then queries every key so the errors are visible. Real systems often do not get to query every possible key. That is the point: Count-Min answers frequency queries for candidate keys; it does not by itself enumerate all candidates.

Exact count Classic Count-Min Conservative update Query / bound Collision heat

Deterministic insertion-only stream. The lab keeps exact counts for verification, but the sketches see only hashed updates. The epsilon*N line is the classic Count-Min point-query error scale using epsilon = e / width. Conservative update is shown as an engineering comparison; the displayed epsilon/delta contract is the standard Count-Min contract. The exported audit checks one-sided estimates, conservative-update dominance, heavy-key containment, table shape, memory accounting, and error-budget arithmetic.

The static-site audit runner checks the exported lab contract and the default collision ledger:

node - <<'NODE'
const lab = require("./assets/js/count-min-sketch-lab.js");
const EXPECTED_AUDIT = { cases: 12, failures: [], ok: 12 };
const EXPECTED_DEFAULT = "12:12:2560:1970:1061.829:500:5:1067:1145:1067:182:66:4:0:0:0";

function fixed3(value) {
  return Number(value).toFixed(3);
}

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

const audit = lab.runAudit();
const result = lab.evaluate({
  events: 50000,
  vocabulary: 2000,
  skew: 105,
  width: 128,
  depth: 5,
  threshold: 10,
  queryRank: 6,
  seed: 37
});
const defaultShape = [
  audit.cases,
  audit.ok,
  result.memoryBytes,
  result.observed,
  fixed3(result.budget),
  result.thresholdCount,
  result.query.item,
  result.query.count,
  result.query.cm,
  result.query.cu,
  result.cmSummary.p95,
  result.cuSummary.p95,
  result.threshold.cmFalsePositive,
  result.threshold.cuFalsePositive,
  result.threshold.cmFalseNegative,
  result.threshold.cuFalseNegative
].join(":");

if (!sameJson(audit, EXPECTED_AUDIT) || defaultShape !== EXPECTED_DEFAULT) {
  throw new Error(JSON.stringify({ audit, defaultShape }, null, 2));
}

console.log(`${audit.ok}/${audit.cases} Count-Min checks passed`);
NODE

The default stream has 50,000 events over a 2,000 key vocabulary with a moderate Zipf skew. The sixth-ranked key appears 1,067 times. The classic Count-Min estimate is 1,145; conservative update lands exactly on 1,067 for this seed. That does not mean conservative update is exact. It means the least-contaminated counters for this key were protected from some unnecessary increments.

The refreshed audit now runs 12 / 12 deterministic configurations over width, depth, query-rank, seed, skew, and vocabulary changes. It verifies that classic Count-Min and conservative update remain upper bounds on exact counts in the positive stream, that conservative update is never above the classic estimate for this implementation, that enumerated true heavy keys are not missed, and that memory and \(\epsilon N\) budget arithmetic match the displayed controls.

Raise Width. Buckets get less crowded, so the p95 overcount and false positive count usually fall. Lower it to 32 and the threshold panel becomes a small disaster: almost every tail key can be pushed over a 1% gate by collision mass.

Raise Depth. The estimate takes the minimum over more rows. More rows give a key more chances to find a clean bucket, but they also cost update work and memory. With depth 1, “minimum” means “the only row,” and the sketch is just a single shared hash table.

Move Zipf skew. A heavy head makes the true heavy hitters easier to spot, but a collision with a head key can poison a tail estimate. Uniform streams have less spectacular head collisions, yet many similarly sized keys compete near the threshold.

Lower Heavy threshold. You ask the sketch to distinguish smaller counts. Because estimates sit above truth, false positives are the natural failure mode when the candidate set is enumerated. The lab’s audit checks exactly this: classic Count-Min and conservative update do not miss enumerated true heavy keys in the positive stream, but they may accuse extra keys.

Counts Are Not Names

There are two related tasks that are easy to blur:

estimate the count of key x
find the keys whose counts are large

Count-Min is naturally a point-query sketch. If you know the key, it can give an upper-biased estimate for that key. But the sketch table contains counters, not key names. A large counter might be one large key, several medium keys, or many small keys colliding.

In the lab, we cheat by querying every synthetic key after the stream is built. Production systems need a candidate source: a sampled dictionary, a heap of observed keys, a separate heavy-hitter algorithm, a shard-local candidate list, or a known query set.

Misra and Gries gave an older deterministic streaming algorithm for finding frequent elements with a bounded number of counters.2 Space-Saving later became a practical counter-based method for frequent and top-\(k\) elements in streams.3 Those algorithms store candidate identities. Count-Min stores compressed evidence about counts.

That difference is not bookkeeping. It is the boundary between estimating a known account and discovering which accounts deserve attention.

If your question is “how many times did this account appear?”, Count-Min is a natural fit. If your question is “which accounts are the largest?”, Count-Min needs help remembering candidate names.

Anatomy of an Overcount

A Count-Min estimate can be written as

\[\hat f(x) = f(x) + \min_i \sum_{y \ne x: h_i(y)=h_i(x)} f(y).\]

The error is the smallest collision load across the rows.

Conservative update changes the write rule, not the query rule. Instead of incrementing every touched counter, it reads the current minimum for the key and increments only the counters that equal that minimum. Estan and Varghese used this idea in traffic-measurement filters as one of several practical optimizations for detecting large flows.4

The intuition is simple: if one row is already inflated, do not inflate it again merely because the key arrived. This can sharply reduce overcount in practice, as the lab shows. It is still a sketch, not a certificate of truth. Its behavior is more delicate to analyze than the classic Count-Min update, and the standard \(\epsilon,\delta\) line in the lab belongs to the classic construction.

That formula is more useful than the theorem when debugging a system. It tells you what to inspect:

  • Are there a few very heavy keys contaminating many buckets?
  • Are hash functions fixed and independent enough for the workload?
  • Did a deployment accidentally change hash seeds, making sketches impossible to merge?
  • Is the stream positive-only, or do deletions break the one-sided guarantee?
  • Are estimates being interpreted as exact counts downstream?

The original Count-Min paper emphasizes a wide range of uses: point queries, inner products, range queries, quantiles, and heavy hitters, all built around a small linear sketch.1 The 2008 empirical comparison by Cormode and Hadjieleftheriou is a useful antidote to treating any sketch as universally best: different frequency-estimation and heavy-hitter methods win in different accuracy, memory, update-speed, and query-speed regimes.5

The practical question is rarely “is the sketch elegant?” It is:

which error shape can this product tolerate?

One-sided overcount is excellent for conservative filters. It is awkward for billing. It is useful for candidate generation. It is dangerous when a thresholded estimate becomes an irreversible enforcement action.

When Deletions Walk In

The Count-Min story above assumes nonnegative updates: events arrive and counts increase.

If updates can be negative, the one-sided argument breaks. A bucket collision can subtract mass as well as add it. The minimum of rows no longer means “least overcount.” In turnstile settings with insertions and deletions, Count Sketch and related signed sketches are often the right starting point.6

This is not a minor implementation detail. It is a change in the error model.

Cash-register stream:

counts only go up
collision mass only inflates estimates

Turnstile stream:

counts can go up or down
collisions can cancel, inflate, or deflate

The same table shape does not imply the same promise.

Preflight for the Sketch

Before using Count-Min in a real service, I would want a ledger:

  • Is the stream positive-only?
  • What is the acceptable false-positive cost from overestimation?
  • What total mass \(\|f\|_1\) defines the error scale?
  • What \(w,d\) correspond to the desired \(\epsilon,\delta\)?
  • Are hash seeds fixed, versioned, and shared across shards for merging?
  • Is there a candidate-key source for heavy-hitter enumeration?
  • Are estimates used as upper bounds, approximate features, or final counts?
  • Are counters wide enough to avoid overflow?
  • Does the workload have adversarial keys or pathological hash interactions?
  • Are sketches reset, aged, windowed, or exponentially decayed?
  • How are confidence intervals communicated to downstream users?

The reset/windowing line is important. Count-Min is a memory-saving structure, not a forgetting policy. If you want recent frequency rather than all-time frequency, the time model has to be designed explicitly.

The Line I Would Remember

The Count-Min Sketch does not remove keys from memory for free.

It replaces exact identity-indexed counters with a few shared counter arrays. Every estimate is the true count plus collision mass. Width makes collisions smaller. Depth gives more chances for a clean row. The minimum is not magic; it is the least contaminated witness.

  1. Graham Cormode and S. Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and its Applications”, Journal of Algorithms, 55(1), 2005. ↩ ↩2 ↩3

  2. J. Misra and David Gries, “Finding Repeated Elements”, Science of Computer Programming, 2(2), 1982. ↩

  3. Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi, “Efficient Computation of Frequent and Top-k Elements in Data Streams”, ICDT 2005. ↩

  4. Cristian Estan and George Varghese, “New Directions in Traffic Measurement and Accounting: Focusing on the Elephants, Ignoring the Mice”, ACM Transactions on Computer Systems, 21(3), 2003. ↩

  5. Graham Cormode and Marios Hadjieleftheriou, “Finding Frequent Items in Data Streams”, PVLDB, 1(2), 2008. ↩

  6. Moses Charikar, Kevin Chen, and Martin Farach-Colton, “Finding Frequent Items in Data Streams”, ICALP 2002. ↩