HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

By Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier. 2007

893 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/36ddd38d69c3df3896ce3033c8f5af03141bede1

How researchers see this paper

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

Citations in the corpus

HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm (2013, methodology): “In Section 4 we present the HyperLogLog algorithm from [7] that is the basis of our improved algorithm.”
Goods: Organizing Google's Datasets (2016, methodology): “To find potential keys, we use the HyperLogLog algorithm [15] to estimate cardinality of values in individual fields and combinations of fields and we compare this cardinality with the number of records to find potential keys.”
The Effect of Recommendations on Network Structure (2016, methodology): “Given the size of the network, exact computation is prohibitively expensive, and so we used the HyperLogLog algorithm [11] to create a sketch of each user’s set of followers.”
KrakenUniq: confident and fast metagenomics classification using unique k-mer counts (2018, methodology): “gorithm (HLL) [10], which is well suited for k-mer counting [14], keeps a summary or sketch of the data that is sufficient for precise estimation of the cardinality and requires only a small amount of constant space to estimate cardinalities up to billions.”
Smart Cities: A Survey on Data Management, Security, and Enabling Technologies (2017, methodology): “Hyperloglog [244] is an algorithm used to count the dis-”
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”
Decentralized and Adaptive K-Means Clustering for Non-IID Data Using HyperLogLog Counters (2020, methodology): “HyperLogLog (HLL) counters are extremely useful for big data as they dramatically decrease the amount of memory needed to approximate the exact cardinality estimation compared to other data structures [6].”
Cardinality Estimators do not Preserve Privacy (2018, methodology): “The merge operation in Deﬁnition 4 is well-deﬁned, i.e., it does not depend on the choice of E .”
Impala: A Modern, Open-Source SQL Engine for Hadoop (2015, methodology): “6 We use the HyperLogLog algorithm [5] for distinct value estimation.”
The khmer software package: enabling efficient nucleotide sequence analysis (2015, methodology): “This script uses the HyperLogLog algorithm to provide a probabilistic estimate of the number of unique k-mers in a data set with a guaranteed upper bound 14 .”
Continual Learning in Practice (2019, methodology): “If the only quantity of interest is the number of unique/distinct items (cardinality estimation), the HyperLogLog algorithm [15] and its derivatives compute this, where the cost only depends on log of log of quantity computed.”
An optimal algorithm for the distinct elements problem (2010, background): “Up until this point, this information being kept is identical as in the LogLog [16] and HyperLogLog [20] algorithms (though our analysis will not require that the hash functions be truly random).”