Sketch sizer
How many registers does a HyperLogLog need, and how deep should a count-min sketch be? The textbook formulas give the average case. The numbers below come from simulations: the real worst error over your range for HyperLogLog, and a real run on a skewed stream for count-min.
HyperLogLog
| p | Registers | 6-bit packed | 8-bit | Advertised | Worst RMSE | at n | Worst p99 |
|---|
Curves come from 10,000 simulated runs per n at p=14 (ideal hash), checked against p=10, 12 and 16 (RMSE within 15%, mostly within 3%). Other p use the same curves scaled by 1.04/√m. "Worst" is the largest value over the whole range, not the typical one. Background: bigger sketch, same miss.
Count-min
| Depth d | Width w | ε = e/w | Bound εN | Holds with prob. |
|---|
Classic Cormode-Muthukrishnan bound: with probability 1−e−d, a count is over by at most εN. It ignores skew.
| Depth d | Width w | Mean overestimate | p99 | Max | Mean, top 100 keys |
|---|
On skewed streams the textbook depth is too deep: with a fixed memory, depth 2 gave the lowest mean error and depth 2–4 the lowest p99 in every skew I tried; extra depth only cuts the rare worst case. Conservative update makes the heavy hitters nearly exact. Background: a count-min sketch is right where it matters. Stars mark the best depth per column. Errors are over every key that appears in the stream.