5 Cardinality Estimation and HyperLogLog

Cardinality estimation asks how many distinct elements appear in a multiset, a need that arises everywhere from databases and web analytics to network security. Exact methods scale poorly at modern data volumes: COUNT DISTINCT often forces costly sorts, hash tables need space proportional to the number of uniques, and even deciding if all items are distinct has strong lower bounds. This has pushed industry toward approximate, streaming-friendly estimators that use tiny memory and one pass. Systems like BigQuery and SQL Server expose approximate distinct counting because they return results fast with predictable error, making them ideal for trillion-event pipelines and real-time dashboards.

The chapter incrementally develops the ideas that lead to HyperLogLog (HLL). It begins by hashing items to bit strings and using probabilistic counting: the maximum number of trailing zeros seen hints at the order of the cardinality, but this yields high variance and power-of-two granularity. Stochastic averaging reduces variance by partitioning hashes into m buckets (via the first b bits) and aggregating per-bucket maxima; LogLog adds a bias-correction constant to this scheme. SuperLogLog trims extreme bucket values to further stabilize estimates. HyperLogLog makes the key leap: it replaces the arithmetic/geometric averaging with a harmonic mean across bucket registers, then applies a refined bias correction. HLL achieves a relative error of roughly 1.04/sqrt(m) with just 5–6 bits per register; with m = 2^14, it uses on the order of a dozen kilobytes while delivering near–percent-level error. Practical refinements include small-range correction via linear counting, large-range corrections, and modern 64-bit hashes (as in HLL++) to avoid collisions and smooth bias near the crossover between regimes.

Beyond theory, the chapter shows where HLL shines and how to use it effectively. In networking, tracking the distinct source–destination IP pairs over time helps detect scans and worm outbreaks; in analytics, HLL powers fast distinct user counts and feature-usage metrics. Its mergeability is crucial: register-wise maxima let you union daily or hourly sketches to get arbitrary time-window estimates without rescanning raw data, enabling multi-level rollups (hour→day→week) with stable relative error that depends only on m. Simulations confirm HLL’s low bias and tight, roughly Gaussian error distribution, and illustrate how increasing m narrows variance. Taken together, these properties explain HLL’s widespread adoption (e.g., in Redis and large-scale data warehouses): it offers single-pass operation, tiny and predictable memory, composability via unions, and accuracy sufficient for operational and business decisions at massive scale.

: A dataset of 12 items is hashed into 16-bit hashes. As we scan the dataset, we keep the running maximum of the In this example, the lemon item, whose hash is 1001 1111 0001 0000 holds the maximum , and our cardinality estimate is , but the true distinct count is .

: In this example, each hash is being mapped to a bucket based on its first two bits (e.g., the hash corresponding to the grape item is mapped to the bucket 00, while the hash corresponding to the pear item is mapped to the bucket 01.) When this process runs on large datasets, we would expect each bucket to receive the same number of distinct hashes. Each bucket computes its , which in this case results in bucket values 2, 2, 5 and 1. Now the hash of the lemon item is only affecting the value stored in the bucket 10.

: A healthy network flow. A fairly large number of packets but a small number of different flows.

: A suspicious flow --- having many source-destination pairs, and one source opening a large number of different connections in a short amount of time.

: Placing a HyperLogLog at the entry point of the network within an organization can help us gather valuable statistics about the network traffic of that organization.

: Plot shows the comparison of the probabilistic counting (Without buckets), stochastic averaging with arithmetic mean (unnormalized) (With buckets (Arithmetic mean)) and stochastic averaging with harmonic mean (unnormalized) (With buckets (Harmonic mean)). All raw estimates show consistent overestimate bias, however the least bias on average is shown by harmonic mean method, followed by the arithmetic mean method and probabilistic counting. The largest deviation in the estimates (having different experiment vary in estimates by a factor of is exhibited by probabilistic counting, that only has estimates that are powers of 2, followed by the arithmetic mean method, and then followed by the harmonic mean method.

: Effect of different values of on the accuracy of log2 cardinality estimate in HyperLogLog. The larger the number of buckets, the smaller deviation from the true cardinality. In general, harmonic mean method once bias corrected, rarely over/underestimates by more than one unit of log2, in all three cases.

: The effect of buckets on cardinality estimate in HyperLogLog. Larger implies smaller bias and a more properly Gaussian-looking distribution.

: In a daily visit table, each row indicates one visit by a user and each table maintains a separate distinct-count variable that tracks the number of different users. Considering that some users return to the website repeatedly, we can not simply sum up the individual counts to obtain the week’s distinct user count.

: Maintaining one HyperLogLog per daily table helps us later aggregate the HyperLogLogs over multiple days to obtain an estimate for more tables. In fact, HyperLogLog can be easily encoded so that we can maintain a table of HyperLogLog schemas , later to be decoded.

: Once we have stored daily HLLs, we can perform union over the arbitrary choice of interest to obtain aggregate cardinality estimate for a given time period.

: Aggregation happens over multiple levels in this case: hour, day, week, etc. Commonly in databases, when we group by different timespans, this requires a one scan of entire data for each level of aggregation.

• Cardinality estimation arises in many areas of software development, primarily databases, network traffic and e-commerce. Due to the volume of data, classical database functions for exact cardinality computation are being replaced with probabilistic methods that offer great space savings in exchange for a small error in accuracy.
• HyperLogLog is the algorithm/data structure that uses hashing and probabilistic properties of random bit strings to gauge the set cardinality. Its space consumption is and its relative error .
• Many companies that run large systems have implemented HyperLogLog for their use, and improved and modernized various aspects of it (e.g., implementations by Google, Redis, Facebook and others.)
• The estimates provided by HyperLogLog have roughly Gaussian shape. In our simulations on a hashset of , we ascertained that HyperLogLog obeys the rules of Gaussian distribution, by letting approximately 70% of data fall within one, 95% within two, and 99% within three standard errors.
• The true power of HyperLogLog is visible when doing aggregations of a huge number of large individual tables that represent data over time. Instead of keeping the large tables, we can instead store a table of HyperLogLogs, and choose to aggregate and merge HyperLogLogs for the periods of interest (e.g., week, month, quarter, etc.)

FAQ