Papers
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier · 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS proc. AH, pp. 127-146, 2007
The problem: counting distinct elements in a huge stream with little memory
The paper is about estimating the cardinality of a multiset, that is, the number of distinct elements in data that are usually single-read streams. The authors cite applications in network monitoring: the number of distinct source-destination pairs in time windows indicates how many active flows exist and helps detect attacks, and worms and viruses tend to spread by opening many different connections, so their activity shows up when cardinalities are measured. Computing the exact value requires storage essentially proportional to the number of elements, and in many applications the set is too large to fit in main memory. That is why the paper relaxes the requirement: an approximate estimate is accepted, since a tolerance of a few percent is usually enough. All known efficient estimators rely on randomness obtained from a hash function, and the analysis assumes that the bits of the hashed values are independent and each have probability 1/2. The paper's abstract presents the promise of HyperLogLog: with m units of memory and a single pass over the data, the relative error (standard error) is typically about 1.04 divided by the square root of m. As an example, the paper says that cardinalities above 10^9 can be estimated with typical accuracy of 2% using only 1.5 kilobytes. The algorithm improves on LogLog, the best previously known estimator, whose accuracy can be matched while using only 64% of the original memory.
The core idea: a bit-pattern observable and stochastic averaging
HyperLogLog uses the same observable as LogLog. For a binary string, rho is the position of the leftmost 1 bit; seeing a prefix with many zeros is evidence that the cardinality is large, since a pattern with rho-1 zeros followed by a 1 suggests a cardinality of at least 2^rho. A single observable has high variability, and repeating the experiment with m independent hash functions would be expensive and would require independent functions for which no construction is known. The solution, called stochastic averaging (an earlier technique by Flajolet and Martin), emulates m experiments with a single hash: the first b bits of the hashed value, with m equal to 2^b, choose one of m registers, and the rest of the string feeds the rho of that register, which keeps the maximum rho seen. Thus each element costs a constant number of operations, not proportional to m. The novelty of HyperLogLog is in the evaluation function: instead of the geometric mean implicit in LogLog, it computes a harmonic mean of the quantities 2 raised to the value of each register. The paper credits the inspiration to a note by Chassaing and Gérin and explains that the harmonic mean tames distributions with a slowly decaying right tail, acting as a variance reducer. The estimate is a correction constant times m squared divided by the sum of 2 raised to minus the value of each register.
The analytical guarantee: bias and standard error of Theorem 1
The main result holds for ideal multisets, a model in which the hashed values are independent uniform variables in the interval [0,1], with arbitrary repetitions and permutations. For m registers, with m greater than or equal to 3, Theorem 1 states two things. First, the estimate is asymptotically almost unbiased: the expected value divided by n tends to 1 plus a small oscillation, of magnitude less than 5 times 10^-5 when m is at least 16. Second, the standard error, defined as the square root of the variance divided by n, tends to beta_m divided by the square root of m, plus an oscillation of magnitude less than 5 times 10^-4 for m from 16 on. The constants beta_m are bounded: beta_16 is about 1.106, beta_32 about 1.070, beta_64 about 1.054, beta_128 about 1.046, and the limit beta_infinity is the square root of 3 log 2 minus 1, approximately 1.03896. The constant alfa_m in the formula exists to correct a systematic multiplicative bias. The paper also states that each register needs at most log2 log2 N plus a constant number of bits when estimating cardinalities up to N. The proof uses standard techniques of algorithm analysis, such as poissonization, Mellin transforms and saddle-point depoissonization, and the nonlinearity of the harmonic mean makes part of the analysis nonroutine.
From algorithm to program: registers, range corrections and cost
The analysis assumes registers initialized to negative infinity, which makes the estimate equal 0 if any register is untouched, and therefore the algorithm is very inaccurate for small cardinalities. The practical program in Figure 3 initializes the registers to 0 and adds two corrections. In the small range correction, applied when the raw estimate is at most 5m/2, the paper uses the balls-and-bins argument, from the same family as the Hit Counting algorithm of Whang et al.: if V registers remain at 0, the cardinality is estimated as m log(m/V), when V is nonzero. Without this, with n equal to 0 the raw version would return about 0.7m. Simulations indicate that the asymptotic regime is practically reached from n equal to 5m/2 for m greater than or equal to 16. In the large range correction, when n approaches 2^L the L-bit hashes collide, and the formula inverts the expected relationship to obtain n equal to minus 2^L log(1 minus E/2^L); with 32 bits, 2^32 is about 4 times 10^9. With a 32-bit hash, 5 bits are enough per register. According to the paper, the running time is dominated by the hash computation, ending up three to four times slower than a simple scan with wc -l. The authors expect approximately Gaussian estimates: within 1, 2, and 3 deviations in about 65%, 95%, and 99% of cases.
Why it is near-optimal and what the article says about practical use
The title speaks of near-optimality, which the paper justifies by combining two facts. First, maintaining approximate counts with tolerance epsilon up to the range N requires at least on the order of log log N bits: cardinalities fall on an exponential scale 1, (1+epsilon), (1+epsilon)^2 and so on, with log base (1+epsilon) of N intervals, and telling them apart takes at least the log2 of that number of bits. Second, Chassaing and Gérin showed that, for a broad class of algorithms based on order statistics, the best achievable accuracy has a lower bound close to 1 over the square root of m. HyperLogLog can be seen as maintaining approximate order statistics and, based on that result alone, sits about 4% above the theoretical optimum of the Chassaing and Gérin class, using memory units typically 3 to 5 times smaller. On real data, the paper shows an experiment with m equal to 2048 (standard error of about 2%) on 458 chunks of about 40,000 lines of octal dumps of a book's PostScript source, with results in good agreement with the analysis. The authors conclude that the algorithm is easy to implement, requires only a good hash, and distributes optimally: given an arbitrary partitioning of the file, it is enough to collect the registers and apply a component-wise maximum. It also adapts to the sliding window model.
See the ideas at work
Practice the designs that use this paper in the System Design school.