HyperLogLog estimates the number of distinct elements in a data stream using a fixed-size sketch. The sketch stores the maximum leading-zero count per bucket — a lossy summary that trades individual element tracking for bounded memory. It works. But the sketch itself is compressible: the bucket values are not uniformly distributed, and standard compression should recover the redundancy.
The Huffman-Bucket Sketch (arXiv:2603.10930) compresses HyperLogLog losslessly to optimal O(m + log n) bits while preserving mergeability and amortized constant-time updates. The key insight is that the Huffman tree only needs rebuilding O(log n) times across the entire stream — roughly when the estimated cardinality doubles. Between doublings, the distribution of bucket values is stable enough that the same code works.
The structural observation: compression and computation can be made concurrent without mutual interference, provided the compression adapts at a coarser timescale than the computation. The sketch updates at every element; the encoding updates at every doubling. The two rates differ by a factor of n/log(n), and this separation is what makes the scheme practical. The compression doesn't need to track the data — it only needs to track the sketch's statistical regime, which changes logarithmically slower than the data itself.