Count-Min Sketch Explained: Frequency Estimation at Streaming Scale

Scenario context

Count-Min Sketch (CMS) is a fixed-size d × w counter matrix that estimates how often any element has appeared in a stream. Insert: hash the element with each of the d hash functions to get one column per row, increment those d counters. Query: read the same d counters, return the minimum — an upper bound that is never an underestimate. With d = 7 rows and w = 2000 columns, a ~112 KB sketch delivers <…

This walkthrough focuses on The Frequency Estimation Problem: Trending at Twitter Scale.

Before making a design choice, clarify:

• Twitter's trending topics feature shows the hashtags gaining the most momentum in the last five minutes.
• At peak load, tens of millions of tweets arrive per minute.
• Every tweet may contain one or more hashtags.

Concepts in play: sorting-and-searching-algorithms, hash-tables-and-bloom-filters, jvm-internals-and-garbage-collection, caching

Stage 1 — The d × w Counter Matrix: One Row Per Hash Function

• A Count-Min Sketch has two parameters: - d (depth) — the number of rows.
• Each row has its own independent hash function.
• • w (width) — the number of columns per row.
• This determines the counter resolution.

counters[d][w]   — all entries start at 0

Observable outcome: This determines the counter resolution.

Stage 2 — Insert and Query: The Minimum Across Rows Is Always an Upper Bound

• Insert: d Increments, One Per Row To record that element x appeared (or appeared with weight weight ): Every insert touches exactly d counter cells — one per row.
• The column in each row is determined by that row's independent hash function.
• Weight is typically 1 for event counting, but weighted inserts (e.g., for byte-counting in network traffic) are supported by using the byte count as the weight.
• Query: Read d Counters, Return the Minimum To estimate how often element x has appeared: Why the minimum?

for i in 0..d:
    col = h_i(x) mod w
    counters[i][col] += weight

estimate = +∞
for i in 0..d:
    col = h_i(x) mod w
    estimate = min(estimate, counters[i][col])
return estimate

Observable outcome: Query: Read d Counters, Return the Minimum To estimate how often element x has appeared: Why the minimum?

Stage 3 — Deep Dive: Error Bounds, Heavy Hitters, and Performance

• The Internals: Hash Independence and Counter Width The error guarantee of Count-Min Sketch depends on the hash functions being pairwise independent — knowing that element x hashes to column c in row i tells you nothing…
• If hash functions are correlated, the collision events across rows become correlated too, and the minimum-across-rows estimate loses its tightness.
• In practice, row-wise hash functions are often derived by the formula: where a i and b i are distinct random coefficients for each row chosen at construction time.
• This universal hashing family provides the required pairwise independence at low computational cost.

h_i(x) = ((a_i * x + b_i) mod prime) mod w

P(estimate ≤ true_count + ε × n) ≥ 1 − δ

Observable outcome: This universal hashing family provides the required pairwise independence at low computational cost.

Stage 4 — Visualizing Count-Min Sketch Insert and Query

• The following diagram traces the complete insert-and-query lifecycle for a hashtag event, showing how each row's hash function maps the element to an independent column, why collisions can inflate individual row counter…
• The minimum-across-rows selection is the probabilistic heart of Count-Min Sketch: each row's independent hash function randomizes collision patterns, so a counter that is inflated in row i is unlikely to also be inflate…
• The minimum captures the row least affected by collisions.

flowchart TD
    A(["Incoming event: tweet contains #kubernetes"]) --> B["Hash #kubernetes with each of d=7 hash functions"]
    B --> C["Row 0: h0('#kubernetes') → col 2\nRow 1: h1('#kubernetes') → col 5\n...\nRow 6: h6('#kubernetes') → col 1"]
    C --> D["Increment counters[0][2], counters[1][5], ..., counters[6][1]"]
    D --> E(["Insert complete — d=7 counter cells updated"])

    A2(["Query: how often has #kubernetes appeared?"]) --> F["Hash #kubernetes with same d=7 hash functions"]
    F --> G["Read counters[0][2], counters[1][5], ..., counters[6][1]"]
    G --> H{"Some rows may have collisions\nfrom other elements hashing to same column"}
    H -->|"collision in row i"| I["counter[i][col] is inflated\nreports count higher than true frequency"]
    H -->|"no collision in row j"| J["counter[j][col] equals or approximates true frequency"]
    I --> K["Return minimum across all 7 row values"]
    J --> K
    K --> L(["Estimated frequency — always ≥ true count\nnever an underestimate"])

    style E fill:#3b82f6,color:#fff
    style L fill:#22c55e,color:#fff
    style I fill:#f59e0b,color:#fff

Observable outcome: The minimum captures the row least affected by collisions.

Stage 5 — Production Deployments: Where Count-Min Sketch Runs in Industry

