Count-Min Sketch

The Count-Min sketch (CMS) is a probabilistic frequency-estimation data structure that summarizes a stream of items in sublinear space while answering point queries — “how many times did we see item x?” — with bounded one-sided error. It uses d hash functions and a d × w matrix of integer counters; on each update(x), it increments one counter per row, and on query(x) it returns the minimum of the d selected counters. The estimate never underestimates the true count, and overestimates by at most ε‖a‖₁ with probability at least 1 − δ, where ‖a‖₁ is the L₁ norm of the frequency vector (the total number of non-negative insertions, N), w = ⌈e/ε⌉, and d = ⌈ln(1/δ)⌉ (Cormode & Muthukrishnan 2005, Theorem 1). Introduced by Graham Cormode and S. Muthukrishnan in 2005, CMS underpins heavy-hitter detection in network monitoring, frequency tracking in Bloom-filter-style admission policies (W-TinyLFU in Caffeine), and is exposed as a first-class data type in Redis Stack (CMS.*), Apache DataSketches, and Spark’s approximate aggregations.

1. Intuition — A Stack of Lossy Tally Cards

You’re a librarian counting how many times each book in a collection of millions has been borrowed. You don’t have room for a million-row tally book — you have room for, say, four small cards each with 1,000 boxes.

For each card, you pick a different “scribbling rule” (a hash function) that maps a book title to one of the 1,000 boxes. When a book is borrowed, you find the right box on each of the four cards and add a tally mark.

When you want to know how many times “Moby Dick” has been borrowed: you look up Moby Dick’s box on each card and report the smallest count among the four.

Why the minimum? Because each box accumulates not just Moby Dick’s tallies but also the tallies of every other book that hashes to the same box on that card. The count in any one box is therefore an overestimate — never an underestimate (we never erase tallies). The minimum over four independently-hashed boxes is the least overestimated of the four — and as we’ll show, the chance that all four boxes are highly polluted by the same heavy-hitting collisions is small.

The asymmetry is the same as in Bloom filters: errors only happen in one direction (over-counting; never under-counting), and we tune the structure’s dimensions to make that error arbitrarily small at the cost of memory.

2. Tiny Worked Example (d = 3 rows, w = 4 columns)

Three independent hash functions, each producing a column index in [0, 4). Initial matrix: all zeros.

Stream of events: apple, apple, banana, apple, cherry, banana.

Suppose the hashes are:

	h₁	h₂	h₃
apple	1	3	0
banana	2	3	1
cherry	1	0	0

After processing the stream (counts shown per row, columns 0..3):

Row 1 (h₁): [0, 3+1, 1+1, 0]   = [0, 4, 2, 0]
Row 2 (h₂):  [1, 0, 0, 3+2]    = [1, 0, 0, 5]
Row 3 (h₃):  [3+1, 2, 0, 0]    = [4, 2, 0, 0]

Wait — let me recompute clearly. Stream is 6 inserts: apple 3 times, banana 2 times, cherry 1 time.

Row 1 (h₁): apple→col 1 adds 3, banana→col 2 adds 2, cherry→col 1 adds 1. Row 1 = [0, 4, 2, 0].
Row 2 (h₂): apple→col 3 adds 3, banana→col 3 adds 2, cherry→col 0 adds 1. Row 2 = [1, 0, 0, 5].
Row 3 (h₃): apple→col 0 adds 3, banana→col 1 adds 2, cherry→col 0 adds 1. Row 3 = [4, 2, 0, 0].

Now query each item:

query(apple): row 1 col 1 = 4; row 2 col 3 = 5; row 3 col 0 = 4. Min = 4. True count is 3, so overestimate by 1 (apple collides with cherry on row 1, with banana on row 2, with cherry on row 3).
query(banana): row 1 col 2 = 2; row 2 col 3 = 5; row 3 col 1 = 2. Min = 2. True count is 2 — exact.
query(cherry): row 1 col 1 = 4; row 2 col 0 = 1; row 3 col 0 = 4. Min = 1. True count is 1 — exact.
query(durian) (never inserted): suppose h₁(durian)=0, h₂(durian)=2, h₃(durian)=2. Row 1 col 0 = 0; row 2 col 2 = 0; row 3 col 2 = 0. Min = 0. Correct — we never overestimate items below their true count, but a never-seen item that happens to hash to all-collided cells could falsely report a positive count. This is the false-positive analog.

