HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm

By Stefan Heule, Marc Nunkesser, Alexander Hall. International Conference on Extending Database Technology, 2013

347 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Automating Large-Scale Data Quality Verification (2018, methodology): “…and might involve re-partitioning or sorting the data, our system provides approximations of metrics such as quantiles in the form of ApproxQuantile (computed via an eﬃcient online algo-rithm [15]) or ApproxCountDistinct for estimating the number of distinct values with a hyperloglog sketch [21].”
KrakenUniq: confident and fast metagenomics classification using unique k-mer counts (2018, methodology): “[11] that has the much higher effective precision p′ of 25 by encoding each index and count in a vector of 4-byte values (see Fig.”
Cardinality Estimators do not Preserve Privacy (2018, background): “Moreover, Hyper-LogLog++ [29] has a sparse mode that stores full hashes when the sketch contains a small number of values; this makes intersection attacks even easier.”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, methodology): “To name a few, these sketch-based algorithms include probablistic counting [34], MinCount [8], LogLog [21] and its variants HyperLogLog [33], and HyperLogLog++ [39]. first work on privacy-preserving cardinality estimators is [66]; they proposed a cardinality estimation mechanism in a distributed set”
Continual Learning in Practice (2019, methodology): “A version called HyperLogLog++ [17] uses 64-bit hash functions instead of 32-bit, which reduces the probability of collisions.”