• CMS tracks hashtag occurrence frequency in sliding five-minute windows.
• The top-K hashtags in the trending sidebar come from Count-Min Sketch estimates, not exact counts.
• Exact counting at Twitter's scale — tens of millions of tweets per minute, with millions of distinct active hashtags — would require hundreds of gigabytes of counter state per analytics tier.
• The CMS sketch for the same workload fits in a few hundred kilobytes.

Observable outcome: The CMS sketch for the same workload fits in a few hundred kilobytes.

Stage 6 — Implementing Count-Min Sketch in Java

• The following Java implementation demonstrates the complete insert-query lifecycle with pairwise-independent hash functions per row.
• Usage example — Twitter-style trending hashtag detection: Three additional streaming problems solved by the same structure: 1.
• Network packet rate monitoring.
• Insert each packet's source IP with weight = packet size in bytes.

public class CountMinSketch {

    private final long[][] counters;  // [depth][width]
    private final int width;          // w — columns per row
    private final int depth;          // d — number of rows / hash functions
    private final long[] a;           // hash function coefficient a_i
    private final long[] b;           // hash function coefficient b_i
    private static final long PRIME = 2_038_074_743L; // a large prime

    /**
     * @param width  w — number of columns (e = e/ε ≈ 2.718 / target_error_fraction)
     * @param depth  d — number of rows (d = ⌈ln(1/δ)⌉)
     */
    public CountMinSketch(int width, int depth) {
        this.width = width;
        this.depth = depth;
        this.counters = new long[depth][width];

        // Initialize random hash function coefficients
        java.util.Random rand = new java.util.Random(42);
        this.a = new long[depth];
        this.b = new long[depth];
        for (int i = 0; i < depth; i++) {
            a[i] = (long) (rand.nextInt(Integer.MAX_VALUE)) + 1;
            b[i] = (long) (rand.nextInt(Integer.MAX_VALUE));
        }
    }

    /** Insert element with weight (use weight=1 for simple event counting). */
    public void insert(String element, long weight) {
        int hashCode = element.hashCode();
        for (int i = 0; i < depth; i++) {
            int col = (int) ((Math.abs(a[i] * hashCode + b[i]) % PRIME) % width);
            counters[i][col] += weight;
        }
    }

    /**
     * Estimate frequency of element.
     * Returned value is always >= true frequency (upper bound guarantee).
     */
    public long estimate(String element) {
        int hashCode = element.hashCode();
        long minCount = Long.MAX_VALUE;
        for (int i = 0; i < depth; i++) {
            int col = (int) ((Math.abs(a[i] * hashCode + b[i]) % PRIME) % width);
            minCount = Math.min(minCount, counters[i][col]);
        }
        return minCount;
    }
}

// Size for 0.5% error (ε=0.005) with 99.9% confidence (δ=0.001)
int w = (int) Math.ceil(Math.E / 0.005);   // ~544 columns
int d = (int) Math.ceil(Math.log(1 / 0.001)); // 7 rows
CountMinSketch cms = new CountMinSketch(w, d);

// Simulate tweet stream
long totalEvents = 0;
cms.insert("#kubernetes", 1); totalEvents++;
cms.insert("#docker", 1);     totalEvents++;
cms.insert("#kubernetes", 1); totalEvents++;
cms.insert("#k8s", 1);        totalEvents++;
// ... millions more events ...

// Query frequency
long k8sEstimate = cms.estimate("#kubernetes");
System.out.println("#kubernetes estimate: " + k8sEstimate);
// Result: >= 2 (true count), bounded by ε × totalEvents error

// Heavy hitter check: is #kubernetes responsible for >0.5% of all events?
if (k8sEstimate > 0.005 * totalEvents) {
    System.out.println("#kubernetes is a heavy hitter");
}

Observable outcome: Insert each packet's source IP with weight = packet size in bytes.

End-to-end outcome

After working through the stages, you should be able to explain:

• Count-Min Sketch answers frequency, not membership or cardinality.
• It tells you how often element X has appeared — not whether X is in the set (Bloom Filter's job) and not how many distinct elements there are (HyperLogLog's job).
• Count-Min Sketch is the right structure when you need to estimate "how often has X appeared?" in a high-volume stream using fixed, pre-allocated memory.
• • Core guarantee: estimates are always ≥ true frequency — the minimum across all d rows is an upper bound, never an underestimate.

Alternatives considered

Decision Guide: Count-Min Sketch vs Exact Counter vs HyperLogLog

The deciding question: Do you need to estimate how often a specific element has appeared in a stream, using fixed memory?

Failure and degraded modes

Trade-offs and Failure Modes

• Detection: Always overestimates, never underestimates.
• User or operator impact: Always overestimates, never underestimates.