The mental model: every counter is a superset of the items hashing to it; the minimum is the least-polluted estimate; collisions only inflate counts, never deflate them.

3. The Algorithm

3.1 Construction

Choose error parameters:

ε = the multiplicative-error fraction (e.g., 0.01 = 1% of N).
δ = the failure probability (e.g., 0.001 = one in a thousand queries may exceed the error bound).

From these, set:

w = ⌈e/ε⌉ (where e is Euler’s number ≈ 2.718). Width of the table.
d = ⌈ln(1/δ)⌉. Depth (number of independent hash functions / rows).

Allocate a d × w matrix C of integer counters, initialized to 0. Choose d pairwise-independent hash functions h_1, ..., h_d : U → [0, w) from a universal hash family (see Hash Function Design).

3.2 Update — `update(x, c)` (insert x with count increment c)

function update(x, c=1):
    for i in 1..d:
        C[i, h_i(x)] += c

For deletion / decrement, use c < 0. The “Conservative Update” variant (Estan & Varghese 2002) only increments the minimum of the d counters and any others that match the minimum — gives empirically better accuracy on skewed distributions.

3.3 Point Query — `query(x)` (estimate frequency of x)

function query(x):
    return min over i in 1..d of C[i, h_i(x)]

3.4 Inner-Product Query

CMS supports more than point queries. Given two CMS structures A and B over the same dimensions and hash family, an estimate of the inner product a ⊙ b = Σ_x f_A(x) · f_B(x) is:

function inner(A, B):
    return min over i in 1..d of (Σ_j A[i, j] · B[i, j])

Theorem 3 of Cormode & Muthukrishnan (2005) gives the symmetric bound: a ⊙ b ≤ (a ⊙ b)_est, and with probability at least 1 − δ, (a ⊙ b)_est ≤ a ⊙ b + ε‖a‖₁‖b‖₁. Useful for self-join size estimation and similarity computations.

3.5 Heavy Hitters via CMS + Min-Heap

To find all items with frequency above φN (e.g., the top 1%), wrap CMS with a small min-heap of (estimated_freq, item) pairs. On every update of x, query CMS for the new estimate and conditionally insert into the heap if it exceeds φN. The heap is not part of CMS itself — CMS is point-query only — but this is the standard way the structure participates in heavy-hitter detection. (Misra-Gries gives an alternative deterministic heavy-hitter algorithm.)

4. Python Implementation

import math
from hashlib import blake2b
 
 
class CountMinSketch:
    """Count-Min Sketch for nonnegative frequency estimation.
 
    Parameters
    ----------
    epsilon : float
        Multiplicative error tolerance. The estimate exceeds the true count
        by at most epsilon * N (total inserts) with probability ≥ 1 - delta.
    delta : float
        Failure probability.
    """
 
    def __init__(self, epsilon: float = 0.001, delta: float = 0.001):
        self.w = max(1, math.ceil(math.e / epsilon))         # cols
        self.d = max(1, math.ceil(math.log(1.0 / delta)))    # rows
        self.table: list[list[int]] = [[0] * self.w for _ in range(self.d)]
        self.n = 0                                           # total inserts
 
    def _indices(self, item: bytes):
        # Two-hash trick (Kirsch-Mitzenmacher 2006): one BLAKE2b call gives
        # 256 bits; we slice into two 64-bit halves and combine linearly to
        # simulate d independent hashes, with no asymptotic loss in error.
        h = blake2b(item, digest_size=16).digest()
        a = int.from_bytes(h[:8], "big")
        b = int.from_bytes(h[8:], "big")
        for i in range(self.d):
            yield (a + i * b) % self.w
 
    def update(self, item: str, count: int = 1) -> None:
        if count < 0:
            raise ValueError("standard CMS does not support deletes; use CMS-Conservative or signed Count Sketch")
        self.n += count
        b = item.encode()
        for i, j in enumerate(self._indices(b)):
            self.table[i][j] += count
 
    def query(self, item: str) -> int:
        b = item.encode()
        return min(self.table[i][j] for i, j in enumerate(self._indices(b)))
 
 
