You have 16 kilobytes per symbol and must estimate both the number of distinct counterparties and the message rate of the heaviest client. State the two sketches you would use and give the error each one guarantees at that memory budget.

You have 16 kilobytes per symbol and must estimate both the number of distinct counterparties and the message rate of the heaviest client. State the two sketches you would use and give the error each one guarantees at that memory budget.

Approach: Distinct counting and frequency estimation need different sketches. Substitute the memory budget into each error formula and state the direction of the bias.

HyperLogLog for distinct counts at 0.81% standard error, and a count-min sketch of width 2719 and depth 7 for frequencies, with error at most 0.001 * N and confidence 0.999. HyperLogLog stores m registers holding the maximum count of leading zeros seen per bucket, with relative standard error 1.04/sqrt(m). Taking m = 2^14 = 16384 registers at 5 bits each is about 10 kilobytes and gives 1.04/128 = 0.0081, so a cardinality of one million is reported to within roughly 8000 either way. Count-min hashes each key into d rows of w counters, adds the count in each row and reports the minimum. Its guarantee is that the estimate never underestimates and exceeds the truth by more than eps * N with probability at most delta, where w = ceil(e/eps) and d = ceil(ln(1/delta)). Setting eps = 0.001 and delta = 0.001 gives w = 2719 and d = 7, about 76 kilobytes at 4-byte counters, so the budget forces either 2-byte counters or a wider eps. The one-sided error is what makes the minimum across rows the right estimator, since every collision can only add.

Follow-up: How do you merge sketches from 40 machines and what property must each structure have for that to be exact?

Key concepts: hyperloglog, count-min sketch, standard error, one-sided error.