Count-Min Sketch: Counting Millions of Events with Kilobytes of Memory

⏱️ Lectura: 12 min

A firewall that sees millions of packets per second can’t open an entry in a hash table for every distinct IP it processes: it runs out of memory in minutes. It needs to count without storing each event, and that’s where the count-min sketch comes in, a probabilistic data structure that estimates how many times something happened using just a few kilobytes.

📑 En este artículo

1. TL;DR
2. What the count-min sketch is and why it matters
3. How it works internally
4. Practical examples with code
5. How to get started step by step
6. Real-world use cases
7. Common mistakes and best practices
8. Comparison with alternatives
9. Going deeper: conservative update and advanced variants
10. Frequently Asked Questions
    1. Can the count-min sketch give a result lower than the real count?
    2. How do I choose the matrix’s width and depth?
    3. Can a count-min sketch be merged with another one?
    4. Can it count elements that I later want to remove?
    5. What’s the difference from a Bloom filter?
    6. What is conservative update?
11. References

The count-min sketch solves that problem with a small matrix and several hash functions: it trades absolute certainty for an estimate with bounded error and constant memory. It’s the same idea behind how Redis, Apache Flink, and network anomaly detection systems count events at scale without memory growing with the number of distinct keys.

TL;DR

• You’ll understand how the count-min sketch estimates frequencies without storing each individual event.
• You’ll be able to calculate the matrix’s width and depth based on the error you’re willing to tolerate.
• You’ll implement a basic count-min sketch in JavaScript in under 30 lines.
• You’ll know how to use CMS.INITBYDIM, CMS.INCRBY, and CMS.QUERY from the RedisBloom module in Redis.
• You’ll be able to tell when a count-min sketch is preferable to a Bloom filter or a HyperLogLog.
• You’ll learn about ‘conservative update,’ the technique that reduces count overestimation.
• You’ll identify the most common mistakes when choosing the epsilon and delta parameters.

What the count-min sketch is and why it matters

An exact hash map stores one entry per distinct key: if there are ten million unique IPs, memory grows with those ten million entries. The count-min sketch breaks that relationship: its size depends only on the error you tolerate, not on how many distinct keys appear in the stream.

Graham Cormode and S. Muthukrishnan published the algorithm in 2005 in response to a concrete problem: counting frequencies in data streams too large to fit in memory. Since then it has become a standard piece in streaming systems, analytical databases, and network monitoring.

This channel already covered other probabilistic structures with different purposes: Bloom filters answer ‘does this element exist,’ HyperLogLog answers ‘how many distinct elements are there.’ The count-min sketch answers a third question, ‘how many times did this element appear,’ and that difference matters because each one solves a problem the other two can’t.

How it works internally

The structure is a matrix of w columns by d rows, all initialized to zero. Each row has an associated independent hash function that maps any element to a column within that row.

To increment an element, the algorithm computes its d positions (one per row) and adds the count to each of those cells. To query the estimated frequency, it recomputes those same d positions and returns the minimum of the values found.

The minimum matters because each row can suffer collisions: two distinct elements that land in the same cell inflate its value. Taking the minimum across several independent rows reduces that noise. The mathematical guarantee is that the estimate is never lower than the real count, but it can be higher.

Cormode and Muthukrishnan showed that with a width of w = ⌈e/ε⌉ and a depth of d = ⌈ln(1/δ)⌉ (where e is Euler’s number), the estimate stays within an error of ε·N relative to the real count, with probability of at least 1-δ, where N is the total sum of all counts.

flowchart TD
    A["Event: IP 203.0.113.7"] --> B["Hash 1"]
    A --> C["Hash 2"]
    A --> D["Hash 3"]
    B --> E["Row 1, column h1"]
    C --> F["Row 2, column h2"]
    D --> G["Row 3, column h3"]
    subgraph Matrix
    E
    F
    G
    end

Practical examples with code

The first example implements a count-min sketch from scratch, with no dependencies, to see the internal mechanics without the layer of an external engine.

class CountMinSketch {
  constructor(width, depth) {
    this.width = width;
    this.depth = depth;
    this.matrix = Array.from({ length: depth }, () => new Uint32Array(width));
    this.seeds = Array.from({ length: depth }, (_, i) => i * 2654435761);
  }

