HyperLogLog (Cardinality Estimation)
1. Overview
A. Definition
HyperLogLog (HLL) is a probabilistic data structure and algorithm that approximately estimates the number of distinct elements — the cardinality (number of unique elements) — in a large data stream using near-constant memory (a few KB) without storing the elements themselves, inferring the set's size from a statistic: the maximum number of leading zeros observed in each element's hash value.
HyperLogLog answers the question "how many distinct values are in this set (COUNT DISTINCT)?" To count exactly you must keep every unique element seen so far in a set (HashSet), so memory grows in proportion to the element count n (O(n)) and explodes. HLL instead stores no elements and leaves only a trace — "how rare a hash pattern has appeared" — in a fixed-size array of registers. As a result, whether there is 1 element or a billion, memory stays constant (e.g. about 12 KB), at the cost of a relative error of a few percent. Unlike the [[bloom-filter]] discussed earlier, which approximates "membership," HLL approximates "count," making them complementary probabilistic data structures.
HLL's properties can be summarized in three points. First, memory is fixed regardless of input size (constant space). Second, per-element processing is just one hash and one register update, so insertion is O(1) and very fast. Third, two or more sketches can be merged losslessly, fitting naturally into distributed aggregation. In return, the result is approximate, and it is unsuitable for deleting a specific element or computing an exact intersection. This bundle of trade-offs determines where HLL applies.
B. Background and Necessity
As web, mobile, and IoT environments have grown, unique-count aggregations such as "number of unique visitors," "number of distinct search terms," "number of distinct IPs that connected," and "deduplicated event count" have become key metrics. Yet this operation is inherently expensive. An exact COUNT DISTINCT must remove duplicates, so it has to remember every value seen so far, and counting unique users across billions of log entries per day requires several GB to tens of GB of memory. In dashboards and ad systems that must aggregate thousands of metrics simultaneously and in real time, this cost translates directly into infrastructure cost and latency.
HyperLogLog engineers around the business reality that "an exact number is unnecessary; ±2% is good enough." Whether unique visitors are 1,000,230 or 1,000,235 does not affect decisions, so trading a small error for saving thousands to millions of times the memory is reasonable. In particular, HLL has the decisive advantage that merging is easy: results aggregated separately by region, time, or server can be combined losslessly to obtain the "total unique count." Thanks to this additivity, it has effectively become the standard in distributed and streaming environments.
Understanding why exact aggregation is fundamentally expensive clarifies HLL's value. COUNT DISTINCT must determine "have I already seen this value?" every time, so to be exact it must either keep all unique values in memory (HashSet) or sort/shuffle the whole set (distributed aggregation). In a horizontally scaling environment this full state hits two walls at once: per-node memory limits and network shuffle cost. HLL sidesteps these walls with the insight that if all you need is the single statistic "unique count," there is no reason to remember every element. This is like embedding into a data structure the statistical idea of estimating a population from a sample rather than a full census.
2. How It Works and the Intuition
The core intuition of HyperLogLog is analogous to coin tossing. A bit string that has passed through a fair hash function looks like a random sequence in which each position is a uniform, independent 0/1. The probability that a bit string starts with k consecutive zeros from the front is (1/2)^k. Therefore, if you have "seen at least once a pattern with k consecutive leading zeros," you can estimate that you have observed roughly 2^k distinct values — the rarer the pattern, the more evidence that many were drawn.
To put this intuition in everyday terms, it is like guessing that you must have tossed a coin quite a few times if you witnessed "ten heads in a row." The important point is that this estimate is unaffected by duplicates. Even if the same element arrives 100 times, its hash value is identical, so the leading-zero count does not change; thus HLL captures not "how many times something arrived (frequency)" but only "how diverse the patterns that appeared were (uniqueness)." This very property is the fundamental principle that lets it filter duplicates and count only unique elements without storing elements. However, a single observation alone has far too much variance (since it can only estimate in powers of two) to use as is, and the bucket averaging below is essential.
flowchart LR
X["input element x"] --> HASH["hash function h(x) → 64 bits"]
HASH --> SPLIT["top b bits: register index j"]
HASH --> REST["remaining bits: leading-zero count +1 = ρ"]
SPLIT --> REG["register M[j]"]
REST --> UPD["M[j] ← max(M[j], ρ)"]
UPD --> REG
The actual algorithm uses stochastic averaging to reduce estimation variance. It picks one of 2^b = m buckets (registers) using the top b bits of the hash, computes ρ from the remaining bits as the leading-zero count plus one, and stores only the running maximum in that register. That is, each register remembers "the strength of the rarest pattern among the values that fell into this bucket." Even if one element arrives many times, the maximum of ρ does not change, so duplicates are automatically ignored — which is why only the unique count is counted.
The final cardinality is estimated using the harmonic mean of the m register values. Using the harmonic mean instead of the arithmetic mean was the key improvement that lifted LogLog to HyperLogLog, because the harmonic mean suppresses the influence of abnormally large register values (outliers) and greatly lowers estimation variance.
flowchart TB
A["m registers M[0..m-1]"] --> B["Z = (Σ 2^(-M[j]))^(-1) : harmonic-mean term"]
B --> C["raw E = alpha_m · m^2 · Z"]
C --> D{"estimate correction"}
D -->|"when E is small (E ≤ 2.5m)"| E1["re-estimate with LinearCounting"]
D -->|"middle range"| E2["use raw E"]
D -->|"very large (near 32-bit limit)"| E3["upper-bound correction"]
E1 --> OUT["final cardinality estimate"]
E2 --> OUT
E3 --> OUT
The estimation formula takes the form E = α_m · m² · (Σ_{j} 2^(−M[j]))^(−1), where α_m is a constant that corrects the estimate's bias (for large m, α_m ≈ 0.7213/(1+1.079/m)). However, when the element count is too small relative to the register count m (many registers remain empty at 0), this formula produces large error, so in this small-cardinality range it switches to Linear Counting, which uses the "fraction of registers that are 0," to correct the estimate.
A. Step-by-Step Insertion Example
Making the operation concrete with a small example sharpens the intuition. Suppose we have only m = 4 registers (indexed by the top 2 bits). All registers are initialized to 0. If hashing element x gives top 2 bits 10 (= bucket 2) and remaining bits 0010…, then there are 2 leading zeros in the remainder, so ρ = 2+1 = 3 and M[2] ← max(0, 3) = 3. If the next element y has top 2 bits 00 (bucket 0) and remainder 1…, then there are 0 leading zeros, so ρ = 1 and M[0] ← 1. Even if the same x arrives again, M[2] stays max(3,3) = 3, so duplicates are naturally absorbed. In this way each bucket cumulatively remembers only "the strength of the rarest pattern" among the values it received.
The key is that one bucket's value is proportional to the logarithm of that bucket's element count. That is why the data structure's name contains "Log," and because a register holds only the leading-zero count (= a log value), a single register needs only 5–6 bits. Combining the log values of m buckets via the harmonic mean yields the logarithm of the total cardinality, which is then multiplied by a correction constant to recover the actual estimate. In short, HLL's design philosophy is to reduce the large variance of a single observation to the 1/√m level by collecting the statistical evidence "saw a rare pattern = drew many" across m buckets in a distributed way and averaging it.
3. Accuracy/Memory Design and the Redis Case
HLL's relative standard error is given as about 1.04/√m with respect to the register count m. That is, to double the accuracy (halve the error) you must quadruple the registers, so memory and accuracy form a squared-relationship trade-off. It is no exaggeration to say this relationship is the whole of HLL design.
Concrete numbers make the design sense clear. Assuming a 64-bit hash, the leading-zero count stored in each register is at most about 50-odd, so 6 bits suffice. With m = 2^14 = 16,384 registers, memory is 16,384 × 6 bits ≈ about 12 KB, and the standard error is 1.04/√16384 = 1.04/128 ≈ about 0.81%. This is exactly the configuration of Redis's HyperLogLog — it counts unique values at the scale of billions with under 1% error using just 12 KB. Doing the same work with an exact set would take tens of bytes per element and require several GB, so this is a memory saving of hundreds of thousands of times or more.
It is important to understand precisely what "standard error 0.81%" means. This is a one-sigma (1σ) expected error, not a guaranteed upper bound. That is, when the true value is 10 million, the estimate falls within ±about 80,000 (0.81%) on average, but it can rarely deviate up to 2–3 times that. In practice, interpret it conservatively as "roughly ±1%," and if a metric is highly sensitive, it is safer to increase m for headroom. Also, a key design point is that increasing the number of bits per register has almost no effect on accuracy and only the register count m governs accuracy — the bit count merely sets the maximum leading-zero count (= maximum scale) that can be held.
Practical parameters usually pick the log register count b (= log₂m) between 4 and 16. If b is small (e.g. b=10, m=1024), memory drops to a few hundred bytes but error grows to the 3% range; if b is large (e.g. b=16, m=65536), memory rises to 48 KB but error shrinks to 0.4%. How precisely each metric is operated is decided by this choice of b, and in a system maintaining thousands of metrics at once, differentiated allocation of b governs the overall memory budget.
| Category | Exact set (HashSet) | HyperLogLog | Comparison perspective |
|---|---|---|---|
| Memory | O(n), proportional to element count | O(1), fixed (e.g. 12 KB) | HLL uses 12 KB even for a billion |
| Result | Exact | Approximate (standard error ~0.81%) | Tolerate small error |
| Merge | Recompute after union | Instant merge via per-register max | HLL favorable for distribution |
| Deletion | Possible | Impossible (add/merge only) | HLL is aggregation-only |
| Intersection | Exact | Approximate via inclusion-exclusion (large error) | HLL weakness |
As the table shows, HLL's greatest practical advantage is the simplicity of merging. To combine two HLLs you only take the larger value (max) between registers at the same index, which satisfies the commutative and associative laws and fits perfectly into the reduce stage of MapReduce/streaming aggregation. For example, if 100 web servers each build an HLL of their own traffic and the center merges the 100 via max, the total unique visitors emerge, and this process needs no gathering of raw logs in one place, greatly reducing network and storage cost. By contrast, the intersection (common user count) cannot be obtained directly from HLL alone and must be approximated by the inclusion-exclusion principle, where error accumulates, so if intersection is central you must combine it with other techniques such as MinHash.
4. Comparison with Similar Techniques and Its Evolution: HyperLogLog++
HyperLogLog started from the 1984 Flajolet–Martin algorithm, evolved to LogLog in 2003 and to HyperLogLog proposed by Flajolet et al. in 2007, and reached its peak in HyperLogLog++ (HLL++), improved by Google in 2013 for large-scale practical use. Each stage is a history of engineering improvement toward "how to further reduce error with the same memory."
HLL++'s key improvements are threefold. First, extending the hash from 32 bits to 64 bits practically eliminated the hash-collision (upper-bound saturation) problem that arose at very large cardinalities beyond billions. Second, it raised accuracy by correcting, with a pre-measured empirical bias correction table, the large bias the original HLL showed in the small-cardinality range. Third, because when the element count is small most of the 16,384 registers are empty and memory is wasted, it initially stores observations only in a sparse representation and switches to dense registers as it grows, thereby saving even more memory at small cardinalities. This HLL++ has become the basis of commercial analytics engines today, such as Google BigQuery's APPROX_COUNT_DISTINCT, Presto/Trino's approx_distinct, Apache Druid, and Elasticsearch's cardinality aggregation.
| Algorithm | Appeared | Averaging method | Relative error | Characteristics |
|---|---|---|---|---|
| Flajolet–Martin | 1984 | Single bitmap | Large | First probabilistic counting |
| LogLog | 2003 | Arithmetic mean | 1.30/√m | A few bits per register |
| HyperLogLog | 2007 | Harmonic mean | 1.04/√m | Variance greatly reduced |
| HyperLogLog++ | 2013 | Harmonic mean + correction | 1.04/√m (low-range improved) | 64-bit, bias correction, sparse representation |
A. Distinguishing Roles from Neighboring Probabilistic Data Structures
HLL is only one axis of the "probabilistic sketch" family, and the choice differs when the question differs. To avoid confusion, distinguish them by "what is being approximated." A Bloom filter approximates membership ("is this value in the set?"), HyperLogLog approximates cardinality ("how many unique elements are there?"), Count–Min Sketch approximates frequency ("how many times did this value appear?"), and MinHash/Theta Sketch approximate similarity/intersection ("how much do two sets overlap?"). If you map the question wrongly, no amount of tuning will yield the answer you want.
| Sketch | Approximation target | Typical query | Relation to HLL |
|---|---|---|---|
| Bloom filter | Membership | "have I seen it?" | Complementary (existence) |
| HyperLogLog | Unique count | "how many kinds?" | This topic |
| Count–Min Sketch | Frequency | "how many times?" | Complementary (frequency) |
| MinHash/Theta | Intersection/similarity | "how much overlap?" | Complements HLL's weakness |
In practice these are used in combination. For example, in traffic monitoring one filters new IPs with a Bloom filter, counts unique IPs with HLL, and tracks the top traffic IPs (heavy hitters) with Count–Min Sketch. Because each sketch shares the common design philosophy of approximating only a specific statistic with fixed memory, they are bundled together as the standard toolbox for large-scale stream analysis.
5. Deep Dive: Practical Application and Latest Usage Trends
HyperLogLog has become a basic feature of data platforms thanks to the broad demand for "unique counting where approximation is acceptable." As a representative case, Redis provides HLL through three commands — PFADD (add element), PFCOUNT (estimate query), and PFMERGE (merge) — and the prefix PF honors Philippe Flajolet, who invented HyperLogLog. It is used widely for real-time unique-visitor dashboards, unique client counts of API calls, unique reach aggregation of ad impressions, and so on.
To give a concrete sense of scale, suppose a service receiving 100 million requests per day aggregates the unique user count per minute. Exact aggregation must keep hundreds of thousands of unique IDs in memory per minute and combine a day's worth at midnight, but HLL needs only one 12 KB sketch per minute, and even gathering a full day (1,440 of them) is only about 17 MB, with the unique count for any interval obtained instantly by merging alone. The three costs — storage, computation, and query — are all reduced by hundreds of times or more at once.
In the data warehouse domain, HLL-based approximate functions solve the problem that an exact COUNT(DISTINCT) slows down on large tables due to shuffle/sort cost. For example, when the daily unique-user trend must be refreshed every hour over a log of tens of billions of rows, exact aggregation may take minutes to tens of minutes per query, whereas APPROX_COUNT_DISTINCT answers in seconds to tens of seconds with error around 1%. In metered cloud analytics environments, reducing scan and compute volume means reducing the bill directly, so the economic effect is immediate.
Additionally, the pattern of storing HLL sketches as intermediate artifacts is widely used. Instead of scanning the source table each time, if you build HLL sketches in advance per hour and load them into a separate table (or Redis keys), the daily/weekly/monthly unique counts are computed almost instantly by merging (PFMERGE/HLL_UNION) the sketches for that interval. This is a strategy impossible with exact aggregation, exploiting the fact that HLL "preserves aggregation results in a reusable, recombinable form." As a result, both batch recomputation cost and real-time query latency can be lowered at once.
Latest trends include ① embedding HLL in a time-series database to pre-aggregate unique counts at the roll-up stage, ② handling multidimensional unique aggregation — queries that combine different axes (region × device × campaign) — by building HLL sketches in advance and processing them via merge, and ③ research combining HLL with Differential Privacy by adding noise to HLL sketches for privacy enhancement. However, even though an HLL sketch itself holds no personally identifying information, there is discussion about the possibility of inferring, under certain conditions, membership in a small set, so careful design is required for sensitive data.
Multidimensional unique aggregation is a representative pattern where HLL's mergeability shines. For example, if an ad platform re-scans the source every time for a query that combines axes, such as "unique reach among Android users in the Seoul region of campaign A," cost explodes. Instead, if an HLL sketch is built and stored in advance for each fine-grained combination of (region, device, campaign), higher-level queries can answer instantly by max-merging the relevant sub-sketches. Because an exact COUNT DISTINCT would require redoing deduplication for each combination, making such pre-aggregation & roll-up impossible, HLL is structurally favorable for OLAP cube–style analysis.
Also, in streaming processing frameworks (Apache Flink / Spark Structured Streaming), the unique count per window is maintained as an HLL sketch and only the estimate is emitted when the window closes, binding the state size to a constant. In an infinitely arriving stream, exact aggregation grows the state without bound, but HLL is a fixed size per window, so memory does not explode even in long-running operation. This property of "summarizing an infinite stream with finite state" is another reason HLL became the standard sketch for real-time analysis.
6. Considerations and Implications
From a professional engineer's perspective, adopting HyperLogLog requires comprehensively considering the following.
Judge error tolerance and the metric's nature first. HLL is suitable for trend/scale metrics (unique visitors, reach) where ±1–2% error is acceptable. It is unsuitable for aggregations where accuracy is legally or financially required, such as billing, settlement, or regulatory reporting, and must always be paired with exact aggregation or an after-the-fact consistency-verification path.
Pre-size the register count m to the accuracy target. Since error is 1.04/√m and memory is proportional to m, halving the target error costs 4× the memory. Rather than applying high precision to all metrics, a design that differentiates precision (memory) by each metric's importance is cost-efficient.
Reflect the strength of mergeability in the architecture. HLL's max merge satisfies the commutative and associative laws, making it ideal for distributed collection and streaming aggregation. Building sketches per edge/server and merging them centrally avoids moving raw logs, so it combines well with [[edge-computing]] and data-locality strategies. However, sketches built with different m or hash cannot be merged, so parameter standardization must come first.
Confirm intersection/difference requirements early. HLL is strong at union (merge) but must approximate intersection via inclusion-exclusion, where error accumulates. If "the common user count of two segments" is a key metric, HLL alone is unsuitable, and you must consider combining MinHash, Theta Sketch, and the like.
Consider the no-deletion and privacy characteristics. HLL is an add/merge-only structure in which elements cannot be erased, so if excluding a specific user from aggregation (handling the right to withdraw, etc.) is needed, recomputation or a separate design is required. Also, even if a sketch holds no identifying information directly, in sensitive domains evaluate the re-inference risk and pair it with noise and access control as needed.
Standardize hash-function quality and parameter compatibility. HLL's theoretical error holds on the assumption that the hash is sufficiently uniform and independent, so a biased or short hash worsens the actual error beyond the theoretical value. Use a fast, high-quality non-cryptographic hash such as MurmurHash or xxHash, but to merge sketches made by different systems, the hash function, register count, and encoding convention must be perfectly identical. If this convention is not standardized organization-wide, the cost of regenerating sketches later arises.
In sum, HyperLogLog is a representative case of engineering approximation that "gives up part of accuracy to gain the substantive benefits of memory and mergeability," and it is a core tool that in the AI/big-data environment of exploding data scale linearly scales unique counting with fixed memory. When adopting it, designing the scope of application based on error tolerance, memory sizing by target precision, merge/intersection requirements, and deletion/privacy constraints is what decides success or failure.
References
- Salvatore Sanfilippo (antirez), "Redis new data structure: the HyperLogLog", https://antirez.com/news/75
- Flajolet, Fusy, Gandouet, Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" (2007), http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- Heule, Nunkesser, Hall, "HyperLogLog in Practice" (Google, EDBT 2013), https://research.google/pubs/pub40671/
In one line: HyperLogLog records the maximum leading-zero count of hash values in a register array and inversely estimates via the harmonic mean, counting unique element counts at the scale of billions with about 1% error using a few KB of fixed memory — a probabilistic cardinality-estimation technique.