# --- demo ----------------------------------------------------------------
if __name__ == "__main__":
    import random, collections
    cms = CountMinSketch(epsilon=0.001, delta=0.001)
    print(f"d = {cms.d} rows, w = {cms.w} cols, total = {cms.d * cms.w} cells")
 
    # Generate a Zipf-distributed stream.
    true_counts = collections.Counter()
    for _ in range(100_000):
        x = f"item_{int(random.paretovariate(1.5))}"
        cms.update(x)
        true_counts[x] += 1
 
    # Check the top 5 items: estimates should be very close to truth.
    for item, true in true_counts.most_common(5):
        est = cms.query(item)
        err = est - true
        print(f"{item}: true={true}, est={est}, over={err}")

Two implementation choices to call out:

Two-hash trick. Like the Bloom Filter implementation, we generate d “independent” hashes from one cryptographic hash via the Kirsch-Mitzenmacher formula h_i(x) = (a + i·b) mod w. The 2006 ESA paper proves no asymptotic loss in false-positive / overestimate rate; in practice the constants are slightly worse than truly independent hashes but indistinguishable on most workloads.
No deletes in standard CMS. Decrementing is mathematically valid but breaks the no-underestimate guarantee in the presence of the two-hash trick (a decrement on a key not currently in the multiset would produce negative counts). Use Count Sketch (Charikar et al. 2002) for signed updates, or CMS-Conservative for skewed read-mostly workloads.

5. Math — Why the Error Bound Holds

This is the section that interviewers probe. The full proof from Cormode-Muthukrishnan 2005 is short and worth knowing.

5.1 Setup

Let a be the implicit frequency vector with a_x = f_x the true frequency of item x in the stream so far, and let N = ‖a‖₁ = Σ_x f_x be the total number of insertions (for the non-negative cash-register case the paper specifies). Let f̂_x = min_i C[i, h_i(x)] be the CMS estimate. The paper states the error bound in terms of the L₁ norm ‖a‖₁ rather than “N” — for the non-negative case the two are identical, but the L₁ framing generalises cleanly to the signed turnstile case where N (count of updates) and ‖a‖₁ (current absolute mass) diverge.

5.2 No underestimate

For each row i, the cell C[i, h_i(x)] is incremented every time x is inserted (always) and every time some other y with h_i(y) = h_i(x) is inserted (collision). Thus:

$C [i, h_{i} (x)] = f_{x} + \sum_{y \neq = x, h_{i} (y) = h_{i} (x)} f_{y} \geq f_{x}$

Taking the min over i preserves the inequality:

$\hat{f}_{x} \geq f_{x}$

so CMS never underestimates. This is a deterministic guarantee, not probabilistic.

5.3 Overestimate bound — single row

Define X_{i,x} = C[i, h_i(x)] − f_x, the per-row collision noise. By construction:

$X_{i, x} = \sum_{y \neq = x, h_{i} (y) = h_{i} (x)} f_{y}$

Each y ≠ x contributes f_y to X_{i,x} with probability 1/w (the chance a pairwise-independent hash function maps y to x’s column — Cormode & Muthukrishnan write this as 1/range(h_j) = ε/e once w = ⌈e/ε⌉ is substituted). Taking the expectation:

$E [X_{i, x}] = \sum_{y \neq = x} f_{y} \cdot P (h_{i} (y) = h_{i} (x)) \leq \sum_{y} \frac{f _{y}}{w} = \frac{∥ a ∥ _{1}}{w} = \frac{ε}{e} ∥ a ∥_{1}$

