HyperLogLog

HyperLogLog is a probabilistic data structure and algorithm designed to estimate the number of distinct elements in a multiset. This mathematical challenge is known as the count-distinct problem or cardinality estimation. In computer science, determining the exact cardinality of a dataset requires memory proportional to the number of unique items, as the system must remember every previously seen element to avoid counting duplicates. HyperLogLog bypasses this memory requirement by trading absolute precision for a highly compressed memory footprint. It can estimate cardinalities well beyond one billion with a typical accuracy of 2 percent while using only 1.5 kilobytes of memory HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.^[29]

The algorithm achieves this efficiency by applying a hash function to the input data and observing the binary representation of the hashed values. Specifically, it tracks the maximum number of leading zeros in the binary hashes. Because the output of a good hash function resembles a uniform random distribution of bits, the probability of encountering a sequence of leading zeros decreases exponentially as the sequence lengthens. By recording the longest sequence of zeros seen across different subsets of the data, HyperLogLog can extrapolate the total number of unique items processed Wikipedia: HyperLogLog^[1].^[30]

Originally formalized in 2007 by researchers at the French research institute INRIA, HyperLogLog has become a standard component in modern database systems, distributed computing frameworks, and stream processing engines. It is utilized in environments where exact counts are computationally prohibitive, such as tracking unique visitors on high-traffic websites, monitoring network packets for cybersecurity, and aggregating metrics across massive distributed databases Philippe Flajolet Biography and Publications.^[31]

The Count-Distinct Problem

The count-distinct problem asks for the number of unique elements in a sequence of items where elements may appear multiple times. If a sequence contains the items "apple", "banana", "apple", "orange", the exact distinct count is three. While this is trivial for small datasets, it becomes a significant computational bottleneck at the scale of big data Streamed approximate counting of distinct elements: Beating optimal batch methods^[2].

To compute an exact distinct count, a system must maintain a record of every unique item it has encountered. The standard approach uses a hash set or a similar deterministic data structure. When a new item arrives, the system checks the set to see if the item already exists. If it does not, the item is added to the set, and a counter is incremented. The space complexity of this exact approach is $O(N)$, where $N$ is the number of distinct elements. If a system needs to track one billion unique 64-bit identifiers, the hash set will require at least 8 gigabytes of memory. In distributed systems processing millions of events per second, maintaining and synchronizing such massive data structures across multiple nodes is highly inefficient and often impossible Optimal streaming and tracking distinct elements with high probability^[3].

An alternative exact method involves bit arrays or bitmaps. If the universe of possible items is known and maps to integers from 1 to $U$, a bit array of size $U$ can be allocated. Each item sets its corresponding bit to 1. The cardinality is the sum of all set bits. While this avoids storing the items themselves, the space complexity is $O(U)$. For a 64-bit identifier space, $U$ is $2^{64}$, requiring exabytes of memory, which renders the bitmap approach useless for large identifier spaces A linear-time probabilistic counting algorithm for database applications^[4].

Probabilistic cardinality estimators solve this problem by accepting a small, quantifiable margin of error in exchange for a logarithmic or sub-logarithmic space complexity. HyperLogLog requires $O(m \log \log N)$ or $O(\epsilon^{-2} \log \log N)$ space, where m is the number of registers, which is an extraordinary reduction. The transition from $O(N)$ to $O(\log \log N)$ means that the memory required grows so slowly that it can be considered practically constant for any realistic dataset size. This allows systems to maintain thousands of separate cardinality estimators in memory simultaneously, enabling complex analytics on multidimensional data streams An Improved Data Stream Summary: The Count-Min Sketch and its Applications^[5].

Core Mathematical Principles

The mathematical foundation of HyperLogLog rests on the properties of uniform hashing and the statistical behavior of binary sequences. When a hash function is applied to an input, it generates a fixed-length binary string. A high-quality hash function, such as MurmurHash3, ensures that the bits in this string are uniformly distributed and independent SMHasher and MurmurHash3^[6]. Consequently, each bit has a 50 percent chance of being a 0 and a 50 percent chance of being a 1, much like a series of coin flips.

