System-Scale & Probabilistic Structures

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!