Now apply Markov’s inequality with threshold ε‖a‖₁:

$P (X_{i, x} \geq ε ∥ a ∥_{1}) \leq \frac{E [ X _{i, x} ]}{ε ∥ a ∥ _{1}} \leq \frac{ε ∥ a ∥ _{1} / e}{ε ∥ a ∥ _{1}} = \frac{1}{e}$

So with w = ⌈e/ε⌉ the probability that any single row’s overestimate exceeds ε‖a‖₁ is at most 1/e ≈ 0.368. (This is precisely the calculation on page 7 of the preprint.)

5.4 Overestimate bound — taking the minimum

The estimate f̂_x − f_x = min_i X_{i,x}. The minimum exceeds ε‖a‖₁ only if every row’s overestimate exceeds ε‖a‖₁. Because the d hash functions are chosen independently from the pairwise-independent family, the events {X_{i,x} ≥ ε‖a‖₁} for i=1..d are independent:

$P (\hat{f}_{x} - f_{x} \geq ε ∥ a ∥_{1}) = \prod_{i = 1}^{d} P (X_{i, x} \geq ε ∥ a ∥_{1}) \leq (\frac{1}{e})^{d} = e^{- d}$

Setting d = ⌈ln(1/δ)⌉ makes e^{−d} ≤ δ. Thus:

$P (\hat{f}_{x} - f_{x} \geq ε ∥ a ∥_{1}) \leq δ$

with probability at least 1 − δ, the CMS estimate exceeds the true count by at most ε‖a‖₁. Q.E.D. — this is exactly Theorem 1 of Cormode & Muthukrishnan (2005).

5.5 Sizing the structure

For a desired error ε and confidence 1 − δ:

Parameter	Formula	Example: ε = 0.001, δ = 0.001
Width w	⌈e/ε⌉	⌈2.718/0.001⌉ = 2,719
Depth d	⌈ln(1/δ)⌉	⌈6.908⌉ = 7
Cells	w × d	2,719 × 7 = 19,033
Memory @ 4 B counter	4 × w × d bytes	~76 KB

So a CMS sized at ε=0.001 absolute error (relative to ‖a‖₁) at 99.9% confidence costs about 76 KB regardless of the stream’s cardinality. A stream with 10 billion distinct items can be summarized in the same 76 KB. This is the magic — and the abstract of Cormode & Muthukrishnan (2005) calls this out as their main contribution over prior sketches: space scales as 1/ε, not 1/ε², “typically from 1/ε² to 1/ε in factor.”

The error is a function of ‖a‖₁ (≡ stream length N in the non-negative case), not of cardinality. An item x with true frequency 0.5N (i.e., half the stream) will be estimated at between 0.5N and 0.501N. An item with true frequency 100 (vanishingly small relative to N=10⁹) will be estimated at between 100 and 10⁶ — the absolute error ε‖a‖₁ = 10⁶ swamps it. CMS is good at heavy hitters, bad at long-tail items. That’s why production heavy-hitter pipelines use CMS for the top-K and a separate exact counter for monitored items.

5.6 Comparison with Count Sketch

Count Sketch (Charikar, Chen & Farach-Colton 2002, two years before CMS) uses signed updates: each row has a sign function s_i: U → {−1, +1}, and updates write C[i, h_i(x)] += s_i(x) · c. Queries take the median rather than the minimum. Properties:

Count Sketch is unbiased (E[f̂_x] = f_x) — useful when both over- and under-estimates are needed.
CMS is biased upward (always ≥ f_x) — useful when over-counting is acceptable but under-counting is not (e.g., admission filters).
Count Sketch’s L₂-error bound is √(F₂/w) where F₂ is the second moment — tighter than CMS for skewed distributions.
CMS’s L∞-error bound is N/w (looser, but holds even for adversarial streams).

For most heavy-hitter applications, CMS is the simpler choice; Count Sketch wins when you need unbiasedness or tight L₂ bounds.

6. Production Use Cases

