Our series on algorithms for estimating the number of distinct values in a multiset continues with the state-of-the-art algorithm, HyperLogLog. All the ideas behind it come from LogLog, which we described earlier, so if you want to read on, make sure you know LogLog well.

LogLog had two main problems:

Outliers

The LogLog estimate is very sensitive to outliers, values that are far away from the rest. Typically, the maximum trailing-zero lengths for the buckets are all roughly the same, say between 12 and 15, and then, bang, one trailing-zero length is 27. This one big difference makes a mess of the estimate of the number of distinct values, because the ordinary arithmetic mean copes with it badly. It is the same effect as a few top managers and directors pushing up the average wage in a country with their high wages.

The authors first tried to deal with this by getting rid of the outliers and leaving the few highest maxima out of the mean, but that was not a very good solution. Later they tried a different approach: instead of the arithmetic mean they used the harmonic mean, which behaves far better when some values are far from the mean.

Very poor results for small cardinalities

LogLog does terribly when it has to estimate the cardinality of small multisets. If a multiset has only a few distinct elements, LogLog gives us a ridiculously large estimate. The authors solved this cleverly: when the input is a multiset with low cardinality, LogLog is not used at all. A completely different algorithm is used instead, the good old Linear counting. But how do we know that the input has a small cardinality, when the cardinality is exactly what we don't know?

We let LogLog estimate the number of distinct elements, and if the estimate turns out to be relatively low, we throw it away and compute it again with Linear counting. Let's quickly recall how Linear counting works. At the start we allocate a zeroed bit array of some predetermined size, typically a power of two. We go through all the elements of the multiset, compute their hashes and turn each hash into an integer i from 0 to the length of the array minus 1. Then we store a one at index i in the array. Finally, we count the zeros and ones in the array and estimate the cardinality with a simple formula.

LogLog, however, does not use any bit array in which it would “store” the computed hashes. Instead, it uses an array in which it keeps the maximum lengths of the suffixes. The array might look like this:

[2, 5, 9, 0, 5, 4, 4, 0]

where each number is the maximum trailing-zero length in the given bucket of computed hashes. A non-zero value at position i necessarily means that the multiset contains an element whose (three-bit) hash is equal to i. In other words, we can turn this array into a bit array for Linear counting by keeping the zeros and turning any positive number into a one. From the previous array we would get this bit array:

[1, 1, 1, 0, 1, 1, 1, 0]

Now we can apply the Linear counting algorithm and use it to estimate the cardinality.

There is one catch, though. We store the maximum number of trailing zeros in the array, but what if all the hashes in some bucket end in a one? For example, if we use the last three bits as the identifier of the bucket a hash belongs to, then the trailing-zero length of the hash “01001100” would be zero, because the vector “01001” ends in a one. So we would store a zero at index 4 (100₂ = 4₁₀) in the array of maxima. In Linear counting, that would look as if we had not found any value whose hash is four, which is not true.

So we modify the algorithm so that, instead of the length of the longest run of trailing zeros, the array of maxima holds the index of the “first one from the right” (for the record, we index from one), which is the same as adding one to the trailing-zero length. This means that a zero at index i says that no value has a hash equal to i, and such an array can then be used for Linear counting.

Implementing HyperLogLog

Let's go step by step:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

The function alpha returns the correction for the computed estimate. We know it from last time, except that in HyperLogLog alpha has a different value depending on the number of buckets.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

A function that returns the number of zero bits at the end of a number.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

A function that goes through all the values, splits them into num_buckets buckets and, for each bucket, computes the index of the first one from the right (the length of the maximum trailing-zero run plus one).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

A slightly modified function for computing the Linear counting algorithm.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

The main function, which puts it all together. First it computes the estimate with the modified LogLog, using the harmonic mean instead of the arithmetic mean on the fourth line. Finally it applies the correction in the form of Linear counting if the computed estimate is less than 2.5 times the number of buckets (at that point we expect the standard LogLog estimate to be worse than Linear counting would be), and if the array of maxima contains at least one zero (we can't use Linear counting on an array full of ones, see the previous article). And what are the results of HyperLogLog?

We run a test that estimates the cardinality of sets whose cardinalities are 10, 100, …, 1,000,000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Results:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

We can see that the results are always within one per cent of the correct value. And that is good!

Further improvements to HyperLogLog

HyperLogLog has received several other interesting improvements. One of the remaining problems is its high memory consumption. That sounds odd, since last time we sang the praises of its memory efficiency and worked out that 768 bytes are enough to store the array of maxima. The problem arises, though, when you want to compute the cardinality not of one huge multiset, but of several million small multisets in parallel, or when you want to keep these computed arrays of maxima in a database for some later trickery.

If we were computing the cardinality of a billion multisets at once, for example, the current implementation would need 1,000,000,000 times 768 bytes, which is 768 GB. On the one hand that's not bad … but on the other hand, we can implement HyperLogLog better.

Sparse representation

Let's say we set k=12, that is, we use 12 bits to identify the buckets, which gives us 2¹² different buckets of hashes. At the start of the algorithm we have to allocate an array of length 4096 (see line 3 of the function count_maxims). Suppose our multiset has three different elements. That means we set some value at three different places in the array, and the remaining 4093 values stay zero. We simply never used those 4093. That's not very efficient, is it?

To avoid having an array that is mostly zero and unused but still takes up a valuable chunk of memory, we can store the values at the start as pairs [index, value]. Here's an example to help you understand. This array

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

can be represented far more efficiently in memory as two pairs:

[0, 7], [4, 12]

Instead of keeping a pile of unused space allocated in memory, we can gradually allocate only the space we really need. We call this representation sparse. At some point, however, this representation would take more memory than simply storing the array. We can then convert the sparse representation into a classic array without losing any information.

Offsets

Practice has shown that all the values in the array are roughly the same. An array of maxima usually looks like this, for example:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

All the values are somewhere around 13. Another strategy for making such an array smaller is to subtract some fixed value from every element and remember it. We can subtract eight, for example:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Now each value in the array takes less memory: in the first array we need to store numbers from 0 to 15, which takes 4 bits, whereas the second array needs only 3 bits, because we store only numbers from 0 to 7. Of course, this assumes the array is implemented at the level of individual bits. When we want to read the values from the array, we have to add the remembered value back to them.

…and a pile of other improvements. Research in this area is still going on, so we can certainly look forward to more interesting ideas. Next time we'll talk about the union and intersection of HyperLogLog vectors, and at some point in the near future we'll talk about why it can be handy to store billions of HyperLogLog vectors.

Links and sources

• You can view my whole implementation on GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — the original paper that introduced HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — an improved version of the original HyperLogLog, including the sparse representation mentioned above.