Why architecture matters here
CMS architecture matters because it gives frequency estimates at fixed cost regardless of the number of distinct items. Naive counting stores every key + count; CMS stores a fixed d × w matrix. At streaming rates, this matters directly.
Cost is fixed. Choose d, w to match error budget.
Reliability of estimates is provably bounded: with parameters d = ⌈ln(1/δ)⌉, w = ⌈e/ε⌉, error ≤ εN with probability 1-δ.
The architecture: every step explained
Walk the diagram top to bottom.
Item + count. Insert (key, count) into sketch.
d hash functions. One independent hash per row of the sketch.
d × w counter matrix. Storage: d rows, w columns. Small integer counters.
Insert. For each of d rows, hash key to column in [0, w), increment counter by count.
Query. For each row, hash key to column, read counter. Return min of the d values. Min because collisions only add.
Overestimate. Counters may be inflated by other keys hashing to same column. Never under, always over or exact.
Params: eps, delta. Error at most εN with probability 1-δ where N is total inserted count.
Applications. Heavy hitters, rate limiters, streaming top-k, network monitoring.
Variants. Count-Min with heap for top-k tracking. Count-Mean-Min for less bias.
vs Bloom / HLL. Bloom = membership only. HLL = cardinality of distinct. CMS = frequency.
End-to-end insert + query flow
Trace inserts and queries. Sketch with d=4, w=1000.
Insert "cat", count=1. For each of 4 hash functions, compute column in [0, 1000), increment counter.
Insert "cat" again. Same 4 columns get incremented.
Insert "dog", count=5. 4 different columns (mostly) increment by 5.
Query "cat": for each of 4 rows, hash and read counter. Suppose values [2, 3, 2, 8]. Min = 2. Correct: cat inserted twice.
Query "elephant" (never inserted): [1, 0, 2, 1]. Min = 0. Correct (or under-est possible if all rows collided, but min = 0 means at least one row saw 0 → truly absent).
Rate limiter application: sketch tracks per-user request rate. Query at each request; if count > threshold, throttle.
Heavy hitter: maintain a min-heap of top-K keys with their CMS-queried counts. Update on each insert; efficient top-K over stream.