Count–Min Sketch

Count–Min Sketch (CM Sketch) is a sublinear-space probabilistic streaming data structure and randomized algorithm in computation and algorithms that summarizes a high-velocity stream of frequency updates and answers point frequency queries, range queries, inner-product queries, and heavy-hitter (frequent-item) queries in O(d) constant time and O(d · w) fixed space. Introduced by Graham Cormode and S. Muthukrishnan in 2005 (first presented at LATIN 2004 and published in Journal of Algorithms), the Count–Min sketch functions as a compact, general-purpose linear projection of an implicit frequency vector a ∈ ℝ^U over a massive key universe U.

Whereas a Bloom filter answers binary set-membership queries (a_x > 0 vs. a_x = 0) and HyperLogLog estimates the total number of distinct keys (‖a‖₀), the Count–Min sketch estimates the multiplicity or cumulative weight a_x of any individual item x ∈ U. By maintaining a two-dimensional d × w grid of integer counters indexed by d pairwise-independent hash functions, a Count–Min sketch with width w = ⌈e / ε⌉ and depth d = ⌈ln(1 / δ)⌉ uses only O((1 / ε) ln(1 / δ)) counters—independent of the universe cardinality |U|—to return an estimate â_x satisfying the one-sided error bound a_x ≤ â_x ≤ a_x + ε ‖a‖₁ with probability at least 1 − δ.

The d × w Counter Array and Pairwise-Independent Hashing

Consider a data stream of updates (x_t, c_t) targeting an implicit frequency vector a = [a₁, a₂, ..., a_|U|] initialized to zero, where each arrival (x_t, c_t) increments coordinate a_xt ← a_xt + c_t. In the standard cash-register (non-negative turnstile) model, all increments are non-negative (c_t ≥ 0), so the ℓ₁ norm of the stream is ‖a‖₁ = ∑_y∈U a_y = N.

Given a target additive error factor ε ∈ (0, 1) and failure probability δ ∈ (0, 1), a Count–Min sketch allocates a two-dimensional array C[1 .. d][0 .. w − 1] of d rows and w columns initialized to 0, where:

Each row i ∈ {1, 2, ..., d} is associated with a hash function h_i : U → {0, 1, ..., w − 1} drawn independently from a pairwise-independent (2-universal) hash family H (for example, h_i(x) = ((α_ix + β_i) mod p) mod w for a prime p > |U|), satisfying Pr[h_i(x) = h_i(y)] ≤ 1 / w for all x ≠ y:

1. Update(x, c): For each row i = 1, 2, ..., d, add c to the hashed counter in row i:

1. Point Query Estimate(x): Return the minimum counter value across all d rows:

One-Sided Overestimation and Expected Collision Noise

In the non-negative stream model (a_y ≥ 0 for all y ∈ U), every counter C[i][h_i(x)] contains the true count a_x plus the counts of all other elements y ≠ x that happened to collide with x in row i:

Because X_i,x ≥ 0 in every row i, taking the minimum across the d rows can never underestimate the true count (â_x ≥ a_x). By linearity of expectation and pairwise independence of h_i (E[1[h_i(x) = h_i(y)]] ≤ 1 / w), the expected collision noise in any single row i is bounded by:

Exponential Tail Decay via d Independent Rows

Applying Markov's inequality to the non-negative random variable X_i,x in row i yields the probability that row i overestimates a_x by more than ε ‖a‖₁:

Because the d hash functions h₁, ..., h_d are mutually independent, the minimum estimate â_x = min_i (a_x + X_i,x) exceeds a_x + ε ‖a‖₁ if and only if every single one of the d rows simultaneously suffers a collision error exceeding ε ‖a‖₁:

For example, choosing w = 2,719 (ε = 0.001 = 0.1% of total stream volume) and d = 5 rows (δ = e⁻⁵ ≈ 0.0067 = 99.33% confidence) requires just 5 × 2,719 = 13,595 counters (54.4 KB using 32-bit integers) regardless of whether the stream contains a million or a trillion distinct keys.

