HyperLogLogLog++ - An Improvement of the HyperLogLogLog algorithm

Abstract

HyperLogLog (HLL) is the de facto standard probabilistic cardinality estimation algorithm due to its effective balance between memory usage, estimation accuracy, and computational efficiency. HyperLogLogLog (HLLL) is a lossless compression of the HLL sketch that preserves its accuracy and mergeability while reducing the memory footprint. This compression, however, increases the computational cost of update operations. This thesis presents HyperLogLogLog++ (HLLL++), an algorithmic and implementation-level enhancement of HLLL that aims for better trade-offs between memory efficiency, estimation accuracy and runtime performance. HLLL++ introduces four main improvements: a dense-array sparsity indicator for faster updates, a compressed sparse dictionary using Elias-Fano and Huffman encoding, integration of Ertl’s Maximum Likelihood Estimation (MLE) estimator, and a bootstrapped base value selection strategy that replaces exhaustive search. Experimental evaluation on synthetic sketches shows that the MLE estimator achieves lower bias and slightly lower variance than the original HLL estimator, while introducing a moderate runtime overhead that becomes relatively smaller as the number of registers increases. The implemented sparse dictionary in HLLL++ reduces memory usage by up to approximately 63% compared to HLLL’s sorted packed dictionary for large sketches, and the bootstrapped base selection strategy matches exhaustive search while providing speedups of up to 7.86× during periodic rebasing. Overall, HLLL++ improves the space, time and accuracy trade-off relative to HLLL while maintaining the correctness and mergeability of HLL algorithm.