Home/Questions/Q 3530
Next
In Process

RTSALL Latest Articles

abderahman
Asked: 2026-09-11T09:52:40-05:00 In: ,

How does a Count-Min Sketch estimate heavy-hitter item frequencies under bounded RAM?

We are building a DDoS mitigation filter monitoring billions of network packets per minute. We need to count the frequency of each source IP address in real-time to detect anomalous spikes.

Using a standard hash map of counters would require tens of gigabytes of RAM and quickly run out of memory. We are looking into the Count-Min Sketch algorithm. How does it work mathematically, why does it never underestimate frequency, and how do we choose the optimal table width and depth?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    The Count-Min Sketch (CMS) is the gold-standard probabilistic algorithm for tracking frequencies in massive, unconstrained data streams (used extensively in Apache Spark, network switches, and Google search analytics).

    1. Architectural Layout

    A Count-Min Sketch consists of a 2D matrix of integer counters with d rows (depth) and w columns (width), paired with d independent hash functions:

    Row 0: [0, 0, 0, 0, ..., 0]  <--- Hash Function h_0(x)
Row 1: [0, 0, 0, 0, ..., 0]  <--- Hash Function h_1(x)
...
Row d: [0, 0, 0, 0, ..., 0]  <--- Hash Function h_d(x)

    2. The Operations

    A. Add Item `x` (Increment):

    For each row i from 0 to d - 1, compute column index col = h_i(x) % w, and increment that counter:

    table[i][h_i(x) % w] += 1

    B. Query Frequency of `x` (Point Query):

    Because multiple items might collide at the same counter bucket, hash collisions can only increase a counter, never decrease it!

    Therefore, to get the best possible estimate, we take the MINIMUM across all d rows:

    estimated_count = min(table[i][h_i(x) % w] for i in range(d))

    The Golden Invariant: A Count-Min Sketch NEVER underestimates the true count! True frequency is always $le$ estimated frequency.

    3. Mathematical Dimensioning Rules

    If you want an error bound within $epsilon cdot N$ with confidence probability $1 – delta$:

    • Width: $w = lceil rac{e}{epsilon}
      ceil pprox lceil rac{2.718}{epsilon}
      ceil$
    • Depth: $d = lceil ln( rac{1}{delta})
      ceil$

    For example, to guarantee $le 0.1%$ error with $99%$ confidence, you need only $w = 2718$ columns and $d = 5$ rows. That’s just 13,590 integer counters (~54 KB of RAM) to monitor billions of events!

    Clean Python 3.12 Implementation

    import math
import mmh3 # MurmurHash3

class CountMinSketch:
    def __init__(self, epsilon: float = 0.001, delta: float = 0.01):
        self.w = int(math.ceil(math.e / epsilon))
        self.d = int(math.ceil(math.log(1.0 / delta)))
        self.table = [[0] * self.w for _ in range(self.d)]

    def add(self, item: str, count: int = 1) -> None:
        """Increments counter for item across all d hash functions."""
        for row in range(self.d):
            col = mmh3.hash(item, row, signed=False) % self.w
            self.table[row][col] += count

    def query(self, item: str) -> int:
        """Returns minimum count across all d rows (never underestimates)."""
        return min(
            self.table[row][mmh3.hash(item, row, signed=False) % self.w]
            for row in range(self.d)
        )

    Complexity Breakdown

    • Add Time: O(d) — strictly constant time ($5$ hash calculations and memory writes).
    • Query Time: O(d) — strictly constant time ($5$ lookups).
    • Memory Footprint: O(w * d) — strictly fixed in size. Bounded memory that never grows regardless of how many billions of packets arrive!
    • 0
  2. Anonymous
    Begginer

    Here is a modern C++ implementation of the Count-Min Sketch for streaming frequency tracking under strict memory caps.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdint>

class CountMinSketch {
    int w; // Width (columns)
    int d; // Depth (rows)
    std::vector<std::vector<uint32_t>> table;

    uint32_t hash(const std::string& str, int seed) const {
        // FNV-1a 32-bit hash with seed variation
        uint32_t h = 2166136261u ^ seed;
        for (char c : str) {
            h ^= static_cast<uint8_t>(c);
            h *= 16777619u;
        }
        return h % w;
    }

public:
    CountMinSketch(double epsilon = 0.001, double delta = 0.01) {
        w = static_cast<int>(std::ceil(2.71828 / epsilon));
        d = static_cast<int>(std::ceil(std::log(1.0 / delta)));
        table.assign(d, std::vector<uint32_t>(w, 0));
    }

    void add(const std::string& item, uint32_t count = 1) {
        for (int r = 0; r < d; ++r) {
            uint32_t col = hash(item, r * 31 + 7);
            table[r][col] += count;
        }
    }

    uint32_t query(const std::string& item) const {
        uint32_t min_val = UINT32_MAX;
        for (int r = 0; r < d; ++r) {
            uint32_t col = hash(item, r * 31 + 7);
            min_val = std::min(min_val, table[r][col]);
        }
        return min_val;
    }
};

int main() {
    CountMinSketch cms(0.01, 0.01);
    cms.add("192.168.1.100", 500);
    cms.add("10.0.0.1", 20);

    std::cout << "Estimated frequency 192.168.1.100: " << cms.query("192.168.1.100") << "n";
    std::cout << "Estimated frequency 10.0.0.1:     " << cms.query("10.0.0.1") << "n";
    return 0;
}

    Guarantees: Strictly bounded RAM overhead and zero underestimations.

    • 0