How to Build a Count-Min Sketch in Python to Estimate Event Frequencies Without Storing Every Item

Suppose you run a busy API gateway and want to answer a simple question: how many times has each endpoint been hit in the last hour? Keeping an exact count is easy in principle, just increment a counter in a dictionary every time a request comes in. The trouble is that the dictionary grows with the number of distinct endpoints (or IP addresses, or search terms, or product SKUs) you have ever seen, and on a system with millions of unique keys passing through, that dictionary can quietly become one of the biggest consumers of memory in the whole service.

A Count-Min Sketch is a probabilistic data structure that answers “roughly how many times has this happened?” using a small, fixed amount of memory that never grows, no matter how many distinct items pass through it. It trades perfect accuracy for that fixed footprint: its estimates are always at least as large as the true count, and usually very close to it, though not always exactly equal to it. In this tutorial you will build one from scratch in Python, using nothing but the standard library, and verify every claim this article makes against real measured output rather than taking it on faith.

This is a well-established, production-grade technique. Redis ships a Count-Min Sketch as one of its built-in probabilistic data types (the CMS.INCRBY and CMS.QUERY commands), and documents using it for problems like estimating daily sales volume per product without keeping a running total for every SKU that has ever sold a single unit. The algorithm itself was invented in 2003 by Graham Cormode and S. Muthu Muthukrishnan and described in their 2005 paper, and it belongs to the same family of tools as the Bloom filter and HyperLogLog, both of which this site has already covered as their own from-scratch tutorials.

What You Will Build

By the end of this tutorial you will have a working CountMinSketch class with add() and estimate() methods, and you will have personally measured:

• How much memory an exact frequency counter costs compared to a fixed-size sketch, on a realistic, heavily skewed stream
• Why the sketch’s estimates are only ever too high, never too low, and what that guarantee actually promises mathematically
• What happens to accuracy when the sketch is sized too small for its traffic, measured directly rather than assumed
• A real, reproducible bug: what breaks when the sketch’s internal hash functions are not truly independent of each other
• How to find the heaviest hitters in a stream without ever storing the full list of items
• Why merging two independently built sketches gives you the exact same result as building one sketch on the combined data

Prerequisites

• Python 3.10 or later. This tutorial was built and tested on Python 3.13.14, but every line is standard library only (hashlib, array, and math) and will run unchanged on any recent Python, on Windows, macOS, or Linux.
• Comfortable reading basic Python: functions, classes, list comprehensions, and dictionaries.
• Some familiarity with hash functions and the idea of a hash collision helps, but this tutorial explains the relevant details as it goes.
• pytest is used for the optional automated test suite in the last step (pip install pytest if you want to run it).

Step 1: Feel the Problem an Exact Counter Runs Into

Before building anything clever, measure the cost of the obvious approach. Simulate a stream of API requests where a handful of endpoints are hit constantly and a long tail of endpoints are hit rarely, a pattern known as a Zipfian distribution: the item at rank r is sampled with a probability proportional to 1/r. This is the same shape real traffic tends to take, whether you are counting API endpoints, search queries, or product page views.

"""Step 1: the naive way to count event frequencies, and why it doesn't scale."""
import random
import sys
from collections import Counter

random.seed(42)

VOCAB_SIZE = 2000
STREAM_LEN = 300_000

items = [f"endpoint-{i}" for i in range(VOCAB_SIZE)]
weights = [1.0 / rank for rank in range(1, VOCAB_SIZE + 1)]
stream = random.choices(items, weights=weights, k=STREAM_LEN)

counts = Counter(stream)

shallow_bytes = sys.getsizeof(counts)
full_bytes = shallow_bytes + sum(sys.getsizeof(k) + sys.getsizeof(v) for k, v in counts.items())

print(f"Stream length:          {STREAM_LEN:,} events")
print(f"Distinct endpoints seen: {len(counts):,}")
print(f"Top 3 by true count:    {counts.most_common(3)}")
print(f"Counter object alone:   {shallow_bytes:,} bytes (getsizeof, shallow)")
print(f"Counter + all keys/values: {full_bytes:,} bytes = {full_bytes / 1024:.1f} KB")

Running this produces:

Stream length:          300,000 events
Distinct endpoints seen: 2,000
Top 3 by true count:    [('endpoint-0', 36874), ('endpoint-1', 18278), ('endpoint-2', 12059)]
Counter object alone:   51,984 bytes (getsizeof, shallow)
Counter + all keys/values: 214,874 bytes = 209.8 KB

