UltraLogLog

A drop-in HyperLogLog alternative (Otmar Ertl, 2023) that estimates distinct counts from the same 2p single-byte registers, but squeezes ~24-28% more accuracy out of them by letting each hash partially improve a register instead of only replacing it with a hard maximum.

How it works

Classic HyperLogLog quantizes every hash down to a single integer, ρ (the position of the leftmost 1-bit), and a register just keeps the hard MAX ρ it has ever seen. That is coarse: two hashes that differ a lot in rarity but happen to share the same ρ look identical to the register, and whichever one "loses" contributes nothing at all.

UltraLogLog instead treats each hash as evidence about a continuous quantity, rank = -log2(u) for a uniform u derived from the hash, and discretizes it onto a much finer scale (q sub-levels per doubling) using stochastic rounding: the fractional part of the level is resolved by an independent coin flip drawn from another slice of the hash, rather than always rounding down. Whether a register advances on a given update ("probabilistic promotion") depends on where the true rank falls relative to the nearest sub-level boundary, not just on crossing a hard power-of-two threshold like classic ρ does.

Because the rounding is unbiased, a fixed-width register byte ends up carrying meaningfully more information about the underlying distribution than a plain integer ρ does. Combined with a maximum-likelihood estimator (instead of HyperLogLog's harmonic mean), that extra information is what lets UltraLogLog match HyperLogLog++'s accuracy using roughly a quarter less memory - or equivalently, beat it at the same memory budget.

One subtlety the demo makes visible: a register storing the raw discretized level would let 0 mean both "never touched" and "observed the smallest possible level", which is ambiguous (classic HyperLogLog never has this problem because ρ is always ≥ 1). This implementation shifts stored levels by one so that register value 0 unambiguously means "never touched", and corrects the likelihood's boundary case to match.

Interactive demo

Registers (m)16
True distinct count0
Estimate0.00
Error vs. truthn/a

Standard error for this precision: ±22.00%. Add more distinct items to see the estimate converge toward the true count.

No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new UltraLogLog(p, q = 4)Allocate 2^p single-byte registers with q sub-levels per doubling.O(2^p) space
add(item): UllStepStochastically discretize the hash's rank and probabilistically promote the item's register.O(1) time
estimate(): numberCardinality estimate via maximum-likelihood search over registers.O(2^p) time per estimate
standardError(): numberApproximate relative standard error, ~0.88/√m.O(1)
merge(other): voidCombine two same-precision sketches in place via per-register max.O(2^p) time
clear(): voidReset all registers to empty.O(2^p) time

References

Original papers

Library implementations

Real-world use cases