A Count-Min sketch is d rows of w counters. Each update increments one counter per row; each estimate is the minimum of a key's d counters. The estimate is never below the truth, because a counter can only be raised by other keys. The guarantee is Markov's inequality applied per row and multiplied: with w = 8 and d = 3 the error exceeds a quarter of the stream length with probability at most 1/8, and on the lab's stream the worst overcount is 2 out of 64 updates.
Core ideas
The hard idea is that taking a minimum removes the error in one direction entirely. The other two are where the bound comes from and how loose it is.
Key x increments one counter per row, so each of its d counters is at least its true count; the other keys that hash to the same cell can only add. Taking the minimum of the d counters therefore gives a value at or above the truth, always, on every stream and every hash choice. The panel checks it on every key and reports never below the truth rather than assuming it.
Let F₁ be the total number of updates. In one row, the overcount on key x is the number of updates by other keys landing in x's cell. Each such update lands there with probability 1/w, so by linearity the expected overcount is at most F₁/w. That is the same indicator-and-sum argument as “Balls in Bins and the Birthday Bound”, with updates in place of keys and counters in place of slots.
Markov's inequality on that overcount at a = 2F₁/w gives P ≥ 2F₁/w) ≤ 1/2 for one row. The rows use independent hashes, so all d rows overcount by that much with probability at most 2⁻ᵈ, and the minimum overcounts by that much only if all of them do. At w = 8 and d = 3: error at most 16 with probability at least 7/8. This library proves Markov and not Chernoff, so this is the guarantee it can state.
The material
The structure, the one-sided error, the Markov guarantee per row, and how far the bound sits from what happens.
A Count-Min sketch is a d × w array of counters, all initially zero, with one hash function per row mapping keys to 0..w − 1. To update key x, increment the counter at (i, hᵢ(x)) in every row i. To estimate the count of x, report the minimum of those d counters. The space is d·w counters, fixed in advance, independent of how many distinct keys arrive.
That last clause is why the structure exists. An exact frequency table grows with the number of distinct keys and a stream can have more of them than you have memory for. A sketch has the size you chose when you built it, and the price is an error whose size you can bound.
For every key x, every stream and every choice of hash functions, the reported estimate is at least the true count of x.
Fix a row i. Every update of x increments the counter at (i, hᵢ(x)), so that counter is at least the true count of x. Every other update increments some counter, possibly this one, and counters are never decremented, so nothing can bring it below that.
The estimate is the minimum over d such counters, each at or above the true count, so it is at or above the true count as well.
□
Let F₁ be the number of updates. For any key x, the estimate exceeds the true count by at least 2F₁/w with probability at most 2⁻ᵈ, provided the rows' hash functions are chosen independently and each spreads keys uniformly.
Fix a row and a key x. For each update of a key other than x, let the indicator be 1 if it lands in x's cell in this row. Each has expectation at most 1/w, so by linearity the expected overcount in this row is at most F₁/w.
The overcount is non-negative, so Markov's inequality applies: P(overcount ≥ 2F₁/w) ≤ (F₁/w)/(2F₁/w) = 1/2.
The rows are independent, and the minimum overcounts by at least 2F₁/w only if every row does, which has probability at most (1/2)ᵈ = 2⁻ᵈ.
□
Markov's inequality is doing all the probabilistic work, and it is the inequality “From an Expectation to a Probability” proves. The textbook statement of this bound is sharper — e/w in place of 2/w, and e⁻ᵈ in place of 2⁻ᵈ — and it needs a concentration result this library does not teach. So the guarantee here is the one that can be proved with what the reader has, and the panel prints 2/w and 2⁻ᵈ for that reason rather than quoting a stronger claim it cannot support.
The stream is 64 updates over 12 distinct keys: key 1 arrives forty times, keys 2 and 3 arrive three times each, and keys 4 to 12 twice each. With w = 8 and d = 3 the sketch takes 192 increments and 36 reads. Every estimate is at or above the truth; five keys are overcounted, each by exactly 2, and the rest are exact. Key 1's estimate is 42 against a true 40.
The bound allows an error of 2F₁/w = 2·64/8 = 16 with probability up to 1/8, and the worst error observed is 2. That is a factor of eight of slack on this stream, and it is the ordinary situation: Markov is loose, “From an Expectation to a Probability” measured it being loose by factors from 2 to nearly 3849, and nothing about this application changes that.
Notice which keys were overcounted. The heavy hitter was, by 2, and so were four of the light keys — and those light keys were overcounted by the same absolute amount, which is a much larger relative error: an estimate of 4 for a true count of 2 is out by a factor of two, while 42 for 40 is out by five per cent. The bound is additive in F₁ and says nothing about relative error, which is the sketch's real limitation and the reason it is used to find heavy hitters rather than to count rare keys.
w controls the size of the error and d controls the probability of exceeding it. Doubling w halves 2F₁/w; adding a row halves 2⁻ᵈ. They are separate knobs and the space is their product, so a sketch with many narrow rows and one with few wide rows can occupy the same memory and offer different guarantees.
The lab's third preset makes the trade visible: w = 12 and d = 4 over a seeded stream of 64 updates across 12 keys. The bound becomes 2F₁/w = 32/3 ≈ 10.67 at a failure probability of 1/16, and every estimate came out exactly right — worst overcount 0. A wider sketch on the same amount of data collides less; the bound improved and the actual error improved more.
And when nothing collides the sketch is exact. The uniform preset — ten keys, six updates each — has a worst overcount of 0 at w = 8 and d = 3, so every estimate equals its truth. That is not the sketch being right about the stream in general; it is this stream's keys happening to miss each other in at least one row each, and a different hash choice would give a different table.
The exact quantities here are 2F₁/w and 2⁻ᵈ, which are fractions computed from the parameters. The measurement is the worst overcount on the stream on screen, which is 2 on the opening preset and 0 on the other two. The bound is the pair of exact quantities read as a guarantee, and it covers streams nobody has run. The course ends where it began: those are three kinds of number and the page prints all three.
Interactive
Estimate by the minimum of d counters, and the error is one-sided
Method
Check the direction of the error first, then its size, then its probability.
This holds always and by construction, and the panel verifies it key by key rather than asserting it. If it ever failed, the defect would be in the implementation rather than in the analysis.
2F₁/w. At 64 updates and eight counters a row that is 16, which is a quarter of the whole stream — large. The bound is about a worst case over streams, and on the stream shown the worst error is 2.
2⁻ᵈ. Three rows give 1/8. Adding a row halves it and costs w counters, and widening the rows shrinks the error instead. Decide which of the two you need before spending the space.
The bound is additive in F₁, so a key with a true count of 2 can be reported as 4 and stay well inside it. Sketches find heavy hitters; they are not a way to count rare keys accurately, and the opening preset shows both cases in one table.
Key 1 forty times; keys 2 and 3 three times each; keys 4 to 12 twice each. Three rows of eight counters. Every estimate is the minimum of that key's three counters.
The bound allows 16 and the worst error is 2. That is Markov being Markov, and it is the third time on this course that the same inequality has come in loose by roughly an order of magnitude. It is still the guarantee, because it holds for streams nobody has run, and the 2 holds only for this one.
Compare key 1 and key 4. Both are overcounted by 2. For key 1 that is an estimate of 42 against 40, five per cent out; for key 4 it is 4 against 2, a factor of two. The bound is additive and does not distinguish them, which is precisely why the structure is used to find the keys with large counts and not to report the small ones.
For a faded rehearsal, set the rows to 4 and predict what moves before the panel redraws. The supplied first move is this: d appears in 2⁻ᵈ and not in 2F₁/w, so one of the two guarantee figures changes and the other does not. Say which, say what the new value is, and then say what would have to change instead to shrink the allowed error from 16.
You should be able to describe update and estimate, prove the estimate is never below the truth, derive 2F₁/w and 2⁻ᵈ from linearity and Markov, say which parameter moves which figure, and explain why an additive bound is no use for a rare key.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.