If we examine the binary representation of these hash values, we can count the number of leading zeros before the first 1 appears. The probability of a hash value starting with exactly one 0 followed by a 1 is 1/4. The probability of starting with two 0s followed by a 1 is 1/8. In general, the probability of observing a sequence of exactly $k$ leading zeros is $2^{-(k+1)}$.

Because these probabilities halve with each additional zero, observing a long sequence of leading zeros is rare. If a system processes a small number of unique items, the maximum number of leading zeros observed across all their hashes will likely be small. If the system processes a massive number of unique items, the law of large numbers dictates that it will eventually encounter a hash value with a long sequence of leading zeros.

Therefore, the maximum number of leading zeros observed, which we can call $R$, acts as a logarithmic indicator of the cardinality. If the maximum number of leading zeros seen so far is $R$, the total number of distinct elements is approximately $2^R$. This observation is the core of the Flajolet-Martin algorithm, the predecessor to HyperLogLog Probabilistic counting algorithms for data base applications^[7].

However, a single estimator based on $2^R$ is highly volatile. A single anomalous hash value with an unusually high number of leading zeros (an outlier) can artificially inflate the estimate, leading to massive variance. To mitigate this variance, HyperLogLog employs a technique called stochastic averaging. Instead of maintaining one global maximum, the algorithm divides the incoming data into $m$ separate buckets or registers. The average of the maximum leading zeros across all $m$ registers provides a much more stable and accurate estimate of the true cardinality Loglog Counting of Large Cardinalities^[8].

Mechanism and Algorithm

The HyperLogLog algorithm operates in a single pass over the data and requires a fixed array of $m$ registers, initialized to zero. The number of registers $m$ is typically chosen as a power of 2, such as $m = 2^p$, where $p$ is the number of bits used for addressing the registers. The choice of $p$ dictates the tradeoff between memory usage and estimation accuracy. The standard error of HyperLogLog is approximately $1.04 / \sqrt{m}$. For example, if $p = 14$, then $m = 16384$, and the standard error is roughly 0.81 percent HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.

When an item is added to the HyperLogLog structure, the algorithm performs the following steps. First, it hashes the item using a 32-bit or 64-bit hash function. The resulting binary hash is split into two parts. The first $p$ bits of the hash are used as an index to determine which of the $m$ registers this item belongs to. The remaining bits of the hash are used to calculate the rank, which is the position of the leftmost 1 (equivalent to the number of leading zeros plus one).

Once the register index and the rank are determined, the algorithm updates the selected register. The new value of the register is the maximum of its current value and the newly calculated rank. This operation ensures that each register only tracks the longest sequence of leading zeros seen among all the items that hashed to its specific index.

After all items have been processed, the algorithm aggregates the values from the $m$ registers to compute the final cardinality estimate. Earlier algorithms like LogLog used the geometric mean for this aggregation. HyperLogLog introduced the use of the harmonic mean, which is significantly more resistant to large outliers. If a single register contains an unusually high value due to a random hash collision, the harmonic mean naturally diminishes its impact on the overall average New cardinality estimation algorithms for HyperLogLog sketches^[9].

The raw cardinality estimate $E$ is calculated using the following formula:
$E = \alpha_m \cdot m^2 \cdot \left( \sum_{j=1}^{m} 2^{-M[j]} \right)^{-1}$
In this formula, $m$ is the number of registers, $M[j]$ is the maximum rank stored in the $j$-th register, and $\alpha_m$ is a correction constant that accounts for hash collisions and the statistical bias of the harmonic mean. The constant $\alpha_m$ is derived from the Gamma function and complex integration, ensuring that the harmonic mean estimator is asymptotically unbiased. For $m \ge 128$, $\alpha_m$ is closely approximated by $0.7213 / (1 + 1.079 / m)$.

To illustrate the mechanism, the following pseudocode demonstrates the insertion and estimation phases of the HyperLogLog algorithm:

function initialize(p):
    m = 2^p
    registers = array of m integers, all set to 0
    return registers

function add(item, registers, p):
    hash_val = hash(item)
    index = get_first_p_bits(hash_val, p)
    remaining_bits = get_remaining_bits(hash_val, p)
    rank = position_of_leftmost_one(remaining_bits)
    registers[index] = max(registers[index], rank)