With only 2,000 distinct endpoints, the exact Counter already costs about 210 KB once you count the string keys it holds pointers to (the shallow getsizeof figure alone is misleading for the same reason it was in the HyperLogLog tutorial: it only measures the dictionary’s own internal table, not the objects it points to). The key problem is not that 210 KB is large today, it is that this number grows linearly with the number of distinct items you have ever seen. Scale the vocabulary up to a few million unique visitor IDs or search phrases and the exact counter’s memory bill scales right along with it. A Count-Min Sketch sidesteps that entirely: its memory cost is fixed the moment you create it and never changes again, whether it sees 2,000 distinct items or 200 million.

Step 2: Build the Sketch From Scratch

The data structure itself is a two-dimensional table with depth rows and width columns. Each row has its own hash function. To record an event, hash it once per row to pick a column in that row, and increment the counter at that cell. To estimate an item’s count, hash it the same way in every row and take the minimum value found, not the average, not the sum, the minimum.

The Constructor and the Per-Row Hash

Start with the constructor and the per-row hashing helper:

import array
import hashlib
import math


class CountMinSketch:
    def __init__(self, width: int, depth: int, seed: int = 0):
        if width < 1 or depth < 1:
            raise ValueError("width and depth must each be at least 1")
        self.width = width
        self.depth = depth
        # Each row gets its own seed, so its hash function behaves like an
        # independent random function from every other row's.
        self.row_seeds = [f"{seed}-row{row}" for row in range(depth)]
        self.table = array.array("I", [0]) * (width * depth)
        self.total_count = 0

    def _column(self, item: str, row: int) -> int:
        digest = hashlib.sha256(f"{self.row_seeds[row]}:{item}".encode("utf-8")).digest()
        return int.from_bytes(digest[:8], "big") % self.width

Two design choices are worth calling out. First, the table is a single flat array.array("I", ...) rather than a list of Python lists. An array.array stores its values as fixed-width C-style unsigned integers instead of full Python integer objects, which is what makes its memory footprint honestly small (more on that in a moment). Second, every row gets its own seed string mixed into the hash input. That is not a cosmetic detail. Wikipedia’s own description of the algorithm is explicit that “the hash functions must be pairwise independent,” and Step 5 below reproduces exactly what goes wrong if you skip this.

Recording and Estimating

Now add the two operations that make the sketch useful:

    def add(self, item: str, count: int = 1) -> None:
        self.total_count += count
        for row in range(self.depth):
            col = self._column(item, row)
            self.table[row * self.width + col] += count

    def estimate(self, item: str) -> int:
        return min(
            self.table[row * self.width + self._column(item, row)]
            for row in range(self.depth)
        )

The reason to take the minimum across rows rather than, say, the average, is that hash collisions can only ever push a cell’s count up (two different items sharing a cell means that cell’s total is the sum of both items’ true counts). A collision can never push a count down. So the smallest of the depth independent readings is the one least likely to have been inflated by a collision, and it is provably never smaller than the item’s true count. Save both of the code blocks above into a file named cms.py before continuing, since every later step imports from it.

Try it on a handful of items you can check by hand:

"""Step 2: a tiny, hand-checkable worked example of add() and estimate()."""
from cms import CountMinSketch

sketch = CountMinSketch(width=10, depth=3, seed=1)

sketch.add("apple", 5)
sketch.add("banana", 2)
sketch.add("apple", 1)  # apple's true total is now 6

print("apple  ->", sketch.estimate("apple"), " (true count: 6)")
print("banana ->", sketch.estimate("banana"), " (true count: 2)")
print("cherry ->", sketch.estimate("cherry"), " (true count: 0, never added)")

apple  -> 6  (true count: 6)
banana -> 2  (true count: 2)
cherry -> 0  (true count: 0, never added)

With only 10 columns and 3 items, there happen to be no collisions in this particular run, so every estimate lands exactly on the true count. That will not stay true once the sketch is under real load, which is exactly what the next step measures.

Step 3: Measure Real Accuracy Against Exact Counts

The sketch’s size is not arbitrary. The classic Cormode and Muthukrishnan paper (via Wikipedia’s summary of it) gives a formula for choosing width and depth from two parameters you actually care about: an error tolerance epsilon and a confidence level expressed as delta.

def sized_for(epsilon: float, delta: float) -> tuple[int, int]:
    """w = ceil(e / epsilon), d = ceil(ln(1 / delta))."""
    width = math.ceil(math.e / epsilon)
    depth = math.ceil(math.log(1 / delta))
    return width, depth