Network monitoring / DDoS detection. Routers and switches use CMS-like sketches to track per-source-IP packet rates without storing per-flow state. The original Cormode-Muthukrishnan-Strauss line of work (DIMACS / AT&T Research) motivated CMS explicitly for IP-flow heavy-hitter detection; their 2005 paper is the canonical citation for the algorithm.
W-TinyLFU admission filter (Caffeine). Caffeine’s FrequencySketch class implements a 4-bit CMS — counters saturate at 15, and the class uses 16 counters per slot so each long word holds an aligned block for hardware-friendly access. Aging is performed by the reset() method: when the internal size counter reaches sampleSize = min(10·maximum, Integer.MAX_VALUE), all counters are halved and size is adjusted by the count of odd-valued counters discarded by the integer shift. This is the central decay mechanism that lets W-TinyLFU adapt to non-stationary workloads. (Source: FrequencySketch.java in the Caffeine repository, and the project’s “Efficiency” wiki page.) This is the largest production deployment of CMS by request volume — every Spring Boot app using Caffeine’s default settings runs CMS in its hot path.
Apache Spark approximate aggregations. DataFrameStatFunctions.countMinSketch(col, eps, confidence, seed) and the SQL function pyspark.sql.functions.count_min_sketch(col, eps, confidence, seed) build a sketch over a column; both overloads accept either (eps, confidence) or explicit (depth, width) and return a CountMinSketch object — used in approximate group-by counts at petabyte scale.
Apache DataSketches (Yahoo / Apache project) — production-grade CMS implementation alongside Theta Sketch (cardinality), KLL Sketch (quantiles).
Redis Stack — CMS.* commands (RedisBloom probabilistic module, v2.0+). The commands are CMS.INITBYDIM key width depth, CMS.INITBYPROB key error probability, CMS.INCRBY, CMS.QUERY, CMS.INFO, CMS.MERGE. Notably Redis uses w = 2/error — not the paper’s w = ⌈e/ε⌉ — so a Redis sketch with error = 0.001 has width = 2000 (vs. the paper’s 2,719). This is a constant-factor tradeoff: Redis trades a slightly looser per-row bound for round-number widths.
Microsoft SQL Server’s Compressed Statistics. Internal use of frequency sketches for query optimizer cardinality estimation.
Twitter Algebird library — CMS as part of a Scala approximate-analytics suite.
Heavy-hitter / “trending topics” pipelines. Twitter’s trending topics, ad-tech click-counting, real-time recommendation popularity tracking. The CMS+heap pattern (§3.5) is canonical here.

7. Variants

7.1 CMS-Conservative Update (Estan & Varghese 2002)

Increment only the minimum of the d selected cells (and any others that tie at the minimum). Rationale: incrementing cells that are already over the true count adds noise without benefit. Empirically halves the average overestimate on Zipf-distributed streams. Same correctness guarantees on the upper bound; tighter in practice.

7.2 Count-Mean-Min Sketch (Deng & Rafiei 2007)

Subtract the row-mean (an estimate of the per-row noise floor) before taking the minimum. Bias-corrected; sometimes negative for very low-frequency items (clip to 0).

7.3 Count Sketch (Charikar et al. 2002)

Signed updates and median queries. Unbiased estimator. See §5.6.

7.4 Bias-Aware CMS / DCM (Roy et al. 2016)

Approximate the noise distribution and subtract its expectation. Gains a few percent on long-tail items.

7.5 Sliding-Window / Aging CMS

Periodically halve all counters (TinyLFU’s “freshness” mechanism), or maintain multiple CMS structures over time windows and combine. Aging makes the structure responsive to non-stationary streams.

7.6 Distributed / Mergeable CMS

CMS with the same dimensions and hash family is linearly mergeable: C_merged[i, j] = C_A[i, j] + C_B[i, j]. This is the property that makes CMS a good fit for MapReduce and Spark — each partition computes its local CMS, and the reducer adds them cellwise. The error bound on the merged sketch is the same as a single CMS over the concatenated stream.

7.7 CMS for Inner Products and Range Queries

