Count-Min Sketching for approximate frequency estimation

Frequency analysis is simple when every event can be retained in a dictionary. The difficulty appears when identifiers arrive faster than they can be stored, or when millions of distinct keys make exact counting expensive. A Count-Min Sketch compresses those totals into a fixed-size table, accepting controlled overestimation instead of preserving every item.

It maintains several independent hash tables and returns the smallest count found for a key. Every update reaches one counter in each table, so the estimate is never below the true count. Collisions can inflate a result, but the structure remains useful when approximate answers are needed quickly.

The following implementation covers the core algorithm, parameter selection, Python and NumPy versions, and a compact C approach. It also considers Australian data streams and privacy obligations, where an approximate counter can be valuable without becoming the authoritative record.

Core mechanics

A sketch contains depth rows, each with width counters. Row i uses its own hash function to map a key to a column. An update increments that column in every row, while an estimate takes the minimum of the corresponding counters.

update(item):
    for each row:
        column = hash[row](item) modulo width
        counters[row][column] += 1

estimate(item):
    best = infinity
    for each row:
        column = hash[row](item) modulo width
        best = minimum(best, counters[row][column])
    return best

A collision occurs when unrelated keys select the same column. Their counters are combined, making the estimate too high. Using several rows reduces the chance that two keys collide everywhere, and taking the minimum discards the most obviously inflated values.

The sketch consumes a sequence of events rather than a connected structure. For graph-shaped data, path order and neighbouring nodes affect the algorithm, as explained in the graph traversal guide. Frequency estimation has no comparable path requirement because each update can be processed independently.

Choosing width, depth, and confidence

Two parameters determine the sketch’s behaviour. Width controls the additive error, while depth controls the probability that all hash functions collide on a frequently updated key. For a stream containing N events, a common error target is:

width = ceiling(e / epsilon)
depth = ceiling(log(1 / delta))

Here, epsilon is the permitted error as a fraction of the total stream count, and delta is the probability of exceeding that target. With suitable hash functions, every estimate stays within epsilon × N of its true count with probability at least 1 - delta.

For one million events and a one per cent error target, a width of roughly 272 is sufficient. A confidence level of 99 per cent requires five rows, giving a compact table of 1,360 counters. The sketch may report 10,010 occurrences when the true count is 10,000, which is suitable for trend detection but not financial reconciliation.

Widening the table lowers the expected error without increasing update time. Adding rows raises confidence and query work while adding only width counters per row. Hash quality also matters: stable, well-distributed functions provide more reliable estimates than short or predictably seeded hashes.

A production-minded Python implementation

Python makes the sketch straightforward to integrate into a service. The implementation below uses BLAKE2 with independent salts, avoiding the process-randomised behaviour of Python’s built-in hash function.

import hashlib
import random


class CountMinSketch:
    def __init__(self, width=1024, depth=5, seed=0):
        if width < 1 or depth < 1:
            raise ValueError("width and depth must be positive")

        self.width = width
        self.depth = depth
        self.counters = [[0] * width for _ in range(depth)]

        generator = random.Random(seed)
        self.salts = [
            generator.randrange(1 << 63) for _ in range(depth)
        ]

    def _positions(self, key):
        if isinstance(key, bytes):
            payload = key
        else:
            payload = str(key).encode("utf-8")

        for salt in self.salts:
            digest = hashlib.blake2b(
                payload,
                digest_size=8,
                salt=salt.to_bytes(8, "little"),
            ).digest()
            yield int.from_bytes(digest, "little") % self.width

    def add(self, key, amount=1):
        if not isinstance(amount, int) or amount < 0:
            raise ValueError("amount must be a non-negative integer")

        for row, column in zip(self.counters, self._positions(key)):
            row[column] += amount

    def estimate(self, key):
        return min(
            row[column]
            for row, column in zip(self.counters, self._positions(key))
        )

The seed makes test runs reproducible, while different salts reduce correlation between rows. It does not remove hash collisions, so returned values should still be treated as estimates. A key absent from the stream can also have a positive estimate if its hashed positions overlap active counters.

Keys need a consistent representation. Converting integers with str distinguishes them from equivalent strings, while byte identifiers remain unchanged. Applications should also track the total number of updates separately, since that total provides context for interpreting relative error.