When deletions (c_t < 0) are not required, Count–Min with Conservative Update (CM-CU) (adapted from Estan & Varghese's Multistage Filters, 2002) reduces empirical overestimation error by a factor of 2× to 5× without adding a single bit of memory: to insert (x, c) with c > 0, first compute the current estimate â_x = min_j C[j][h_j(x)], and then update each row i via:

In other words, a counter that already exceeds â_x + c due to prior collisions from other keys is not unnecessarily incremented further.

Because the standard Count–Min sketch is a linear sketch (C(αa + βb) = αC(a) + βC(b)), sketches computed on distributed shards or network switches can be added or subtracted elementwise, and inner products a · b are estimated via min_i ∑_j=0..w−1 *C_a*[i][j] *C_b*[i][j]. In Caffeine (the high-performance Java caching library powering Cassandra, Finagle, and Neo4j), a 4-bit TinyLFU Count–Min sketch tracks access frequencies of millions of cache keys in 8 bytes per cached entry to achieve near-optimal admission control. In bioinformatics, the khmer library (Zhang et al., 2014) uses Count–Min sketches to count DNA k-mer abundances across terabase-scale metagenomic sequencing reads in fixed RAM alongside cuckoo hashing and locality-sensitive hashing indexes.

How does the Count–Min sketch differ from the Count Sketch (Charikar, Chen, & Farach-Colton, 2002)?

In the Count–Min sketch, every row increments C[i][h_i(x)] by +c and queries take the minimum, giving a one-sided error O(ε ‖a‖₁) using O(1/ε) columns. In the Count Sketch, each row multiplies c by a second pairwise-independent random sign s_i(x) ∈ {−1, +1} so collision noise cancels in expectation (E[s_i(x)*s_i*(y)] = 0), and queries take the median across rows, achieving a two-sided ℓ₂ error bound O(ε ‖a‖₂) at the cost of O(1/ε²) columns.

How can a Count–Min sketch answer 1D range queries a[l .. r] = ∑_k=l..r a_k in logarithmic time?

Summing r − l + 1 individual point queries would accumulate(r − l + 1)ε ‖a‖₁ error. Instead, Cormode and Muthukrishnan maintain log₂ |U| parallel Count–Min sketches corresponding to the levels of a binary dyadic interval tree over [0, |U| − 1]. Each update increments O(log |U|) dyadic intervals containing x, and any range [l, r] decomposes into the disjoint union of at most 2 log₂ |U| canonical dyadic intervals, bounding total range error by 2(log₂ |U|)ε ‖a‖₁.

What happens to the query procedure when negative updates (deletions c_t < 0) are allowed in the strict turnstile model?

In the strict turnstile model, individual updates c_t may be positive or negative (representing insertions and deletions), provided the net cumulative frequency of every item remains non-negative (a_y ≥ 0 at query time). Because a_y ≥ 0 for all y, the collision noise X_i,x = ∑_y≠x a_y 1[h_i(x) = h_i(y)] remains non-negative, so the exact same minimum estimator â_x = min_i C[i][h_i(x)] continues to hold with one-sided error ≤ ε ‖a‖₁ (whereas if net frequencies a_y can become negative in the general turnstile model, the median across rows is used with width w = ⌈3 / ε⌉).

1. Cormode, G., & Muthukrishnan, S. (2005). "An improved data stream summary: the count-min sketch and its applications." Journal of Algorithms, 55(1), 58–75. https://doi.org/10.1016/j.jalgor.2003.12.001
2. Estan, C., & Varghese, G. (2002). "New directions in traffic measurement and accounting." ACM SIGCOMM Computer Communication Review, 32(4), 323–336. https://doi.org/10.1145/964725.633056
3. Charikar, M., Chen, K., & Farach-Colton, M. (2002). "Finding frequent items in data streams." Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), LNCS Vol. 2380, 693–703. https://doi.org/10.1007/3-540-45465-9_59
4. Zhang, Q., Pell, J., Canino-Koning, R., Howe, A. C., & Brown, C. T. (2014). "These are not the k-mers you are looking for: efficient online k-mer counting using a probabilistic data structure." PLOS ONE, 9(7), e101271. https://doi.org/10.1371/journal.pone.0101271
5. Einziger, G., Friedman, R., & Manes, B. (2017). "TinyLFU: A highly efficient cache admission policy." ACM Transactions on Storage, 13(4), 35:1–35:31. https://doi.org/10.1145/3149371