LogLog: how to estimate the number of distinct values
After the previous instalments on Linear Counting and Min Value, we finally get to almost the very best probabilistic algorithm for estimating the number of distinct values in a data set, LogLog. The only thing better is its little brother HyperLogLog, which builds on LogLog, but more on that next time.
Let's recap the problem. The input is some data set or multiset, for example an array or generator of IDs. Some values occur several times in this array, and we want to count the distinct values in it. We will call this number the cardinality. We expect the cardinality to be really large, otherwise we could use conventional algorithms.
The idea behind the LogLog algorithm
Imagine we have a set of binary vectors. Don't be alarmed — for example, 0001011001001100 is a binary vector of length 16. Suppose we have binary vectors of length 32 and one million of them in total, all generated completely at random. How many vectors will end in a zero?
We cannot know exactly, of course, but if we really did generate the vectors at random, about half of them should end in a zero, that is 500 thousand. How many vectors will end in 00? A quarter. In 000? An eighth. And so on. Roughly, we can show it like this:
vector pattern share of all vectors
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12.5%
...xxx0000 6.25%
... ...
If we ask about a suffix (a suffix is a string that another string ends with — the opposite of a prefix) of length d, we expect to find v vectors ending with that suffix. We calculate the value v as:
where N is the number of all vectors in the set. A suffix of length 3 (for example …010) should occur in 1/2^3 N = 1/8 N of the vectors, that is 12.5% of all vectors.
Time for a little mind-bender. Take a multiset of 1024 distinct vectors. How many vectors should end with the suffix 0000000000? (ten zeros) Substituting into the formula, we get
Huh, one! Among a thousand randomly generated binary vectors there should be exactly one vector ending in ten zeros. And how do we use this information to estimate the number of distinct elements? We can work the other way round. What if we go through all the binary vectors in the input and find that the set contains a single vector that ends in ten zeros? Then we can surely estimate that the set had 1024 vectors in it!
Generalising and building the algorithm
The goal should be to find a suffix that is contained in only a single vector, while being as short as possible. That is very hard to do, though, because to really find such a vector we would have to store all the suffixes, which we do not want to do because it would take up too much memory. Instead, we settle for looking for the longest run of zeros at the end of a vector.
So we go through all the vectors, for each vector we count how many zeros it has at the end, and in one variable we keep the maximum of these values. Once we have gone through all the vectors, we know the length of the longest suffix made up only of zeros. We denote this length by the letter d. Now we rearrange the previous formula to make N the subject, so that it is the output of the algorithm, not the input. In place of v we can substitute one, because we expect to find exactly one such vector, that is, we expect v=1 to hold.
So once we find the length d of the longest zero suffix, we estimate the cardinality using the formula N=2d.
How to get random binary vectors
With random binary vectors the algorithm already works, but how do we apply this procedure to real data? As usual, here too we use a suitable hash function. If the input is a data set, for example IDs (strings), we hash them first. The output of an n-bit hash function is n bits which, from a practical point of view, look like randomly generated binary vectors.
Now we can write down our algorithm:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
The function trailing_zeroes returns the number of zeros at the end of a number. How does it do that? If you did not understand it from the code, you had better not ask. And how successful is the function? For a set that contained a hundred thousand distinct elements, the function returned an estimate of 524,288.
Well…
I mean, that’s not exactly good, is it? But never mind! We will try to improve the algorithm in exactly the same way as with the previous Min Value. We split the input data into several disjoint groups, for each group we calculate the longest zero suffix, then we calculate the average length of the zero suffix and use that to estimate the number of distinct values.
We could say, for example, that the last two bits of each vector determine the number of the group the vector belongs to. These six vectors
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
can be split into four groups according to how they end:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Next we find the length of the longest zero suffix in each vector, but we skip the bits we used as the group number. We mark the zero “suffixes” in green:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
At the end we have the lengths of the longest zero suffixes in each group. From these we can calculate the arithmetic mean, which comes out as 2.75. We substitute that value into the formula and get
This gives us the average number of distinct elements in each group. That obviously does not fit at all, but let's not worry about it — for small sets the LogLog algorithm gives dreadful results.
To estimate the cardinality of the whole set, we still have to multiply this value by the number of groups: 6.727 · 4 = 26.908. The algorithm calculated that the set contains approximately 27 distinct values. There were six, so it is completely off, but that really does not matter right now.
Implementing the algorithm
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
The parameter k determines how many bits will be taken as the group index. This parameter determines the accuracy of the algorithm — the higher k, the greater the accuracy. The variable bucket_index holds the number of the group. How does the magic on the right-hand side of the equals sign work?
The variable num_buckets holds the number of groups, which is always a power of two. If, for example, k = 3, then num_buckets=8. In binary, the number 8 is 1000. If we subtract one, we get 7, which is 0111. Subtracting one from num_buckets always gives a number that has k ones at the end and nothing but zeros before them. Next we apply a bitwise AND (that is the operator &). For the vector 1110110010100101, the operation would look like this:
1110110010100101
& 0000000000000111
------------------
0000000000000101
The point of all that magic is to get a number that has nothing but zeros at the start and whose last k bits are the same as those of the given hash h.
Next we calculate bucket_hash, which is the original hash with the last k bits removed by shifting the whole hash k bits to the right. A shift simply moves all the bits in the number k places to the right and fills the number up with zeros on the left. (A bit shift right by one behaves the same as dividing the number by two and discarding the remainder.) From the vector 1110110010100101, a shift by three would give 0001110110010100. This vector would be stored in the variable bucket_hash.
Next we count the zeros at the end of this vector, and if this value is greater than the current maximum stored in the array max_zeroes at the index bucket_index, we overwrite the value.
At the end we just calculate the average number of zeros across all the groups and work out the average number of distinct elements in each group (2 ** average_max_zeros). Since we have num_buckets groups in total, we multiply this value by the number of groups, which gives the final estimate of the number of distinct elements. Phew, and that didn’t even hurt. The results for several data sets containing 250,000 distinct elements and k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Noooo, still wrong :-(. But we are already quite close, don't worry. Notice that all the results are larger than the correct result. Various errors accumulate during the algorithm, so the estimate is noticeably larger than the correct result. However, these errors are fairly constant and we can estimate how big the error was. If we multiply the estimate by the fudge factor 0.79402, we get results that are much better:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
I also tried a multiset with a cardinality of one million, and the results were:
Result Error
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Nice! The error stays below 2.5%, which is a decent performance. And that, ladies and gentlemen, is the LogLog algorithm. The final implementation, including the fudge factor, looks like this:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
How to modify this algorithm to get the legendary and very best HyperLogLog, we will cover next time. For now, let's look at how much memory the algorithm needs.
Memory requirements
The algorithm is very efficient when it comes to the memory it uses. All we need to remember is the array holding the maxima. The length of this array depends on the value of k, that is, the number of bits of the vector that we take as the group index. For a given k we have 2k different groups in total, so the array of maxima has length 2k. In the implementation we called this value num_buckets.
How big does one cell of the array need to be? We will store the lengths of zero suffixes in it. I can tell you in advance that a 64-bit hash is probably enough for every multiset in the world you could think of, so this array must be able to hold numbers from 0 (a vector made up entirely of ones) to 64 (a vector made up entirely of zeros). Furthermore, if we assume that k will always be greater than zero, then it is enough to store numbers from 0 to 63. For that, mind you, 6 bits are enough, because 26 = 64.
Yes, all we need is an “array” in which one cell is 6 bits in size. I can also tell you that the value k=10 is enough to estimate the cardinality quite decently up to the hundreds of millions. An algorithm set up like this would create an array of size 210 = 1024 in which each cell takes up 6 bits. In total, this array would take up 6144 bits, which is 768 bytes. Not even a kilobyte.
And that is all.
We do not need to store anything else; we can throw the calculated hashes away straight after use, since all we need to know is the number of zeros at the end of the vector.
Notice that if you used a larger hash function, one that returned 128 bits, say, the memory requirements would not change much. We would need to store numbers from 0 to 127, and 7 bits are enough for that. So the memory requirements are determined mainly by the parameter k, that is, the number of groups.
LogLog is suited above all to cases where we need to count multisets of really large cardinality. As the simple example above showed, LogLog does not cope ideally with multisets of small cardinality. That too can be fixed, for example by using another algorithm for the estimate when we find that the multiset has a low cardinality, such as the Linear Counting described earlier. We will come back to that next time too.
Sources:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (the LogLog code is more or less lifted from there)
Chapters: Linear counting: how to estimate the number of distinct values, Min Value: how to estimate the number of distinct values, LogLog: how to estimate the number of distinct values, HyperLogLog: how to accurately estimate the number of distinct values
