A frequency question
A stream contains updates to keys in a fixed universe , with nonnegative integer weights . Let be the sum of the weights for and the total weight. Only finitely many updates are processed. Keeping an exact counter for each distinct key may be costly; a Count–Min sketch trades exactness for a compact table. It answers the frequency of a specified key, but it does not by itself list all keys that have occurred.
Definition 1.2.1
(Count–Min sketch and its estimate)
Choose positive integers (width) and (depth), and choose random hash functions independently across rows . Within each row assume only the collision bound
Initially every counter is zero. For each update , add to in every row. The estimate of a key's frequency is
The stream and any queried key are fixed independently of the chosen hashes. We do not require independence among different collisions in one row. Hash descriptions and seeds must also be stored; their size depends on the chosen family and universe. The collision condition is an assumption to verify for that family, not a property of an arbitrary hash function.
Proposition 1.2.2
(The estimate never undercounts)
If every update weight is nonnegative, then for every key and for every realization of the hash functions.
Proof
(Each queried counter contains the whole count)
Fix a row . Every update adds to , so this counter receives all of , together with the weights of the keys with . Those extra weights are nonnegative, hence for each , and the minimum over is also at least .
The argument used the sign of the colliding weights and nothing else, which is why the hypothesis on the updates cannot be dropped.
Counterexample mode
Negative updates can push the estimate below the truth
Claim: the Count–Min estimate is an upper bound for every stream of integer updates. Take , , and hashes that send keys and to the same bucket in both rows. Process and . Both queried counters for equal , so , while . The proof breaks exactly where the colliding weight was assumed nonnegative. The repaired statement is the proposition above: with nonnegative updates the estimate is one-sided; with negative updates neither this inequality nor the error bound below is claimed.
Error bound for a fixed key
Theorem 1.2.3
(Count–Min error bound)
Assume nonnegative updates, fix the stream and a key before the hashes are drawn, and let . If , then
In particular, for the choices and give success probability at least .
Proof
(Markov in each row, independence across rows)
The lower inequality holds always by the previous proposition. When , all counters and frequencies are zero, so the result holds deterministically without dividing by ; assume . In row , the excess over the true count is
By linearity of expectation and the collision assumption,
No independence between terms of this sum is needed. Markov's inequality gives
Because entire row hash functions are independent and the stream is fixed, the row errors are independent. The minimum estimate exceeds only if every row's error exceeds , an event of probability at most . Finally, gives .
Proof X-ray
Where each assumption enters the error bound
The proof has two separate moves. The first is within one row: the expectation of the excess needs only pairwise collision probabilities and linearity, so hashes inside a row may be correlated in any way. Markov's inequality then needs , which is again the nonnegative-update hypothesis. This row-level bound is weak, only . The second move is the amplification: taking a minimum turns "one row is good" into success, so failure requires all rows to fail, and this is the only place where independence of whole rows is used. Fixing the stream and key before drawing the hashes is what makes the functions of independent hashes alone; a key chosen after looking at the table would break this step.
This is a probability statement over the hash selection for a fixed stream and key, not a guarantee for every adaptively chosen key after seeing the table. For a predetermined finite set of keys, a union bound gives simultaneous success probability at least ; makes the total failure probability at most . No independence between different keys' failure events is needed for that union bound.
Common mistake
(The error is additive in the total weight, not relative to the key)
The bound reads , with the weight of the whole stream. It does not say . For a rare key with much smaller than , the estimate may be many times the true count and still satisfy the theorem.
A small table and merging
Worked example 1.2.4
(Reading the estimates from a fixed table)
Suppose , and , with and . In row 1, let and hash to bucket 0 and to bucket 1. In row 2, let and hash to bucket 1 and to bucket 2. The nonzero counters are
The queried row counts for are , giving ; for they are , giving ; and for they are , giving . Each estimate is at least the true count, as the proposition guarantees, and the minimum removes the collision in whichever row is cleaner. The example illustrates collisions for these particular functions; a single chosen table is not an empirical proof of the probability bound.
Worked example 1.2.5
(Sizing a sketch for a fixed set of queries)
Suppose the queries form a predetermined set of keys, with and total failure probability . The width does not depend on : . The depth must satisfy , so . Then , and with probability at least every one of the estimates lies in . The table has counters. For a single key, would suffice; the extra five rows pay for the union bound.
Two sketches of disjoint update batches may be merged by adding corresponding counters only when their dimensions and row hash functions agree. The result equals processing the concatenated batches with that same hash choice. If the batches overlap, shared updates are counted twice. The bound above applies to the combined stream when it was fixed independently of the shared hashes.
Worked example 1.2.6
(Merging two batches with shared hashes)
Use the hashes of the first example. Batch 1 is and batch 2 is . Sketch 1 has , , ; sketch 2 has , , . Adding entrywise gives
The concatenated stream has , , , and processing it directly gives , , , : the same table. Hence , exactly as for a single sketch of the whole stream.
Common mistake
(Adding sketches built with different seeds)
Counters can be added only if they describe the same buckets. With , , let sketch 1 use and receive , and sketch 2 use and receive . Adding gives counters ; querying with reads , although . The one-sided guarantee fails even with nonnegative updates, because the merged table is not the sketch of any stream under one hash choice.
The table uses counters and each update touches counters, in addition to hash descriptions and the cost of computing hashes. In a word model with constant-time arithmetic and hashing, this is counters and operations per update and per query. Exact nonnegative counters can reach and require up to bits each when ; fixed-width overflow invalidates exact arithmetic and can invalidate the guarantees. A small number of counters is not automatically a complete memory bound in bits.
Exercises
Quick check
(In the first worked example, why is larger than even though all updates are nonnegative?)
Look at which keys share 's bucket in each row.
Solution · Answer
The two queried counts are and : in row 1 the key collides with and adds , in row 2 the key collides and adds . Every row has a positive collision contribution, so even the minimum, , exceeds . Nonnegativity guarantees only , not equality.
Quick check
(For and , find integer and by the ceiling choices, and state the probability statement they ensure for one fixed key.)
Solution · Answer
and . For a stream and key fixed before the hashes are drawn, the probability over independent row hashes that the estimate lies between and is at least .
Quick check
(A user queries the sketch, sees the table, and then picks the key whose estimate looks largest. Does the fixed-key theorem bound the error of that estimate?)
Solution · Answer
No. The theorem requires the key to be fixed independently of the hashes. A key chosen after inspecting the table may be selected precisely because its buckets carry large collisions. Only a predetermined set of keys is covered, through the union bound with .