When a frequency can decrease
An event counter often needs corrections. A duplicated event may be removed, an earlier value may be revised, or two time windows may be compared by subtracting their frequency vectors. The resulting coordinates need not all be nonnegative. The previous Count-Min unit explained why taking a minimum then loses its deterministic upper-bound property: a collision with a negative coordinate can pull a counter below the true answer.
CountSketch changes the treatment of a collision. Each key receives a random sign as well as a bucket. Before adding an update to a bucket, we multiply it by that key's sign; when reading the bucket, we multiply by the queried key's sign again. The queried contribution is restored exactly because the square of a sign is one. Other contributions may have either sign. Their expectation cancels, and their second moment gives a useful error scale.
This unit proves a point-query guarantee; it does not supply an algorithm that discovers all frequent keys.
A fixed stream and exact signed counters
Definition 14.1.1
(Net frequency and the general turnstile model)
Let be a finite universe. An update has key and arbitrary real amount . At a fixed time , the net frequency of is
Allowing negative amounts with possibly negative net coordinates is the general turnstile model.
Requiring every net coordinate to stay nonnegative would be the stricter turnstile model. The argument here does not impose that restriction. The complete finite stream is fixed independently of all sketch randomness. We first fix a queried key and time independently of that randomness too. Random input independent of the sketch can be treated by conditioning on the input.
Definition 14.1.2
(CountSketch rows and the update rule)
Choose width and an odd number of rows . In each row , choose a bucket function and a sign function with these properties:
- For distinct keys , .
- Signs at any two distinct keys are independent and each is uniformly distributed on .
- The entire sign function is independent of the entire bucket function in that row.
- The pairs are independent between rows.
Initialize every counter to zero. For update , perform the following in every row:
The first property is a universal-hashing collision bound; it does not require all bucket values to be mutually independent. Pairwise independent signs suffice for the point-query second-moment calculation below. A deterministic hash routine or repeated seed is not a proof of these properties.
The signs and hashes stay fixed for the lifetime of the summary. Adding an update and its exact negative therefore cancels their effects. By induction over updates, at any time
This is an exact-arithmetic identity. An implementation using bounded integers must prevent overflow; floating-point updates require a separate rounding analysis.
Definition 14.1.3
(Row estimates and the median estimate)
For a queried key , the row estimates and the final point estimate are
The median is the middle order statistic because is odd. It tolerates a minority of very inaccurate rows.
Concept lensAlgebraic
Each row is a random linear map
Fix a row and order the keys. Let be the matrix with entries ; each column has a single nonzero entry, equal to . The counter invariant says that row of the counter array is . Moreover
so the vector of all row- estimates equals . The diagonal entries are one, and properties 2 and 3 give the off-diagonal entries mean zero, so . The proposition below says that this random matrix is the identity on average, with a controlled spread in each coordinate. Linearity of is what lets compatible summaries be added and subtracted; the median across rows is the only nonlinear step.
Why the row estimate has the right mean
Suppress the fixed time and write
The coordinate is absent from the noise. Define the remaining squared mass by
This is the squared Euclidean length of the vector after deleting the queried coordinate. In particular, one very large queried coordinate does not inflate its own collision-error bound. Large other coordinates do. Opposite net frequencies do not cancel inside this sum of squares.
Proposition 14.1.4
(Mean and variance for one fixed point query)
Under the stated assumptions, for each row,
The expectation is over the random functions, with the frequency vector and queried key fixed independently of them.
Proof
(Expanding the row error)
Let . Pairwise uniform signs give for . Independence of the two functions lets us factor this expectation from that of . Every term in is therefore zero, proving unbiasedness.
For the second moment, expand the square. Since and ,
For distinct , independence of the sign and bucket functions factors the cross expectation into . The indicators themselves need not be independent. The diagonal terms are at most by the collision bound. Hence . The noise has mean zero, so this is the variance bound.
Proof X-ray
A common queried sign disappears before the cross terms
The noise terms share , so they are not automatically independent. Independence of the terms is unnecessary. On squaring, the shared sign becomes , and each remaining cross term contains just two different signs, whose product has mean zero. This is why pairwise sign independence suffices here. Independence from the bucket function is what permits the factorization; independent rows will be used later, not in this calculation.
The proposition concerns individual rows. It does not assert that taking a median preserves their expectation; the confidence proof below establishes a different property of the median.
From a variance bound to high confidence
If , every other coordinate is zero, all row errors are identically zero, and the final answer is exact. Suppose . For , Chebyshev's inequality gives
Choose , so a row is bad with probability at most . More buckets reduce the failure probability of one row; independent rows reduce it further.
Theorem 14.1.5
(Median confidence for a fixed key and time)
Let . Use width and any odd integer . For the fixed stream, key and time specified above,
The constants are sufficient and deliberately conservative.
Proof
(A failed median needs a majority of bad rows)
Put . If at least row estimates belong to , their middle order statistic belongs to that interval too. If the median were below the interval, all good values would be strictly greater than it, but only order positions lie after the median. The case above the interval is symmetric. Consequently a failed median requires at least bad rows.
For any specified set of rows, independence between rows makes the probability that they are all bad at most . If there are at least bad rows, some such set exists. A union bound over the possible sets yields
We used and , the latter because there are subsets altogether. The case was already exact. This completes the proof without assuming independence between queries.
Proof X-ray
Why the width constant is eight and not four
The proof has a deterministic half and a probabilistic half. The order-statistic step uses no randomness: a bad median forces a majority of bad rows. Row independence enters only to bound a specified majority by , where is one row's failure probability. The union bound then gives , which decays only when . Chebyshev with width gives , so any works; makes and yields the clean depth .
The space is exactly counters plus descriptions of the random functions. If is the smallest permitted odd integer, this is counters; the added one accounts for the minimum depth even when is close to one. An update touches counters. A query reads counters and selects their median; sorting them is a simple implementation, while a linear-time selection method can avoid a full sort. These are operation and counter counts, not a fixed-byte bound. For integer updates with known total absolute update mass , each counter has magnitude at most , so bits per signed counter suffice.
A signed example, including an underestimate
Worked example 14.1.6
(Undo each row's sign before taking its median)
Let . Use three buckets and these realized assignments; a pair such as means bucket zero and sign minus one.
| Key | Net frequency | Row 1 | Row 2 | Row 3 |
|---|---|---|---|---|
| 5 | ||||
| -3 | ||||
| 2 | ||||
| 1 |
The counter rows are , and . For , undoing the queried sign gives row estimates , so the median is 5. For , the row estimates are , and the median is the true signed value .
For , the squared collision scale is . The small table shows how the rule works, not that width three meets a chosen confidence requirement. For and , our sufficient theorem uses width 128 and depth 9: 1152 counters. Its successful event guarantees error at most , approximately .
The scale is a sum of squares, not the signed sum of the other frequencies, and the next example makes the difference concrete.
Worked example 14.1.7
(Opposite frequencies still enter the error scale)
Let the queried key have , and let two other keys have and . Their signed sum is zero, but , so . In a realized row with and ,
The row error is 100 in absolute value although the other frequencies sum to zero, and it lies within , as the scale predicts. Because , the additive statement "error at most " stays meaningful, while a relative error divided by is undefined. The theorem is therefore not a relative-error guarantee for small coordinates.
Common mistake
(Reading the bucket without undoing the queried sign)
In the table, the buckets of hold , whose median is 2. The counter stores plus noise, so only multiplication by restores . The row estimates have median 5, the exact value.
Common mistake
(Taking the minimum over signed rows)
In Count-Min every collision adds a nonnegative amount, so every row overestimates and the minimum is the safest row. With signs a row error can be negative, and the minimum selects the most negative one. In the table the minimum for is 2, an underestimate by 3, while the median is exact.
Why the independence wording matters
Counterexample mode
Correct sign marginals do not excuse coupling signs to collisions
Take two keys , width two, and . Draw as independent uniform signs. Set and set when the signs agree, but when they disagree. The sign family is pairwise independent, and the collision probability is exactly , as required for width two. Nevertheless the functions are coupled.
When the signs agree, querying returns 2; when they disagree, it returns 0. Both cases have probability , so the expected answer is 1 rather than the true value zero. The first-moment term used for unbiasedness no longer factors into . Repair the construction by drawing the sign function independently of the bucket function; checking their marginal properties separately was insufficient.
Row independence, property 4, is a separate requirement, and storing extra copies does not supply it.
Common mistake
(Copying a row instead of drawing a new one)
A copied row has exactly the original row's bad event, so copying it nine times leaves the same bad probability. The median argument multiplies probabilities only for independent row constructions. Repeated storage does not create independent information.
Linear merging, nonlinear queries, and finite query budgets
Keep identical dimensions, hashes and signs when summarizing separate inputs. The counter invariant is linear in . Entrywise addition of summaries for vectors and therefore equals the summary for , and entrywise subtraction equals the summary for . This makes a signed difference between two fixed time windows possible without retaining each event. The combined input vectors must still be independent of the random functions.
Apply the point-query theorem to the combined vector: its scale is for subtraction. Cancellation may reduce this scale, but the formula does not replace it by zero just because the total signed mass is zero. Merging summaries built with different functions does not have the stated invariant.
Worked example 14.1.8
(Subtracting medians is not querying the difference)
Suppose two compatible summaries give row estimates and for the same key. Each median is zero, so the difference of the returned medians is zero. The rowwise difference is , whose median is ten. The array difference is the summary of , so querying it is the operation that the combined-vector guarantee covers; the difference of returned medians carries no such guarantee, because the median is nonlinear.
For predetermined key/time pairs on an independently fixed stream, each pair has failure probability at most with the chosen width. The union bound gives total failure at most . It suffices to choose any odd . The queried values may share counters; their errors need not be independent.
For a finite universe of size and a known finite horizon , taking protects every key and every prefix up to on one event. On that event, a reader may select a query or a stopping time bounded by after seeing outputs: all its possible key/time pairs were already protected. The underlying updates remain fixed independently of the sketch. This is not a proof for future updates chosen adversarially from observed outputs, an unbounded horizon, or an unlimited universe.
Practice with complete solutions
Quick check
(For the worked frequency vector and query , take width 20. Bound the variance of one row and its probability of an absolute error greater than 2. Is this necessarily the exact variance?)
Use the squared mass of the other coordinates.
Solution · Answer
The other-coordinate squared mass is 14, so the variance is at most . Chebyshev bounds the stated probability by . The collision assumption is an upper bound, so the variance need not equal 0.7. No independence between bucket collision indicators is needed for this calculation.
Quick check
(Use our sufficient construction with and overall failure allowance . Find the width, the smallest allowed odd depth, and counter count for one fixed query. Repeat for 16 predetermined queries.)
For several queries, replace by in the depth condition.
Solution · Answer
Width is . For one query, , so the smallest odd choice is 7, giving 224 counters. For 16 queries, , hence choose 15 and store 480 counters. This budgets simultaneous failure; it does not assume independent query errors.
Quick check
(A fixed vector has only one nonzero coordinate, . What does the sketch return for ? If an absent key is queried instead, must it return zero?)
Compare and .
Solution · Answer
For , every row returns , so the median is exact. For , a collision contributes , so individual row estimates can be nonzero and the median is not guaranteed to be zero for every random construction. The error scales differ: while . A nonzero approximate answer alone does not certify that a key occurred.
Quick check
(In the coupled-hash counterexample, replace by an arbitrary fixed real . Compute the expected answer for and identify precisely which assumption fails.)
Condition on whether the two signs agree.
Solution · Answer
The answer is when signs agree and zero otherwise, so its expectation is . It is biased unless . The signs remain pairwise independent and uniform, and the collision bound remains . Independence of the whole sign function from the whole bucket function fails, which prevents the expectation factorization used in the proof.
Quick check
(Two time windows each contain a key one hundred times, while key occurs 12 times in the first and 7 in the second. Each occurrence is a update, and no other keys appear in either window. What is the difference vector, and what does a compatible difference sketch return for ? Explain why this does not justify subtracting returned medians in general.)
Subtract the arrays first, then query.
Solution · Answer
The difference has and . After entrywise subtraction of compatible arrays, only coordinate remains; every row query for is therefore exactly 5. This conclusion uses cancellation before the query. In general the median of rowwise differences differs from the difference of medians, as the explicit three-row example showed, so the same argument cannot be transferred to the latter procedure.
This unit establishes signed point updates, an exact array invariant, row unbiasedness and variance, median confidence, and compatible linear merging under stated finite-query assumptions. It does not cover candidate discovery, stronger bounds after removing several large coordinates, adversarially adaptive streams, or an implemented hash-family construction.