Range queries (e.g., “estimate Σ_{x ∈ [a, b]} f_x”) use a hierarchy of CMS structures at different granularities — O(log U) overhead. See Cormode-Muthukrishnan 2005 §3 for details.

8. Pitfalls

8.1 Error is Relative to ‖a‖₁ (≈ N), Not f_x

The most common interview / production misconception. CMS guarantees f̂_x ≤ f_x + ε‖a‖₁ — additive in the L₁ norm of the frequency vector (equivalently the stream length N for the non-negative case). For an item with true frequency 1 in a stream of 10⁹, with ε=0.001, the bound is f̂_x ≤ 1 + 10⁶. CMS will tell you “this item appeared between 1 and a million times” — useless for tail items, fine for heavy hitters.

8.2 No Native Deletions

Standard CMS doesn’t support deletions: a decrement on an item that wasn’t inserted produces meaningless results. Use Count Sketch for signed updates, or a counting-Bloom-style variant for limited delete support.

8.3 Hash Function Quality

The error bound assumes pairwise-independent hashes. Using a weak hash family (e.g., hash(x) % w with a non-uniform distribution) inflates collision rates and can blow up the bound. Use a universal hash family — see Hash Function Design.

8.4 Choosing ε and δ Backward

Beginners sometimes set ε and δ to match the cardinality of the stream rather than its length. The math depends only on N. If you expect N=10¹⁰ insertions and want to detect heavy hitters with frequency ≥ 10⁵, you need ε ≤ 10⁵ / 10¹⁰ = 10⁻⁵, giving w ≈ 270K. Don’t size the sketch for cardinality.

8.5 Counter Width

For a 32-bit counter, the maximum value is ~4.3 × 10⁹. At streaming rates of 10⁶ updates/second this overflows in ~1 hour for a heavy hitter. Use 64-bit counters or saturating arithmetic.

8.6 Using CMS for Cardinality

CMS estimates frequencies of specific items; it does not estimate distinct-element count. For “how many distinct items have we seen?” use HyperLogLog (which is the dual structure: distinct-cardinality at sub-linear space).

8.7 Collisions Are Not Independent Across Rows

The independence assumption in §5.4 holds for truly independent hash functions. In practice (with the two-hash trick) the collisions are correlated in subtle ways. The error bound is slightly looser empirically than the theoretical δ; calibrate before deploying with very tight δ (e.g., 10⁻⁹).

8.8 Heavy-Hitter Algorithm Conflation

“Heavy hitters” can mean (a) ε-approximate top-K (CMS+heap), or (b) Misra-Gries style “any item with frequency > φN” (a different, deterministic algorithm with O(1/φ) space). They have different guarantees — don’t conflate.

9. Diagram — d × w Matrix with d Hash Functions

flowchart TD
    X["Item x"] --> H1["h₁(x) → col 2"]
    X --> H2["h₂(x) → col 5"]
    X --> H3["h₃(x) → col 1"]
    X --> H4["h₄(x) → col 7"]

    subgraph "d × w counter matrix"
        R1["Row 1: [_, _, +1, _, _, _, _, _]"]
        R2["Row 2: [_, _, _, _, _, +1, _, _]"]
        R3["Row 3: [_, +1, _, _, _, _, _, _]"]
        R4["Row 4: [_, _, _, _, _, _, _, +1]"]
    end

    H1 --> R1
    H2 --> R2
    H3 --> R3
    H4 --> R4

    Q["Query x"] --> READ["Read C[i, h_i(x)] for i=1..d"]
    READ --> MIN["Return min over rows"]

What this diagram shows. On update(x), x hashes to one column per row via d independent hash functions; the corresponding cell in each row is incremented. On query(x), we read those same d cells and return the minimum. The rows are independent — collisions on row 1 don’t imply collisions on row 2. This independence is what powers the δ ≈ e^(−d) bound: we need all rows to be unlucky simultaneously for the estimate to exceed the error tolerance, and that compounds exponentially in d. The diagram intentionally omits the modulus arithmetic and the actual hash family — those are details; the d ⊥ w topology is the load-bearing concept.