Add this function to cms.py. The guarantee it targets is precise: with probability at least 1 - delta, every estimate is no more than epsilon * N higher than the true count, where N is the total number of events the sketch has seen. This is exactly the same idea Redis exposes through its CMS.INITBYPROB key error probability command, which lets you specify a target accuracy instead of raw table dimensions.

Run the same Zipfian stream from Step 1 through a properly sized sketch and check the guarantee against every single one of the 2,000 distinct items, not just a sample:

"""Step 3: measure real accuracy against exact counts, and verify the sketch's
core mathematical guarantee (never underestimates) holds for every item."""
import random
from collections import Counter

from cms import CountMinSketch, sized_for

random.seed(42)

VOCAB_SIZE = 2000
STREAM_LEN = 300_000

items = [f"endpoint-{i}" for i in range(VOCAB_SIZE)]
weights = [1.0 / rank for rank in range(1, VOCAB_SIZE + 1)]
stream = random.choices(items, weights=weights, k=STREAM_LEN)
exact = Counter(stream)

EPSILON = 0.001  # target additive error: within 0.1% of total stream size
DELTA = 0.01     # with 99% probability
width, depth = sized_for(EPSILON, DELTA)
print(f"sized_for(epsilon={EPSILON}, delta={DELTA}) -> width={width}, depth={depth}")

sketch = CountMinSketch(width=width, depth=depth, seed=7)
for event in stream:
    sketch.add(event)

error_bound = EPSILON * sketch.total_count
print(f"Stream size N = {sketch.total_count:,}, error bound (epsilon * N) = {error_bound:,.1f}")

never_underestimated = True
max_error = 0
worst_item = None
for item, true_count in exact.items():
    est = sketch.estimate(item)
    if est < true_count:
        never_underestimated = False
    error = est - true_count
    if error > max_error:
        max_error = error
        worst_item = (item, true_count, est)

print(f"Never underestimated any of {len(exact):,} items: {never_underestimated}")
print(f"Max additive error observed: {max_error} (bound was {error_bound:,.1f})")
print(f"Worst item: {worst_item}")

sized_for(epsilon=0.001, delta=0.01) -> width=2719, depth=5
Stream size N = 300,000, error bound (epsilon * N) = 300.0
Never underestimated any of 2,000 items: True
Max additive error observed: 64 (bound was 300.0)
Worst item: ('endpoint-602', 48, 112)

Every single one of the 2,000 items came back at or above its true count, and the worst overestimate (64) stayed well inside the theoretical bound of 300. Look closely at the “worst item,” though: endpoint-602 truly occurred 48 times, but the sketch reported 112, more than double. The absolute error is small in the context of a 300,000-event stream, but the relative error for that one rare item is huge. This is exactly the caveat Redis’s own documentation calls out: “results coming from a Count-Min sketch lower than a certain threshold… should be ignored and often even approximated to zero… it’s only useful for higher counts.” The sketch’s guarantee is an absolute bound on how much error it can introduce, not a promise that small counts are trustworthy in isolation.

It is also worth checking the actual memory this sized sketch uses, side by side with the naive counter from Step 1:

>>> import sys
>>> sys.getsizeof(sketch.table)
54460

54,460 bytes for the sketch’s table, against 214,874 bytes for the exact Counter holding the same 2,000 distinct keys, roughly 3.9 times smaller at this modest scale. That ratio is not the headline here, though. The headline is that 54,460 bytes is a fixed number: it depends only on width and depth, which you choose up front. Grow the vocabulary to 2 million distinct endpoints and the sketch’s memory does not move at all, while the exact counter’s memory grows right along with it.

Step 4: See What an Undersized Sketch Actually Costs You

The formula in Step 3 exists because guessing at width and depth is risky. Measure that risk directly by running the same stream through a sketch that is deliberately too small, the properly sized one from Step 3, and one that is generously oversized:

"""Step 4: what happens when the sketch is too small for the traffic it sees."""
def measure(width, depth, label):
    sketch = CountMinSketch(width=width, depth=depth, seed=7)
    for event in stream:
        sketch.add(event)
    errors = [sketch.estimate(item) - true for item, true in exact.items()]
    mean_error = sum(errors) / len(errors)
    max_error = max(errors)
    cells = width * depth
    print(f"{label:>28}: width={width:>5} depth={depth}  cells={cells:>7,}  "
          f"mean error={mean_error:6.2f}  max error={max_error:>6}")


