ExaLogLog

UltraLogLog's successor (Otmar Ertl, 2024; EDBT 2025): same commutative, idempotent, O(1)-insert contract as HyperLogLog, but registers that remember a bit more than just their maximum - which buys up to 43% less space than 6-bit-register HyperLogLog for the same estimation error, while still counting all the way up to the exa-scale.

How it works

UltraLogLog gets a finer-than-integer register scale by treating each hash as evidence about a continuous rank and stochastically rounding it onto a base-b grid, using a second, independent hash draw as the rounding coin flip. ExaLogLog reaches the exact same kind of grid without the second hash: it slices t extra bits straight out of the same hash and folds them into the update value, k = nlz · 2^t + tBits + 1, where nlz is a leading-zero count - exactly what classic HyperLogLog's ρ already is. Because every block of 2t consecutive k values shares the same nlz, they carry identical total probability mass, which is what makes this bit-slicing trick statistically equivalent to a base b = 2^(1/2^t) discretization - reached here deterministically, with one hash call instead of two.

The bigger change is what a register stores. UltraLogLog (like HyperLogLog) only ever keeps the hard maximum it has seen - the moment a bigger value arrives, whatever the register used to hold is gone for good. ExaLogLog splits each register into two parts: q = 6 + t bits for the maximum update value u (small, and notably independent of precision p - nlz is bounded by roughly 64 regardless of how many registers exist, which is exactly the mechanism that lets a small, fixed-width register keep tracking cardinalities all the way to the exa-scale), plus d extra "flag" bits that each remember whether some update value in the recent window [u-d, u-1] was also observed at some point, even though it never became the max.

Those flag bits are basically free extra evidence for the maximum-likelihood estimator: instead of only knowing "the largest value seen was u," it also gets to know "and these specific smaller values were seen too, while these others definitely weren't." That is more signal per register bit than UltraLogLog's max-only registers provide, which is what lets ExaLogLog beat UltraLogLog's already-improved space efficiency - up to 43% less space than classic 6-bit-register HyperLogLog for the same error, versus UltraLogLog's ~24-28%.

Merging two sketches still works register-by-register, but now has to reconcile two (max, flags) pairs instead of one number: the register with the smaller max gets folded entirely into the other's flag window (its own max becomes a "recently observed smaller value," and its flags get re-aligned to the new reference point) - the very same fold operation add() uses whenever a bigger update value knocks the current max down into the flag window.

Interactive demo

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

Standard error for this configuration: ±15.88%. Register width: 16 bits (8 for the max update value + 8 flag bits). 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 ExaLogLog(p, t = 2, d = 8)Allocate 2^p registers, each (6+t)+d bits wide: t controls resolution, d controls the flag-bit memory window.O(2^p) space
add(item): EllStepDeterministically bit-slice the hash into an update value and advance the register's max or set a flag bit.O(1) time
estimate(): numberCardinality estimate via maximum-likelihood search over registers' (max, flags) pairs.O(2^p) time per estimate
standardError(): numberApproximate relative standard error, improving with both t and d.O(1)
merge(other): voidCombine two same-shape sketches in place by folding the smaller-max register into the larger's flag window per bucket.O(2^p) time
clear(): voidReset all registers to empty.O(2^p) time

References

Original papers

Library implementations

Real-world use cases