10. Common Interview Problems

System-design rounds where CMS is the right answer:

Problem	Why CMS
Design YouTube view counter (approximate)	Per-video CMS counters at edge, merged centrally
Design Twitter trending topics	CMS + min-heap for top-K hashtags
Design a heavy-hitter detector for a network	The original CMS application
Design an ad click counter at scale	CMS to dedupe / count without per-click row storage
Design a recommendation popularity tracker	CMS as input to ranking
Design a cache admission filter	W-TinyLFU’s CMS-based frequency estimate
Design an analytics dashboard (“approximate counts ok”)	CMS for “events per category per time window”
Find the top-K items in a stream	CMS + min-heap; or Misra-Gries for deterministic

For coding rounds CMS appears less often than Bloom Filter (it’s harder to fit on a whiteboard), but the math derivation in §5 is interview gold for senior / staff system-design rounds where the interviewer wants to gauge depth.

11. Open Questions

Does CMS-Conservative’s empirical advantage on Zipf streams provably extend to heavy-tailed but non-Zipf distributions, or is the gap workload-specific?
At what stream length does the two-hash trick (Kirsch-Mitzenmacher) start measurably degrading vs truly independent hashes? Most papers say “doesn’t matter at practical sizes” but I haven’t seen rigorous calibration.
How do CMS and HyperLogLog combine — is there a “Count-Min HyperLogLog” hybrid that estimates frequency-weighted distinct cardinality in sublinear space?
When does Count Sketch’s unbiasedness justify its larger constant overhead vs CMS in production? Empirical guidance is thin.

12. See Also

Bloom Filter — sister probabilistic structure (membership, not frequency)
HyperLogLog — sister probabilistic structure (cardinality, not frequency)
Count Sketch — unbiased relative; signed updates; median estimator
Hash Function Design — universal hash families needed for the error bound
Hash Table — exact counterpart at O(N) space
Top K Elements — CMS + heap is the canonical streaming top-K
Least Frequently Used Cache — TinyLFU uses CMS as its frequency estimator
Reservoir Sampling — sister streaming algorithm
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Count-Min Sketch

Count-Min Sketch

1. Intuition — A Stack of Lossy Tally Cards

2. Tiny Worked Example (d = 3 rows, w = 4 columns)

3. The Algorithm

3.1 Construction

3.2 Update — update(x, c) (insert x with count increment c)

3.3 Point Query — query(x) (estimate frequency of x)

3.4 Inner-Product Query

3.5 Heavy Hitters via CMS + Min-Heap

4. Python Implementation

5. Math — Why the Error Bound Holds

5.1 Setup

5.2 No underestimate

5.3 Overestimate bound — single row

5.4 Overestimate bound — taking the minimum

5.5 Sizing the structure

5.6 Comparison with Count Sketch

6. Production Use Cases

7. Variants

7.1 CMS-Conservative Update (Estan & Varghese 2002)

7.2 Count-Mean-Min Sketch (Deng & Rafiei 2007)

7.3 Count Sketch (Charikar et al. 2002)

7.4 Bias-Aware CMS / DCM (Roy et al. 2016)

7.5 Sliding-Window / Aging CMS

7.6 Distributed / Mergeable CMS

7.7 CMS for Inner Products and Range Queries

8. Pitfalls

8.1 Error is Relative to ‖a‖₁ (≈ N), Not f_x

8.2 No Native Deletions

8.3 Hash Function Quality

8.4 Choosing ε and δ Backward

8.5 Counter Width

8.6 Using CMS for Cardinality

8.7 Collisions Are Not Independent Across Rows

8.8 Heavy-Hitter Algorithm Conflation

9. Diagram — d × w Matrix with d Hash Functions

10. Common Interview Problems

11. Open Questions

12. See Also

Graph View

Table of Contents

Backlinks

3.2 Update — `update(x, c)` (insert x with count increment c)

3.3 Point Query — `query(x)` (estimate frequency of x)