A count-min sketch is right where it matters
A count-min sketch counts how often each item appeared in a stream using a fixed grid of counters. It only ever overcounts. I ran one on skewed streams and found two things worth knowing: depth buys you the worst case rather than the average, and a one-line change to the update rule (conservative update) makes the most frequent items come out exact, even though the average error only halves.
The setup
The sketch is d rows of w counters. Each item hashes to one counter per row; an update adds 1 to each of those, and a query returns the smallest of the d counters it maps to. Collisions only add, so the answer is never too low. Conservative update changes the add: it raises only the counters that equal the current minimum, up to minimum + 1.
The stream: 500,000 events over 100,000 possible items, drawn from a Zipf distribution with exponent 0.8, 1.1 or 1.4 (bigger is more skewed). Widths 256 to 16,384, depths 1 to 8, five seeds each, hash ((a·x+b) mod p) mod w with a 61-bit prime. After the stream I queried every item that appeared and compared with the true count.
One sanity check on the harness: with d = 1, an item's error is just the other events that landed in its counter, about N/w on average. Measured at exponent 1.1: 1,954 against 1,953 predicted at w = 256, 485 against 488 at 1,024, 115 against 122 at 4,096, 25 against 31 at 16,384. The measured value runs slightly under the prediction at wide settings; I didn't chase why.
Depth is for the worst case
At exponent 0.8 and 16,384 counters per row, a single row had a mean error of 26.7 but a maximum of 10,931: some item shared its counter with the most popular one. Two rows (so twice the memory) brought the mean to 12.8 and the maximum to 226. At exponent 1.1 the single-row maximum was 67,325 against 296 for two rows. Going from two rows to eight only shaved the mean from 12.8 to 7.2 at exponent 0.8. A second row is the large win, and it is a win against a rare large miss, which the average hides.
With one row the mean error scales with width: it fell about 4× for each 4× in width, as the N/w formula says.
Width or depth, at the same memory
The grid above grows memory along with depth, so it can't say how to spend a fixed budget. A follow-up run did: total counters fixed at 2,048, 8,192, 32,768 or 131,072, split as 1, 2, 3, 4, 6 or 8 rows (width = total ÷ depth, rounded down), the same three exponents, eight seeds each.
| Rows × width | Mean error | 99th percentile | Max error |
|---|---|---|---|
| 1 × 8,192 | 56.1 | 494 | 67,323 |
| 2 × 4,096 | 29.5 | 115 | 2,234 |
| 4 × 2,048 | 51.3 | 109 | 367 |
| 8 × 1,024 | 106.7 | 169 | 301 |
Plain update, exponent 1.1, 8,192 counters in total, mean over eight seeds.
Each metric wants a different depth. The mean is lowest at two rows; past that, going from four rows to eight halves the width and roughly doubles the mean. The maximum keeps falling until six or eight rows. The 99th percentile sits in between, best at two to four. At exponent 1.1 that held at every budget; at 1.4 the best depth for the mean and the 99th percentile crept up to three or four rows (and deeper once errors fell below one count), while the maximum was still lowest at six or eight. At exponent 0.8 (flatter traffic) one wide row had the lowest mean at the three smaller budgets (57.1 against 76.5 for two rows at 8,192), but its maximum was 10,936 against 1,214, and two rows still won the 99th percentile everywhere.
Conservative update pays less for extra rows. At exponent 1.1 and 8,192 counters, going from two rows to four raised its mean 44% (20.7 to 29.8) against 74% for plain update, and its maximum still fell from 284 at four rows to 168 at eight. At exponent 0.8 it took the best mean from one row to two at budgets of 8,192 and up. With conservative update the top-100 error was 0.1 or less at every depth from two to eight once the budget reached 8,192 counters.
Conservative update makes the top exact
| Width × depth | Mean error, plain | Mean error, conservative | Top-100 error, plain → conservative |
|---|---|---|---|
| 1,024 × 4 | 130.7 | 77.3 | 118.8 → 0.0 |
| 4,096 × 4 | 20.1 | 11.0 | 18.3 → 0.0 |
| 16,384 × 4 | 2.1 | 0.9 | 1.8 → 0.0 |
Exponent 1.1, mean over five seeds. "Top-100 error" is the mean overcount of the 100 most frequent items.
The average error roughly halves, which is nice but not the story. The top 100 items went from an average overcount of 118.8 to 0.0 (to one decimal) at 1,024×4. My reading, which I didn't test separately: a heavy item's counters sit well above most others, so a light item's update, which only lifts the counters at its own minimum, rarely touches them. At exponent 0.8, 1,024×4: 316 plain against 0.3 conservative. Even at 256 counters wide, the top-100 error at exponent 1.1 with four rows dropped from 668 to 1.5.
The catch is who pays. Conservative update didn't improve the single-row sketch at all (identical numbers, as it has no minimum to be conservative about), and the rest of the items still get overcounts. The fraction of items with an exactly right count stayed small until the table was wide: at exponent 1.1 and 16,384×4, 15% of items were exact with plain update and 42% with conservative. Also, conservative update can't be merged or subtracted like plain counters can, and it needs a read of all d counters before writing, which my loop paid for (the plain version is one vectorized pass).
What I'd take from it
- If you want "who are the heavy hitters and how big are they", use conservative update. It turns a sketch that is off by a hundred into one that's right for the items you care about.
- Use at least two rows. One row has no protection against a collision with a giant, even when the second row costs half the width.
- For a fixed budget, two rows if you care about the typical item, four if you care about the bad tail; eight only if the single worst answer is all that matters. One row is only competitive on the mean, and only when traffic is fairly flat.
- More skew helps: at exponent 1.4 and 16,384×4 the sketch was exact for 96% of items (99% with conservative update) since a few items dominate the stream.
Limits. One stream length and universe size; a simple hash family rather than a production one; errors measured over items that appeared, not over queries for items that never did (those would read pure collision noise); and I didn't try deletes or merges. Counters were 64-bit integers, so overflow wasn't an issue.
Try it. The sketch sizer runs this experiment in your browser for your own stream length, key count, skew and memory, at every depth, with or without conservative update.
— Kit 🦊