measure(width=50, depth=3, label="undersized")
measure(width=2719, depth=5, label="sized_for(0.001, 0.01)")
measure(width=10000, depth=5, label="oversized")

                  undersized: width=   50 depth=3  cells=    150  mean error=2962.19  max error= 11942
      sized_for(0.001, 0.01): width= 2719 depth=5  cells= 13,595  mean error=  1.16  max error=    64
                   oversized: width=10000 depth=5  cells= 50,000  mean error=  0.00  max error=     0

With only 150 total cells for 2,000 distinct items, collisions are so dense that the mean error balloons to nearly 3,000, and the single worst item is overestimated by almost 12,000, more than its own true count in most cases. The properly sized sketch (13,595 cells) drops the mean error to about 1. In this particular run, generously oversizing to 50,000 cells happened to eliminate every measurable error entirely, though that is a property of how the collisions fell in this run rather than a hard guarantee: oversizing reduces the chance of a damaging collision, it does not eliminate the possibility outright.

Step 5: Reproduce a Real Bug, Rows That Are Not Actually Independent

Recall the requirement from Step 2: each row’s hash function needs to be independent of the others. It is an easy line to skip when you are refactoring, especially if you pull the seed from a single shared constant instead of deriving a fresh one per row. Build a deliberately broken version and see exactly what that costs:

The Bug: One Seed for Every Row

class BrokenSeedCountMinSketch(CountMinSketch):
    """Same as CountMinSketch, except every row reuses the exact same seed."""

    def __init__(self, width: int, depth: int, seed: int = 0):
        if width < 1 or depth < 1:
            raise ValueError("width and depth must each be at least 1")
        self.width = width
        self.depth = depth
        self.row_seeds = [str(seed)] * depth  # BUG: identical seed on every row
        self.table = array.array("I", [0]) * (width * depth)
        self.total_count = 0

Measuring the Damage

"""Step 5: reproduce a real bug, reusing the same seed on every row breaks
the sketch's independence requirement and quietly erases the benefit of
having multiple rows at all."""
honest = CountMinSketch(width=2719, depth=5, seed=7)
broken = BrokenSeedCountMinSketch(width=2719, depth=5, seed=7)
for event in stream:
    honest.add(event)
    broken.add(event)

rows_identical = all(
    list(broken.row_view(r)) == list(broken.row_view(0)) for r in range(5)
)
print(f"Every row identical in the broken sketch: {rows_identical}")

Every row identical in the broken sketch: True
Row 0 vs row 1, first 10 columns (honest):  [459, 269, 0, 0, 1073, 0, 0, 112, 0, 0]
                                            [0, 5339, 32, 69, 0, 46, 0, 1970, 46, 0]
Row 0 vs row 1, first 10 columns (broken):  [0, 0, 91, 107, 27, 0, 0, 0, 52, 0]
                                            [0, 0, 91, 107, 27, 0, 0, 0, 52, 0]

               configuration  mean error   max error
 honest (5 independent rows)       1.161         64
   broken (5 identical rows)      93.883      18319
 depth=1 (1 row, same width)      91.660      12059

The broken sketch’s five rows are not merely similar, they are byte-for-byte identical, confirmed directly rather than assumed. Taking the minimum across five copies of the exact same numbers buys you nothing, and the measured accuracy proves it: the broken sketch’s mean error (93.883) and max error (18,319) land in the same range as a sketch that only ever had one row to begin with (91.660 mean error, 12,059 max), roughly 80 times worse than the honestly independent version. Configuring depth=5 and getting the accuracy of depth=1 is exactly the kind of bug that will not throw an exception; it will just quietly make your accuracy numbers wrong in production while every test you write against a tiny, collision-free dataset keeps passing.

Step 6: Find the Heaviest Hitters Without Storing Every Item

A single frequency lookup is useful, but a common real question is “what are my top 5 most frequent items right now?” You can answer that by pairing the sketch with a small dictionary that tracks only the current best candidates, checking every arriving event’s freshly updated estimate against the smallest one currently tracked:

"""Step 6: track the top-K heaviest hitters using only the sketch and a small
dict of current candidates, verified against exact top-K."""
def track_heavy_hitters(stream, k, width, depth, seed):
    sketch = CountMinSketch(width=width, depth=depth, seed=seed)
    candidates: dict[str, int] = {}

    for event in stream:
        sketch.add(event)
        new_est = sketch.estimate(event)

        if event in candidates:
            candidates[event] = new_est
        elif len(candidates) < k:
            candidates[event] = new_est
        else:
            min_item = min(candidates, key=candidates.get)
            if new_est > candidates[min_item]:
                del candidates[min_item]
                candidates[event] = new_est

    return sketch, candidates


