HyperLogLogs

HyperLogLog is a probabilistic algorithm for estimating the cardinality of a set, i.e., the number of distinct elements, in large data streams or distributed computations. It achieves memory efficiency by hashing each element to a fixed-size bit string and updating a small, fixed set of registers rather than storing elements. The hash is divided into two parts: an index that selects a register and the value that records the position of the first 1 bit in the remaining bits. Each register stores the maximum observed position, and the final cardinality estimate is computed from these registers using a scaled harmonic mean.

The practical strength of HyperLogLog lies in its space-time efficiency and mergeability. With m registers (where m is a power of two), the standard error is approximately 1.04 divided by the square root of m. Increasing the number of registers reduces error but increases memory usage linearly. HyperLogLog sketches from separate sources can be merged by taking the element-wise maximum of corresponding registers, enabling distributed counting without transferring all data. The estimator is unbiased for mid to large cardinalities, with bias corrections for small cardinalities.

HyperLogLog++ is a widely used improvement that reduces bias, provides better small-cardinality handling through linear counting, and maintains mergeability. Real-world deployments include implementations in databases and data processing systems, such as Redis (PFADD, PFCOUNT, PFMERGE) and various analytics engines. Typical memory footprints are small even for very large cardinalities, making HyperLogLog useful for web analytics, network telemetry, fraud detection, and stream processing. Limitations include the inability to obtain exact counts, reliance on a good hash function, and reduced accuracy for very small sets unless bias corrections are applied.