Count-min sketches: bounded-memory event estimates

Operational case

A compact four-row, 47-column sketch records bay-hot seven times and gate-open three times. Their estimates print 7 and 3 for this particular state; another event code can collide and return a positive estimate even if it was never recorded. Increasing width lowers collision pressure at a memory cost. Increasing depth takes more updates and hash work, while a minimum across rows helps avoid a collision in every row. The simple API rejects zero or negative amounts, so subtraction and deletion are outside its guarantee.

Working Python program

"""Deterministic row hashes for nonnegative approximate frequency counts."""

import hashlib


class EventCountSketch:
    def __init__(self, width, depth):
        if width < 2 or depth < 1:
            raise ValueError("positive depth and width at least two required")
        self.width = width
        self.depth = depth
        self.counters = [[0] * width for _ in range(depth)]

    def _column(self, event_code, row):
        payload = event_code.encode("utf-8")
        digest = hashlib.blake2b(payload, digest_size=8, person=row.to_bytes(8, "big")).digest()
        return int.from_bytes(digest, "big") % self.width

    def record(self, event_code, amount=1):
        if not isinstance(event_code, str) or not event_code:
            raise ValueError("nonempty event code required")
        if not isinstance(amount, int) or amount <= 0:
            raise ValueError("positive integer amount required")
        for row in range(self.depth):
            self.counters[row][self._column(event_code, row)] += amount

    def estimate(self, event_code):
        if not isinstance(event_code, str) or not event_code:
            raise ValueError("nonempty event code required")
        return min(self.counters[row][self._column(event_code, row)] for row in range(self.depth))


frequency = EventCountSketch(width=47, depth=4)
frequency.record("bay-hot", 7)
frequency.record("gate-open", 3)
print(frequency.estimate("bay-hot"))
print(frequency.estimate("gate-open"))

Output

7
3

Time, space, and tradeoff

With D rows and W columns, the counter matrix uses O(DW) space independent of the number of distinct event codes. Record and estimate perform D hash computations over a code of length K, costing O(DK) time here, plus O(D) counter operations. Initialization touches O(DW) counters. Exact counts would require a separate map, which may grow with distinct keys; this sketch trades accuracy for fixed memory. Overflow is limited only by Python integer memory in this implementation. Practical deployments must choose width, depth, hash family, counter representation, merge compatibility, and an error policy from their workload rather than assuming the sample's exact printed estimates generalize.

Common Mistakes

• Do not interpret a nonzero estimate as proof the key was recorded.
• Do not subtract counts from this positive-only sketch and keep the no-underestimate claim.
• Do not claim a formal probability bound from arbitrary deterministic row hashes.
• Do not combine sketches with different dimensions or hash conventions as if their cells aligned.

Connected lessons

• Hashing
• Data Structures
• Bloom filters: reject absent keys without claiming exact membership
• Hash maps: keyed lookup with collision and load costs
• Sparse sets: constant-time membership for bounded integer IDs
• Projects
• Quizzes

Apply this structure in the incident search project, then test the index decisions quiz.

Misra–Gries: find frequent-item candidates in one pass adds a bounded stream contract.

Space-Saving: ranked candidates with count bounds adds a bounded stream contract.

Frequency admission: compare an arrival with an eviction victim extends the retention comparison.

Count Sketch: estimate signed incident frequencies with row medians adds a related structure with a different operation boundary.