Vectorising updates with NumPy

A two-dimensional NumPy array can hold the same counter table in contiguous memory. The NumPy broadcasting operations guide explains the indexing and broadcasting techniques useful for this arrangement.

import numpy as np


class VectorCountMinSketch:
    def __init__(self, width=1024, depth=5, seed=0):
        self.width = width
        self.depth = depth
        self.table = np.zeros((depth, width), dtype=np.int64)
        self.inner = CountMinSketch(width, depth, seed)

    def add(self, key, amount=1):
        rows = np.arange(self.depth)
        columns = np.fromiter(
            self.inner._positions(key),
            dtype=np.int64,
            count=self.depth,
        )
        np.add.at(self.table, (rows, columns), amount)

    def estimate(self, key):
        rows = np.arange(self.depth)
        columns = np.fromiter(
            self.inner._positions(key),
            dtype=np.int64,
            count=self.depth,
        )
        return int(self.table[rows, columns].min())

np.add.at performs the repeated indexed updates correctly, while advanced indexing gathers each row’s selected counter for the minimum. This representation is particularly effective when the same sketch processes many batches, because NumPy performs the arithmetic in compiled code.

The array version still performs one hash operation per row. It becomes most valuable when updates are grouped into arrays, counters occupy predictable memory, or several sketches are evaluated together. For sparse event streams, a Python implementation may consume less memory and complete sooner.

Compact counters and C performance

Python integers carry allocation and reference overhead, which can dominate a large counter table. Packed native counters reduce that cost and can suit high-throughput ingestion services. For teams maintaining native software, the C programming guide provides a foundation for implementing the same data structure with a flat array.

#include <stddef.h>
#include <stdint.h>

static uint64_t cms_hash(const unsigned char *key, size_t length,
                          uint64_t seed) {
    uint64_t hash = 14695981039346656037ULL ^ seed;

    while (length--) {
        hash ^= *key++;
        hash *= 1099511628211ULL;
    }
    return hash;
}

static uint64_t cms_estimate(const uint64_t *table, size_t width,
                             size_t depth, const uint64_t *seeds,
                             const unsigned char *key, size_t length) {
    uint64_t best = UINT64_MAX;

    for (size_t row = 0; row < depth; ++row) {
        size_t column = cms_hash(key, length, seeds[row]) % width;
        uint64_t value = table[row * width + column];
        if (value < best) {
            best = value;
        }
    }
    return best;
}

The flat layout makes memory use predictable: width × depth × sizeof(uint64_t) bytes, excluding hash state. An update follows the same row-and-column path as the Python version, so most native implementations execute in constant time per row.

The included hash is compact and useful for demonstration, but production services should benchmark a stronger hash suited to their workload. Counters also need overflow checks or a safely bounded lifetime. Unsigned wraparound is defined in C, yet it can silently destroy the error guarantees.

Australian deployment considerations

Transport operators in Sydney and Melbourne already generate large tap streams through Opal and Myki systems. Where data-sharing agreements permit, an analytics service could count station codes, route identifiers, or service periods instead of retaining individual card numbers. The sketch can identify busy routes or unusual activity while aggregated operational records remain the source of truth.

Australian retailers such as Woolworths and Coles process everyday shopping events through loyalty programmes, online stores, and click-and-collect services. Counting product identifiers can reveal popular products, repeated searches, or demand patterns without retaining every basket. Inventory, pricing, and financial totals should still come from transactional systems because approximation is unsuitable for stock deductions or customer billing.

Privacy obligations depend on the data being processed. For covered organisations, the Privacy Act 1988 and Australian Privacy Principles may require lawful collection, limited use, security, and appropriate handling of personal information. A sketch does not automatically make data anonymous, particularly when identifiers can be linked back to people. Commercial electronic messages are also governed by the Spam Act 2003 and guidance from ACMA, with consent, sender identification, and unsubscribe requirements remaining separate from frequency estimation.

Operational safeguards should include separate sketches for time windows, tracked event totals, and comparisons against sampled exact counts. Individual events cannot be safely removed from a conventional sketch because decrements can affect collided counters. Used within these boundaries, the sketch becomes a fast layer for heavy-hitter detection and anomaly screening while exact systems retain authority over regulated records.