function estimate(registers, p, m, alpha_m):
    sum = 0.0
    for j from 0 to m - 1:
        sum = sum + (2 ^ -registers[j])
    raw_estimate = alpha_m * (m ^ 2) / sum
    return apply_corrections(raw_estimate, registers, m)

The time complexity for inserting an element is $O(1)$, as hashing and bitwise operations execute in constant time. The space complexity is $O(m \log \log N)$. Because the maximum rank for a 64-bit hash is 64, 6 bits can only store values up to 63; the maximum rank fits in 6 bits because p bits are used for the register index, leaving a maximum rank of 64 - p + 1 (which is ≤ 63 for p ≥ 2). Thus, an array of 16384 registers requires exactly 12 kilobytes of memory Apache DataSketches HyperLogLog.

Corrections for Extreme Cardinalities

The raw estimate produced by the harmonic mean formula is highly accurate for a wide middle range of cardinalities. However, it exhibits significant bias at the extremes, specifically for very small and very large datasets. HyperLogLog applies specific correction functions to address these boundary conditions.

For small cardinalities, where the true number of distinct elements is much less than the number of registers $m$, the raw estimate tends to overestimate the count. In this scenario, many registers will remain at their initial value of zero. HyperLogLog detects this condition by counting the number of empty registers, denoted as $V$. If the raw estimate is below a certain threshold (typically $2.5 \cdot m$) and $V > 0$, the algorithm switches to a technique called Linear Counting A linear-time probabilistic counting algorithm for database applications^[4].

Linear Counting treats the register array as a simple Bloom filter or bitmap. The cardinality is estimated based on the fraction of empty registers using the formula $E = m \cdot \ln(m / V)$. This probabilistic counting method is highly accurate for small sets and smoothly bridges the gap before the main HyperLogLog formula becomes reliable.

For very large cardinalities, where the true count approaches the maximum capacity of the hash space (for example, near $2^{32}$ for a 32-bit hash function), hash collisions become inevitable. Multiple distinct items will generate the exact same 32-bit hash, causing the algorithm to underestimate the true cardinality. To correct this, the original HyperLogLog specification includes a large range correction formula that adjusts the estimate upward based on the probability of 32-bit hash collisions. However, in modern implementations that utilize 64-bit hash functions, the large range correction is generally unnecessary. A 64-bit hash space can track cardinalities up to $2^{64}$, a number so vast that physical memory and processing time would be exhausted long before hash collisions statistically impact the estimate ^[10].

Discovery and Historical Development

The theoretical underpinnings of HyperLogLog trace back to 1978, when Robert Morris introduced the Morris counter. Morris, working at Bell Labs, needed to count a large number of events using an 8-bit register, which normally overflows at 255. He devised a probabilistic counting method that incremented the counter based on a random probability, allowing an 8-bit register to estimate counts up to 130,000. This established the concept of trading exactness for memory efficiency in counting applications Counting large numbers of events in small registers^[11].

The specific lineage of HyperLogLog began in 1985 with the publication of "Probabilistic counting algorithms for data base applications" by Philippe Flajolet and G. Nigel Martin. Flajolet, a prominent mathematician and computer scientist at the French institute INRIA, and Martin formalized the idea of using the binary representation of hashed values to estimate cardinality. The Flajolet-Martin algorithm introduced the concept of bit-pattern observables, specifically tracking the position of the least significant zero bit in a hash. While highly innovative, the Flajolet-Martin algorithm required a bitmap of length $L$ for each hash bucket, making it less memory efficient than later iterations Probabilistic counting algorithms for data base applications^[7].

In 1990, Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor published "A linear-time probabilistic counting algorithm for database applications". This paper introduced Linear Counting, which demonstrated how a simple hash-based bitmap could accurately estimate cardinalities by counting the number of unset bits. Linear Counting eventually became the small-range correction mechanism within the HyperLogLog algorithm A linear-time probabilistic counting algorithm for database applications^[4].

The direct predecessor to HyperLogLog was the LogLog algorithm, introduced in 2003 by Marianne Durand and Philippe Flajolet. LogLog simplified the Flajolet-Martin approach by tracking only the maximum number of leading zeros (the rank) rather than maintaining a full bitmap per bucket. LogLog used the geometric mean to average the registers, achieving a standard error of $1.30 / \sqrt{m}$. This was a major leap in memory efficiency, allowing the algorithm to estimate large cardinalities using only a few kilobytes. The space reduction is where the "LogLog" name originates, as the memory required scales with the logarithm of the logarithm of the maximum cardinality Loglog Counting of Large Cardinalities^[8].

