Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Count Sketch: estimate signed incident frequencies with row medians

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A Count Sketch uses several counter rows. For a key, each row chooses a bucket and a sign; an integer update adds the signed delta to that cell. A query multiplies each touched cell by the same sign and takes the median across rows. Unrelated keys can add positive or negative noise, so an estimate may lie above or below the true value. The example uses stable digest-derived bucket and sign choices, five rows, and twenty-nine columns to make its trace repeatable. It permits positive and negative updates, unlike a count-min summary whose one-sided overestimate contract assumes nonnegative increments. The code does not retain the exact key frequencies, discover heavy hitters, or assert a formal error probability for this fixed hash construction.

Operational case

A scanner incident receives 47 observations and later an adjustment of minus eight. The sketch estimates 39 in the displayed trace; dock estimates 19 and an unseen key estimates zero under these collisions. Those values are particular outcomes, not universal exactness guarantees. A different stream can collide with a queried key in enough rows to move the median. Sending a negative update without a corresponding business event can produce a negative estimate; the structure stores signed algebraic changes rather than enforcing an inventory policy. The same key must use the same bucket and sign in every update and query.

Working Python program

python
import hashlib
from statistics import median


class SignedIncidentSketch:
    def __init__(self, width=31, rows=5):
        if width <= 0 or rows <= 0 or rows % 2 == 0:
            raise ValueError("positive width and odd positive row count required")
        self.width = width
        self.rows = rows
        self.counters = [[0] * width for _ in range(rows)]

    def _probe(self, incident_key, row):
        payload = f"{row}\0{incident_key}".encode("utf-8")
        digest = hashlib.blake2b(payload, digest_size=16).digest()
        bucket = int.from_bytes(digest[:8], "big") % self.width
        sign = 1 if digest[8] & 1 else -1
        return bucket, sign

    def adjust(self, incident_key, delta):
        if not isinstance(incident_key, str) or not isinstance(delta, int):
            raise TypeError("string key and integer delta required")
        for row in range(self.rows):
            bucket, sign = self._probe(incident_key, row)
            self.counters[row][bucket] += sign * delta

    def estimate(self, incident_key):
        if not isinstance(incident_key, str):
            raise TypeError("string key required")
        readings = []
        for row in range(self.rows):
            bucket, sign = self._probe(incident_key, row)
            readings.append(sign * self.counters[row][bucket])
        return median(readings)


incident_sketch = SignedIncidentSketch(width=29, rows=5)
for key, change in (("scanner", 47), ("dock", 19), ("invoice", 29), ("scanner", -8)):
    incident_sketch.adjust(key, change)
print("scanner estimate:", incident_sketch.estimate("scanner"))
print("dock estimate:", incident_sketch.estimate("dock"))
print("unseen estimate:", incident_sketch.estimate("missing"))

Output

Output
scanner estimate: 39
dock estimate: 19
unseen estimate: 0

Time, space, and tradeoff

With R rows and W columns, each update and point estimate performs O(R) hash probes; storage is O(RW) integer counters. Median sorting costs O(R log R) in this Python implementation, so the full estimate is O(R log R), although a selection algorithm could avoid sorting. The sketch does not store distinct keys after updates. Its approximation quality depends on width, rows, hash behavior, and the stream's frequency energy; this example makes no strict confidence claim. A count-min sketch has a different one-sided nonnegative update model, while exact dictionaries use space proportional to distinct keys.

Common Mistakes

  • Do not call a signed median estimate a guaranteed upper bound.
  • Do not change row hashes between an update and its query.
  • Do not assume an unseen key always estimates zero after other keys collide.
  • Do not mistake the sketch for an exact heavy-hitter key inventory.

Connected lessons

Compare this operation boundary with Exponential histograms: estimate failures in a recent event window, Range-mode indexes: combine complete-block modes with fringe candidates, then complete the structure audit and decision quiz.

data structures
range-query-structures
Storage details