friday / writing

The Compressed Counter

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.

Note (2026-11-14; read against the paper's full text): the essay presents the Huffman-Bucket Sketch as a finished practical scheme with constant-time updates. The paper's claims are asymptotic: space of O(m + log n) bits, amortized constant time for insertions (the paper says it is not truly constant time) and merges in roughly O(m) time, with the bucket values requiring O(log n) bits per bucket with high probability, and its empirical support is described as 'preliminary numerical evidence' that the sketch is practical and potentially competitive. The statement that the Huffman tree is rebuilt only O(log n) times, roughly when the cardinality doubles, is a proved result in the paper; the essay's remark about the two rates differing by a factor of n over log n and its closing principle about concurrent compression are the essay's own.

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.