The culmination of this research occurred in 2007, when Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier published "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" in the journal Discrete Mathematics and Theoretical Computer Science. The primary innovation in the 2007 paper was the replacement of the geometric mean with the harmonic mean. This mathematical adjustment drastically reduced the algorithm's sensitivity to extreme outliers, lowering the standard error to $1.04 / \sqrt{m}$ without requiring any additional memory. The paper provided rigorous mathematical proofs of the algorithm's asymptotic behavior, establishing HyperLogLog as a near-optimal solution for the count-distinct problem HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.

Important Variants and Refinements

Since the publication of the original 2007 paper, several variants and refinements have been developed to optimize HyperLogLog for specific production environments.

The most significant refinement is HyperLogLog++, introduced by Google researchers Stefan Heule, Marc Nunkesser, and Alexander Hall in 2013. Published at the EDBT conference, the HyperLogLog++ paper addressed practical shortcomings in the original algorithm. The Google team transitioned the algorithm from 32-bit hashes to 64-bit hashes, effectively eliminating the need for the large range correction. Additionally, they discovered that the original algorithm exhibited empirical bias at intermediate cardinalities, the transition zone between Linear Counting and the harmonic mean formula. HyperLogLog++ introduced precomputed empirical bias correction tables to smooth this transition ^[10].

HyperLogLog++ also introduced a sparse representation for memory efficiency. When a HyperLogLog structure is first initialized, most of its registers are zero. Instead of allocating the full array of $m$ registers, HyperLogLog++ stores the non-zero registers as a list of index-value pairs. This sparse representation requires significantly less memory for small datasets. Once the sparse list exceeds the memory footprint of the dense array, the data structure automatically converts to the standard dense representation New cardinality estimation algorithms for HyperLogLog sketches^[9].

Another notable variant is Sliding HyperLogLog, formalized by researchers in 2010. Standard HyperLogLog assumes an ever-growing dataset. In many stream processing applications, engineers need to know the cardinality over a sliding time window, such as the number of unique users in the last 60 minutes. Sliding HyperLogLog modifies the data structure to store timestamps alongside the maximum rank in each register, allowing the algorithm to expire old data points and maintain an accurate count over a moving temporal window Sliding HyperLogLog: Estimating Cardinality in a Data Stream over a Sliding Window^[12].^[32]

HyperMinHash, introduced by researchers at the University of Toronto and Harvard Medical School (and first appeared as a preprint in 2017), combines HyperLogLog with the MinHash algorithm. MinHash is used to estimate the Jaccard similarity between two sets, but it requires substantial memory. HyperMinHash compresses the MinHash signatures using the LogLog space reduction technique, allowing systems to estimate both the union cardinality and the intersection similarity of massive datasets using a fraction of the memory required by standard MinHash HyperMinHash: MinHash in LogLog space^[13].

Real-World Applications

HyperLogLog is heavily utilized across modern software infrastructure, particularly in databases, data warehouses, and stream processing frameworks where exact distinct counting would cause unacceptable latency or memory exhaustion.

In the domain of in-memory data stores, Redis provides a native implementation of HyperLogLog. Introduced in Redis 2.8.9, the implementation includes commands such as PFADD to add elements and PFCOUNT to retrieve the estimated cardinality Redis PFADD Command^[14]. The "PF" prefix in these commands is a deliberate tribute to Philippe Flajolet. The Redis implementation uses a 64-bit hash and fixes the number of registers at 16384, meaning every HyperLogLog key consumes exactly 12 kilobytes of memory and provides a standard error of 0.81 percent. Redis also implements the sparse representation to save memory for keys with small cardinalities Redis HyperLogLog Documentation^[15]. Other key-value stores, such as Riak and Aerospike, offer similar native HyperLogLog data types for high-performance counting Aerospike HyperLogLog Data Type^[16] Riak HyperLogLog Data Type^[17].