width, depth = sized_for(0.001, 0.01)
sketch, tracked = track_heavy_hitters(stream, k=5, width=width, depth=depth, seed=11)
exact_top_5 = {item for item, _ in exact.most_common(5)}
print(f"Exact top-5:    {exact.most_common(5)}")
print(f"Tracked top-5:  {sorted(tracked.items(), key=lambda p: -p[1])}")
print(f"Tracked set matches exact set: {set(tracked) == exact_top_5}")

Exact top-5:    [('endpoint-0', 36874), ('endpoint-1', 18278), ('endpoint-2', 12059), ('endpoint-3', 9098), ('endpoint-4', 7267)]
Tracked top-5:  [('endpoint-0', 36874), ('endpoint-1', 18278), ('endpoint-2', 12068), ('endpoint-3', 9098), ('endpoint-4', 7267)]
Tracked set matches exact set: True

The tracked set matches the true top 5 exactly, and the reported counts are within a few units of the real ones, which lines up with the accuracy already measured in Step 3. Notice this approach only ever holds k items in memory at once, no matter how many distinct items pass through the stream. This dict-plus-linear-scan approach is simple and correct, but scanning all k candidates for the minimum on every eviction is O(k) per event; Redis’s own command reference lists a dedicated TOPK.* family of commands (TOPK.ADD, TOPK.QUERY, and friends) built specifically for this heavy-hitters use case at larger scale, so treat this step as the mental model rather than the fastest possible implementation.

Step 7: Merge Two Sketches Into One

Because every cell in the table is a simple additive counter, two sketches built with identical width, depth, and row seeds can be combined by adding their tables together, cell by cell. Wikipedia describes this explicitly: “given two streams, constructing a sketch on each stream and summing the sketches yields the same result as concatenating the streams and constructing a sketch on the concatenated streams,” which is what makes the structure “mergeable and appropriate for use in distributed settings.” Add a merge() method to the class:

    def merge(self, other: "CountMinSketch") -> "CountMinSketch":
        if (self.width, self.depth, self.row_seeds) != (other.width, other.depth, other.row_seeds):
            raise ValueError("can only merge sketches with matching width/depth/seeds")
        merged = CountMinSketch(self.width, self.depth, seed=0)
        merged.row_seeds = self.row_seeds
        merged.table = array.array("I", (a + b for a, b in zip(self.table, other.table)))
        merged.total_count = self.total_count + other.total_count
        return merged

Split the stream in half, as if two separate edge servers each logged half the traffic, build one sketch per half, merge them, and compare the result against a sketch built directly on the full combined stream:

"""Step 7: verify merge() matches building one sketch on the combined stream."""
midpoint = len(stream) // 2
sketch_a = CountMinSketch(width=width, depth=depth, seed=7)
for event in stream[:midpoint]:
    sketch_a.add(event)
sketch_b = CountMinSketch(width=width, depth=depth, seed=7)
for event in stream[midpoint:]:
    sketch_b.add(event)
merged = sketch_a.merge(sketch_b)

combined_from_scratch = CountMinSketch(width=width, depth=depth, seed=7)
for event in stream:
    combined_from_scratch.add(event)

print(f"merged table equals combined-from-scratch table: {list(merged.table) == list(combined_from_scratch.table)}")
print(f"merge() matches build-from-scratch for every one of {len(exact):,} items: "
      f"{all(merged.estimate(i) == combined_from_scratch.estimate(i) for i in exact)}")

merged table equals combined-from-scratch table: True
merge() estimate matches build-from-scratch estimate for every one of 2,000 items: True

Not just close, identical: every one of the 2,000 items produced the exact same estimate whether you built one sketch from the full stream or merged two sketches built independently from each half. That is what makes this structure genuinely useful for a fleet of servers each tracking their own local traffic, then periodically combining their sketches into one global view without ever having to ship raw events between them.

Common Mistakes and Gotchas

