HyperLogLog (HLL) is a probabilistic data structure used for efficiently estimating the cardinality of massive datasets. HLL is particularly useful in contexts where a precise count might be impractical due to memory constraints, such as counting unique visitors to a website or unique elements in a stream of data.
The strength of HyperLogLog lies in its ability to provide cardinality estimates with a standard error of 1-2% using significantly less memory than would be required for an exact count.
Use Cases and Benefits
HLL is valued for its efficient memory usage and scalability in estimating cardinalities of very large sets where exact counts are unnecessary:
-
Massive Data Analysis: HLL provides cardinality estimates in situations where datasets are too large for exact counting, such as processing logs or network monitoring.
-
Performance Monitoring: Estimating unique events or users in real-time performance monitoring systems.
-
Resource-limited Environments: HLL's low memory footprint makes it a good fit for environments with limited resources, like edge devices in IoT.
-
Stream Processing: HLL is commonly used in streaming applications for real-time analytics without the storage overhead of tracking individual elements.
How HyperLogLog Works
HLL applies hash functions to elements and uses the pattern of leading zeros in the hashed values to infer the cardinality of the set. It divides the hash space into several registers and tracks the maximum number of leading zeros seen in each one. These counts are then used in a mathematical formula to estimate the cardinality of the dataset.
The accuracy and memory usage of HLL can be adjusted by changing the number of registers used, trading off between resource consumption and the precision of the estimate.
Popular implementations of HyperLogLog
Due to its practicality, HLL has been implemented in various databases, data processing systems, and programming libraries:
- Databases: Redis, PostgreSQL, QuestDB and BigQuery have built-in support for HLL.
- Data Processing Systems: Apache Spark and Apache Flink offer HLL implementations for distributed computing environments.
- Programming Libraries: HLL algorithms are available in languages like Java, Python, and Go, often as open-source libraries.
HLL in a modern SQL database
An example from a database such as QuestDB looks as such.
SELECT approx_count_distinct(order_id, 8) FROM orders;
| approx_count_distinct |
|---|
| 3456789 |
Note that there is a precision parameter (8), which is passed into the function. A higher precision leads to more accurate results with increased memory usage. Naturally, precision within an estimate is costly as far as system resources are concerned!
Further reading
-
See HyperLogLog in a top-10 "1 Billion Row Challenge" Java optimization challenge
-
GoLang's HyperLogLog implementation
-
YouTube video demonstrating HyperLogLog in the context of Redis