  hash(item, seed) {
    let h = seed;
    for (let i = 0; i < item.length; i++) {
      h = (h * 31 + item.charCodeAt(i)) >>> 0;
    }
    return h % this.width;
  }

  add(item, count = 1) {
    for (let row = 0; row < this.depth; row++) {
      const col = this.hash(item, this.seeds[row]);
      this.matrix[row][col] += count;
    }
  }

  estimate(item) {
    let min = Infinity;
    for (let row = 0; row < this.depth; row++) {
      const col = this.hash(item, this.seeds[row]);
      min = Math.min(min, this.matrix[row][col]);
    }
    return min;
  }
}

const cms = new CountMinSketch(2000, 5);
cms.add("203.0.113.7");
cms.add("203.0.113.7");
cms.add("198.51.100.23");
console.log(cms.estimate("203.0.113.7")); // 2, unless there's a collision

Each call to add increments five cells (one per row); estimate recomputes those same five positions and returns the smallest one. With w=2000 and d=5, two distinct IPs rarely collide across all five rows at once.

The second example uses the RedisBloom module, which exposes the count-min sketch as native Redis commands instead of reimplementing it in the application.

redis-cli CMS.INITBYDIM ip_counter 2000 5
redis-cli CMS.INCRBY ip_counter 203.0.113.7 1
redis-cli CMS.QUERY ip_counter 203.0.113.7

The first command creates the matrix with a width of 2000 and a depth of 5. The second increments the counter associated with that IP. The third returns the current estimate: in this example, 1.

const Redis = require("ioredis");
const redis = new Redis();

await redis.call("CMS.INITBYDIM", "ip_counter", 2000, 5);
await redis.call("CMS.INCRBY", "ip_counter", "203.0.113.7", 1);
const estimado = await redis.call("CMS.QUERY", "ip_counter", "203.0.113.7");
console.log(estimado); // ["1"]

This version delegates the matrix and hashing to Redis, which allows sharing the same sketch across multiple processes without coordinating them manually.

sequenceDiagram
    participant C as Client
    participant R as Redis
    C->>R: CMS.INCRBY ip_counter 203.0.113.7 1
    R-->>C: OK
    C->>R: CMS.QUERY ip_counter 203.0.113.7
    R-->>C: approximate estimate
    Note over C,R: the estimate is never lower than the real count

How to get started step by step

To try it today without installing anything on your system, spin up Redis Stack in Docker:

docker run -d --name redis-stack -p 6379:6379 redis/redis-stack:latest

With the container running, create the sketch and try the three basic commands:

redis-cli CMS.INITBYDIM visitas_por_pagina 2000 5
redis-cli CMS.INCRBY visitas_por_pagina /blog/count-min-sketch 1
redis-cli CMS.QUERY visitas_por_pagina /blog/count-min-sketch

To confirm the structure is active and has the expected parameters, use CMS.INFO, which returns the width, depth, and total sum of recorded counts:

redis-cli CMS.INFO visitas_por_pagina
# 1) width
# 2) (integer) 2000
# 3) depth
# 4) (integer) 5
# 5) count
# 6) (integer) 1

If the width or depth don’t match what you expected, the sketch was created with different parameters and needs to be recreated: it can’t be resized once initialized.

Real-world use cases

Detecting heavy hitters in network traffic is the classic case: identifying which IPs or which flows account for the bulk of the traffic without maintaining a complete flow table, something unfeasible when there are millions of simultaneous connections.

Twitter used an equivalent structure in its Algebird library to count occurrences of hashtags and terms in tweet streams, where storing an exact counter for every distinct word would have been impractical at that scale.

Analytical database engines use similar sketches to estimate a column’s selectivity before choosing an execution plan, without needing to scan the entire table. Projects like Apache DataSketches bundle the count-min sketch alongside other probabilistic structures for large-scale data pipelines.

💡 Tip: if your goal is to limit requests per user (rate limiting), a count-min sketch with a time window (resetting the matrix at regular intervals) usually consumes far less memory than an exact per-user counter.

Common mistakes and best practices

The most common mistake is treating the estimate as an exact number. The count-min sketch never underestimates, but it can overestimate, so it’s not suited for decisions where a false positive from overcounting is unacceptable, like exact per-event billing.

