DynamicLogLog: Faster, Smaller, and More Accurate Cardinality Estimation
For applications requiring cardinality estimation (e.g., networking, databases), DLL offers a drop-in replacement that is smaller, faster, and more accurate, addressing a known bottleneck in HLL.
DynamicLogLog (DLL) reduces memory by 33% (4 vs 6 bits per bucket) and eliminates HyperLogLog's 34% error spike, achieving 1.83% mean error with 1,024 bytes versus HLL's 1.84% mean and 34.1% peak error with 1,536 bytes, while also being 16-29% faster via an early exit mask.
Cardinality estimation - calculating the number of distinct elements in a stream - is a longstanding problem with applications from networking to bioinformatics. HyperLogLog (HLL), the prevailing standard, has a well-known 34% error spike in its transition region and requires 6 bits per bucket, with data structure size scaling as B*log(log(cardinality)). We present DynamicLogLog (DLL), which uses a shared exponent across all buckets, storing only relative leading-zero counts. This yields three benefits: (1) only 4 bits per bucket (33% memory reduction), (2) an early exit mask that rejects >99.9% of elements at high cardinality before any bucket access (16-29% faster than HLL), and (3) a flat error profile via Dynamic Linear Counting (DLC) and a Logarithmic Hybrid Blend that eliminates HLL's transition artifact. Squaring the maximum representable cardinality requires only a single additional bit of global state. At 2,048 buckets with 512k simulations, DLL4's hybrid estimate achieves 1.830% mean and 1.834% peak absolute error using 1,024 bytes, compared to 1.84% mean and 34.1% peak for HLL using 1,536 bytes. DLC achieves 1.90% mean without correction factors. DynamicUltraLogLog (UDLL6), a fusion of DLL and UltraLogLog, achieves ULL-level accuracy at 75% of the memory. History-corrected variants (Hybrid+n) and Layered DLC (LDLC) provide further improvements using per-state correction tables and anti-phase error cancellation.