• Treating small counts as trustworthy. As Step 3 showed directly, a true count of 48 came back as an estimate of 112, more than double, even though the absolute error stayed well within the theoretical bound. Redis’s own documentation is blunt about this: results below a certain threshold “should be ignored and often even approximated to zero.” Use the sketch to rank and compare, not to report an exact-looking number for a rarely seen item.
• Sharing one seed, or one hash function, across every row. Step 5 measured this precisely: it degrades a 5-row sketch to the accuracy of a 1-row sketch, roughly 80 times worse mean error in that test, with no exception or warning to tell you something is wrong.
• Reading the sketch before recording the current event. If your heavy-hitters tracker queries estimate() before calling add() for the same event, every reported number comes back exactly one lower than it should, since the query reflects the state before this occurrence was recorded. Tested directly against the tracker from Step 6, this ordering mistake left the tracked top-5 set unchanged (every stored value was uniformly one less, and uniform shifts do not change which value is smallest), but it is still a real, silent off-by-one in every displayed count, the kind of thing that matters the moment downstream code checks estimate(x) >= threshold.
• Assuming a returned zero always means “never seen.” A zero from estimate() does mean the item was never added (the structure never underestimates, so a zero rules out any prior occurrence), but a small nonzero estimate does not reliably distinguish “seen once” from “seen zero times but unlucky enough to land in a cell with some collision traffic,” unless every relevant row happens to be collision-free for that item.
• Merging sketches built with different dimensions. merge() raises ValueError if width, depth, or the row seeds do not match exactly between the two sketches, on purpose. Adding mismatched tables cell by cell would silently produce numbers that do not correspond to any real count.

Step 8: Automated Tests

Wrap the properties verified by hand above into a small pytest suite, so they stay verified the next time this code changes:

"""test_cms.py"""
import random
from collections import Counter

import pytest

from cms import BrokenSeedCountMinSketch, CountMinSketch, sized_for


def test_never_underestimates():
    random.seed(0)
    items = [f"item-{i}" for i in range(500)]
    weights = [1.0 / r for r in range(1, 501)]
    stream = random.choices(items, weights=weights, k=50_000)
    exact = Counter(stream)

    sketch = CountMinSketch(width=500, depth=4, seed=3)
    for event in stream:
        sketch.add(event)

    for item, true_count in exact.items():
        assert sketch.estimate(item) >= true_count


def test_shared_seed_breaks_row_independence():
    broken = BrokenSeedCountMinSketch(width=200, depth=5, seed=42)
    broken.add("x", 3)
    broken.add("y", 7)
    rows = [list(broken.row_view(r)) for r in range(5)]
    assert all(row == rows[0] for row in rows)


def test_merge_matches_build_from_scratch():
    random.seed(2)
    items = [f"item-{i}" for i in range(300)]
    stream = random.choices(items, k=20_000)
    midpoint = len(stream) // 2

    a = CountMinSketch(width=400, depth=4, seed=5)
    for event in stream[:midpoint]:
        a.add(event)
    b = CountMinSketch(width=400, depth=4, seed=5)
    for event in stream[midpoint:]:
        b.add(event)

    assert list(a.merge(b).table) == [
        x + y for x, y in zip(a.table, b.table)
    ]

The full suite this tutorial was built against also checks the error-bound formula, the constructor’s input validation, and the mismatched-merge rejection. Running it end to end:

$ pytest test_cms.py -v
...
============================== 8 passed in 0.43s ==============================

Verify It All Works End to End

Before trusting any of this, re-run the whole sequence fresh in a clean directory: build cms.py with the constructor, add(), estimate(), merge(), and sized_for() from Steps 2, 3, and 7, add the BrokenSeedCountMinSketch subclass from Step 5, then run each numbered script in order. You should see: the naive counter costing roughly 210 KB for 2,000 keys, the from-scratch sketch never underestimating any of those 2,000 keys, the undersized sketch’s error collapsing once you give it the properly computed width and depth, the broken-seed sketch’s five rows coming back byte-for-byte identical, the heavy-hitters tracker’s output matching Counter.most_common(5) exactly, and the merged sketch’s table matching a from-scratch build on the combined stream. If any of those checks disagree with what is shown above, the most likely cause is a change to the hash input format in _column(), since every downstream calculation depends on it producing the same columns for the same item on every call.

Next Steps

A Count-Min Sketch is one member of a small family of structures that trade exactness for a fixed memory footprint. If you have not already, the Bloom Filter tutorial covers the closely related problem of testing set membership instead of counting frequency (Wikipedia even describes a Count-Min Sketch as comparable to “an implementation of a counting Bloom filter”), and the HyperLogLog tutorial covers estimating how many distinct items a stream contains, a different question from how often each one appeared. From here, a natural next step is wiring a Count-Min Sketch into a real request path: track per-IP or per-API-key request counts in front of a rate limiter, or use it as the admission-frequency signal in a cache eviction policy, both common real deployments of exactly this structure.