Another mistake is choosing an arbitrary width or depth. If the tolerated error ε is very small, the width w grows proportionally, and if the failure probability δ is very demanding, the depth d grows with it: it’s best to calculate both values based on the actual memory budget available, not guess them.

Highly skewed distributions (a few elements with enormous counts, the rest with low counts) suffer the most: an element with millions of occurrences can inflate the estimate of elements that collide in its same cell. Increasing the depth or applying conservative update mitigates that effect.

⚠️ Heads up: a basic count-min sketch doesn’t reliably support removing or decrementing elements; if your use case needs that, look at the Count Sketch variant before forcing the basic structure.

Comparison with alternatives

Structure	What it answers	Memory	When to use it
Exact hash map	Exact frequency	Grows with distinct keys	Few elements or abundant memory
Bloom filter	Does the element exist?	Fixed (bits)	Checking membership, not frequency
HyperLogLog	How many distinct elements are there?	Fixed (a few KB)	Approximate cardinality (COUNT DISTINCT)
Count-Min Sketch	How many times did it appear?	Fixed (w × d)	Approximate frequencies in massive streams
Count Sketch	Frequency with less bias	Fixed, similar to CMS	When systematic overestimation is a problem

Going deeper: conservative update and advanced variants

Conservative update is a simple but effective optimization: instead of adding the full count to the d cells, first calculate what the new minimum value among those cells would be, and raise each one only up to that value, never beyond. This reduces accumulated overestimation without changing the query logic.

The Count Sketch variant adds a random sign (+1 or -1) for each hash function, and on query returns the median instead of the minimum. The result is an estimator without systematic bias, although unlike the count-min sketch, it can underestimate the real count.

When the problem is identifying the k most frequent elements (top-k) instead of estimating individual frequencies, the Misra-Gries Space-Saving algorithm tends to be more accurate with similar memory, because it explicitly keeps track of the heaviest candidates instead of a generic matrix.

A key property for distributed systems is mergeability: two count-min sketches with the same width, depth, and hash functions can be combined by adding their matrices cell by cell. This allows each node in a cluster to count its portion of the stream separately and merge the results at the end, without prior coordination.

flowchart TD
    Q["What do you need to know?"] --> M["Does the element exist?"]
    Q --> D["How many distinct ones are there?"]
    Q --> F["How many times did it appear?"]
    M --> BF["Bloom filter"]
    D --> HLL["HyperLogLog"]
    F --> CMS["Count-Min Sketch"]

📖 Summary on Telegram: View summary

Your next step: spin up Redis Stack with this article’s Docker command, run CMS.INCRBY over a real log file, and compare it against an exact count with awk or uniq -c to see the margin of error in practice.

Frequently Asked Questions

Can the count-min sketch give a result lower than the real count?

No. The structure can only overestimate, never underestimate, because it takes the minimum across several rows that only add positive values.

How do I choose the matrix’s width and depth?

The width w is calculated as ⌈e/ε⌉ and the depth d as ⌈ln(1/δ)⌉, where ε is the tolerated error and δ is the accepted failure probability. A smaller error requires more width; a lower failure probability requires more rows.

Can a count-min sketch be merged with another one?

Yes, as long as both use the same width, depth, and hash functions. Merging them means adding their matrices cell by cell, which makes it ideal for counts distributed across several nodes.

Can it count elements that I later want to remove?

The basic version doesn’t reliably support decrements. That’s what the Count Sketch is for, a variant with random signs that allows unbiased estimates, though it can underestimate.

What’s the difference from a Bloom filter?

A Bloom filter answers whether an element exists or not; the count-min sketch answers how many times it appeared. They solve different questions and are often combined in the same system.

What is conservative update?

It’s an optimization where, when incrementing an element, each cell only rises to the new minimum value necessary instead of adding the full count, which reduces accumulated overestimation.

References

• Wikipedia: Count-min sketch: formal description of the algorithm, original authors, and mathematical guarantees.
• GitHub: RedisBloom: open source implementation of the module that exposes CMS.INITBYDIM, CMS.INCRBY, and CMS.QUERY in Redis.
• Apache DataSketches: library of probabilistic structures, including the count-min sketch, used in large-scale data pipelines.
• Redis: official documentation for the project and its probabilistic data structure modules.

📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Imagen destacada: Foto de Logan Voss en Unsplash