Motivation
A stream may contain far more updates than can be stored individually. If the item universe is large, maintaining an exact counter for every possible item can also be expensive. A Count–Min sketch uses a small array of shared counters. Hash collisions can only increase an estimate when updates are nonnegative, and multiple independent rows make large overestimates unlikely.
The guarantee is additive relative to the total stream weight. It is not a relative-error guarantee for every rare item. We prove the result for a fixed query and an update stream chosen independently of the sketch's random hashes, then explain how to obtain a simultaneous guarantee for a finite set of queries.
Definitions
Let be a finite item universe. A stream consists of updates with and nonnegative integer increment . Let be the total increment to item , and let be the total stream weight. Counts are exact nonnegative integers; zero increments are harmless.
Choose a width and a depth . For each row , choose a random hash function from a family satisfying
Rows are independent. This collision property follows from uniform pairwise-independent hash values, but the proof needs only the displayed collision bound within each row. We assume the stated family can be sampled and evaluated; its representation and computational costs are separate implementation requirements.
Maintain counters , initially zero. On update , add to in every row. For query item , return
Theorems
Theorem 10.2.1
(Fixed-query Count–Min guarantee)
For and , take and . For any fixed nonnegative stream and fixed query , independent of the hashes,
Theorem 10.2.2
(A finite simultaneous guarantee)
For a fixed set of query items, using depth makes all their estimates satisfy the same additive bound with probability at least .
Proof: one row
Proof
(Error of a single row)
Fix and one row. Its queried counter contains all updates to , plus updates to other items that collide with . Define the nonnegative collision noise
Thus . This inequality holds for every hash outcome because increments are nonnegative. Taking the minimum over rows also never underestimates.
By linearity of expectation and the collision bound,
The collision indicators for different need not be mutually independent. Their individual probabilities and linearity are enough. If , Markov's inequality gives
The same bound holds if strict inequality is replaced by a non-strict threshold. If , every counter and true frequency is zero, so the conclusion is immediate without applying Markov at a zero threshold.
Proof: independent rows and queries
Proof
(Amplification over rows and queries)
For a fixed stream and query, the noise in row depends only on that row's hash function. The rows are independent, so the events that their noises exceed are independent. The minimum estimate exceeds only if every row has excessive noise. Its probability is at most . Together with the deterministic no-underestimate property, this proves the fixed-query bound.
For a fixed set of query items, replace in the per-query calculation by . The chosen depth makes each query fail with probability at most . A union bound gives probability at most that any query fails. The query failures can be dependent; the union bound does not require independence among them.
Proof X-ray
Two uses of probability
Where each hypothesis enters: nonnegativity of the increments gives the deterministic bound and makes nonnegative, so Markov's inequality applies. The collision bound is used only through linearity of expectation, so needs no independence among the colliding items. The key move is two-level: Markov turns a mean into a constant failure probability for one row, and independent rows raise that probability to the power . For several queries a union bound replaces independence, which is why the depth grows only logarithmically in . If the stream or query is chosen after the hashes are seen, the premise ‘fixed stream and query’ fails and the argument does not apply.
Worked examples
Worked example 10.2.3
(One collision)
Suppose the stream has frequencies , , and a row hashes and to the same bucket. The queried row counter for is seven, so its collision noise is three. A second row that separates them gives counter four, and the minimum of the two row counters is the exact frequency four.
Worked example 10.2.4
(A zero stream)
If all increments are zero, and every counter remains zero. Every query returns its true frequency zero. There is no need to divide by in this case.
Worked example 10.2.5
(Choosing dimensions)
For and , the stated choices are and . For a fixed query, the probability of additive error greater than is at most . This is a worst-case bound over the fixed stream, not a claim that typical error equals .
Worked example 10.2.6
(A rare item)
If , and , the guarantee permits an estimate as large as . That is a small additive error relative to but a large relative error for . The theorem makes no multiplicative guarantee for rare items.
Common mistakes
Counterexample mode
Negative updates break one-sidedness
Suppose and a separate item contributes a negative update of to a bucket shared with . That row counter can be , below the true frequency of . Taking a minimum cannot repair the claimed deterministic lower bound. The theorem assumes nonnegative increments.
Common mistake
(Applying the fixed-input guarantee to adaptive streams)
The probability statement fixes the stream and query independently of the random hashes. If an adversary can inspect the sketch and choose future updates or the query based on the hash outcomes, the same fixed-input calculation does not automatically apply. Adaptive guarantees require a separate model and proof.
Common mistake
(Replacing the minimum by an average)
The minimum is essential to the amplification argument: it is small when at least one row has small collision noise. Averaging counters would be a different estimator and would require a different analysis.
Concept lensAlgebraic
The sketch is a linear image of the frequency vector
Let be the frequency vector. The counters satisfy , where is a - matrix with one entry in each column of each row block, namely at the bucket . Hence the sketch of two streams combined is the sum of their sketches, and is exactly the collision noise term.
Space and update costs
The sketch stores integer counters. Each update evaluates hashes and increments counters; each query evaluates hashes and takes a minimum. Under constant-time hashing and word-sized counter operations, these take time per update or query. If counts can grow beyond one machine word, their bit lengths and arithmetic costs must be included. Hash-function descriptions also occupy space and must be counted for a concrete family.
The parameter choices give and , hence counters. This is a count of counters, not automatically the same number of bits. Each counter must represent values up to in the nonnegative stream model.
A concrete implementation must use a collision family with the stated probability, independent row choices and a representation compatible with the universe. An idealized table of fully independent hash values is mathematically valid but may require space proportional to . The theorem separates the sketch analysis from that construction cost.
A concrete collision family in a limited setting
Suppose the universe is a subset of the finite field for a prime , and choose the sketch width to be exactly . Choose independently and uniformly from , and define in the field, identifying its values with the bucket labels. For distinct , a collision means . Since in a field, this happens exactly when , with probability .
In fact the two hash values are jointly uniform. For any prescribed outputs , the equations and have a unique solution: and . Thus each output pair occurs for exactly one of the equally likely choices of . Independent choices of the two field elements for each row give independent row functions.
This construction illustrates the hypothesis, but it is not a general compressed-universe solution: it requires an injective representation of in a field of size and uses buckets. In particular, if , the resulting width may be too large to save space compared with exact counters. A practical smaller-width family needs its own proof of the desired collision bound; simply taking a field value modulo an unrelated bucket count can introduce bias.
Following the counters
Consider a two-row sketch of width three. Suppose the first row hashes to buckets , and the second hashes them to . Process updates , and . The first-row counters become and the second-row counters become . The query for reads five and two and returns two, its exact frequency. The query for reads five and seven and returns five, an overestimate of two. The query for reads four and seven and returns four, its exact frequency. A collision in one row need not cause an error in the minimum if another row separates the queried item from its colliders.
The example separates a particular hash outcome from the probability guarantee. The theorem does not promise that every possible choice of hashes gives a small error. It bounds the probability, over the specified random row choices, of a large error for a fixed stream and query. With the chosen width and depth of this small example, no particular numerical failure guarantee has been asserted.
Deriving and using Markov's inequality
For a nonnegative random variable and , the pointwise inequality gives . Rearranging proves Markov's inequality. Here nonnegative updates make nonnegative, so the argument applies to collision noise. The exceptional zero-total case is handled directly because the threshold would then be zero.
The theorem bounds . If the estimate equals the upper boundary, it still satisfies the guarantee. Using a non-strict threshold in Markov gives a valid upper bound for the strict failure event, even when is not an integer.
For a predetermined set of queries, a union bound controls the event that any one fails. The set can be the whole finite universe, at the cost of depth when is nonempty. This simultaneous guarantee holds on one high-probability event for all those items. It does not automatically cover an unbounded sequence of adaptively chosen updates that changes the stream after observing the sketch.
Reading the parameter tradeoff
Increasing width reduces the expected collision noise in each row; increasing depth reduces the probability that every row has a large collision. These two effects appear in different parts of the proof. Doubling depth without controlling single-row noise does not by itself establish the stated threshold, and widening a single row does not produce the same exponential confidence amplification.
The constants and the ceiling choices are convenient sufficient values. Other widths and depths can be analyzed directly from the bound whenever . Using a different constant may change the numerical space bound while leaving the same proof structure. All logarithms in the parameter formula are natural logarithms.
Summary
A row counter equals the true frequency plus nonnegative collision noise. The collision property bounds the expected noise, Markov bounds a single-row failure, and independent rows amplify the chance that at least one row is accurate. A union bound extends the result to any fixed finite set of queries.
Exercises
Quick check
(Why can the estimate never be below the true frequency under nonnegative updates?)
Which quantity is added to the true frequency in each row?
Solution · Answer
Each queried counter includes all updates to the queried item plus nonnegative contributions from colliding items. The minimum of numbers all at least is still at least .
Quick check
(If a row has expected collision noise at most , what bound does Markov give for noise exceeding when ?)
Apply Markov to the collision noise.
Solution · Answer
At most .
Quick check
(Why is independence across rows needed in the displayed exponential failure calculation?)
How are the failure probabilities of the individual rows combined?
Solution · Answer
The proof multiplies the probabilities that every row has excessive noise. That multiplication is justified by independent row hash functions for a fixed stream and query; correlated rows could fail together.
Quick check
(How should the per-query failure budget be chosen for fixed queries and total failure probability at most ?)
Divide the total failure budget among the queries.
Solution · Answer
Use failure probability at most for each query. The union bound then gives total failure probability at most .