Everything about HyperLogLog
Approximate distinct counting algorithm
HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the exact cardinality of the distinct elements of a multiset requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. Probabilistic cardinality estimators, such as the HyperLogLog algorithm, use significantly less memory than this, but can only approximate the cardinality. The HyperLogLog algorithm is able to estimate cardinalities of > 109 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory. HyperLogLog is an extension of the earlier LogLog algorithm, itself deriving from the 1984 Flajolet–Martin algorithm. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: HyperLogLogA 5-minute orientation
- Skim a recent paper: Using HyperLogLog to Prevent Data Retention in Social Media Streaming Data AnalyticsInfluential work since 2022
- Read the landmark paper: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithmCited 367 times
- Go sideways: Count-distinct problemA closely related topic
- Go sideways: Flajolet–Martin algorithmA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Dashing: fast and accurate genomic distances with HyperLogLog
How can sliding HyperLogLog and EWMA detect port scan attacks in IP traffic?
Security of HyperLogLog (HLL) Cardinality Estimation: Vulnerabilities and Protection
Expected 10-anonymity of HyperLogLog sketches for federated queries of clinical data repositories
Efficient estimation of inclusion coefficient using hyperloglog sketches
UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting
Erasable Virtual HyperLogLog for Approximating Cumulative Distribution over Data Streams
🆕 Influential since 2022
đź“š Books worth reading
Open Library didn't respond; try again in a moment.
đź”— Related topics
- Count-distinct problem In computer science, the count-distinct problem (also known in applied mathematics as the cardinality estimation problem) is the problem of finding the…
- Flajolet–Martin algorithm The Flajolet–Martin algorithm is an algorithm for approximating the number of distinct elements in a stream with a single pass and space-consumption logarithmic…
- Streaming algorithm In computer science, streaming algorithms process input data streams as a sequence of items, typically making just one pass (or a few passes) through the…
- Approximate counting algorithm The approximate counting algorithm allows the counting of a large number of events using a small amount of memory. Invented in 1977 by Robert Morris of…
- Count–min sketch In computing, the count–min sketch (CM sketch) is a probabilistic data structure that serves as a frequency table of events in a stream of data. It uses…
- MinHash In computer science and data mining, MinHash (or the min-wise independent permutations locality-sensitive hashing scheme) is a technique for quickly estimating…
- Set (abstract data type) In computer science, a set is an abstract data type that can store distinct values, without any particular order. It is a computer implementation of the…
- Flajolet Lecture Prize The Philippe Flajolet Lecture Prize is awarded to for contributions to analytic combinatorics and analysis of algorithms, in the fields of theoretical…