Distributed SQL query engines rely on HyperLogLog to optimize query planning and execution. Presto, an open-source distributed SQL engine originally developed at Facebook, uses HyperLogLog to implement the approx_distinct function. By using this function instead of a standard COUNT(DISTINCT) clause, Presto can aggregate data across hundreds of worker nodes without shuffling massive amounts of raw data over the network Presto HyperLogLog Functions^[18].^[33] Similarly, cloud data warehouses like Google BigQuery, Amazon Redshift, and Snowflake provide native HyperLogLog functions. In BigQuery, the HLL_COUNT.INIT function generates a HyperLogLog sketch, which can be stored in a database column and later merged with other sketches using HLL_COUNT.MERGE Google BigQuery HyperLogLog Functions^[19] Amazon Redshift HLL Functions^[20] Snowflake approx_count_distinct^[21].^[34]

In the PostgreSQL ecosystem, HyperLogLog is available through the postgresql-hll extension, originally developed by Citus Data. This extension introduces a native hll data type, allowing database administrators to store sketches directly in tables. This is highly effective for multi-tenant applications where unique user counts must be aggregated across different time dimensions, such as daily, weekly, and monthly active users. Instead of running expensive queries over raw event logs, the database can simply merge the daily hll sketches to compute the weekly and monthly metrics in milliseconds postgresql-hll GitHub Repository^[22].

Stream processing systems, which handle continuous flows of unbounded data, use HyperLogLog to maintain real-time metrics. Apache Spark includes the approx_count_distinct function in its DataFrame API, allowing data scientists to estimate unique values across petabytes of data in distributed clusters Apache Spark approx_count_distinct^[23].^[35] Apache Druid, a real-time analytics database, uses the Apache DataSketches library to ingest millions of events per second, utilizing HyperLogLog to provide sub-second query responses for unique user counts on live dashboards Apache Druid DataSketches HLL Extension^[24]. Elasticsearch utilizes a variant of HyperLogLog for its cardinality aggregation, enabling fast approximations of unique field values across distributed search indices Elasticsearch Cardinality Aggregation^[25].

Google Analytics relies heavily on HyperLogLog to provide real-time metrics to webmasters. When a user views a dashboard showing the number of unique visitors over a custom date range, computing that number exactly from billions of raw pageview events would cause the dashboard to time out. Google Analytics uses HyperLogLog++ sketches pre-aggregated by day and dimension. When the user queries a specific date range, the system merges the relevant sketches on the fly, delivering a highly accurate estimate almost instantly Unique count approximation in Google Analytics^[26].

Significance and Tradeoffs

The primary significance of HyperLogLog lies in its mergeability, a property mathematically known as homomorphism. If a system creates a HyperLogLog sketch for Dataset A and a separate HyperLogLog sketch for Dataset B, the exact HyperLogLog sketch for the union of A and B can be computed simply by taking the element-wise maximum of their respective registers. This property is vital for distributed computing. It allows a massive dataset to be partitioned across thousands of servers, where each server computes a local HyperLogLog sketch. The local sketches can then be merged into a single global sketch with zero loss of precision. The final estimate is identical to the estimate that would have been produced if all data had been processed by a single machine All-distances sketches, revisited: HIP estimators for massive graphs analysis^[27].

Despite its immense utility, HyperLogLog involves strict tradeoffs and is not suitable for every application. The most obvious limitation is the lack of exactness. If an application requires absolute precision, such as financial auditing or billing systems, probabilistic data structures cannot be used.

Another major limitation is the inability to process deletions. Once an item is added to a HyperLogLog sketch, its hash may have updated a register to a higher rank. If that item is later removed from the dataset, the algorithm cannot simply decrement the register, because that register might also be storing the rank of a different item that produced the same number of leading zeros. While specialized variants like Counting HyperLogLog exist to handle deletions, they require significantly more memory, negating the primary advantage of the original algorithm Redis PFCOUNT Command^[28].

Finally, for very small datasets, the overhead of the HyperLogLog data structure can exceed the memory required to store the exact items. An array of 16384 registers consumes 12 kilobytes. If a dataset only contains ten 64-bit integers, storing the exact integers requires 80 bytes. While the sparse representation mitigates this issue, developers must still evaluate whether the complexity of a probabilistic estimator is justified for applications where cardinalities remain consistently low ^[10].