Linear counting: how to estimate the number of distinct values

How could we count the distinct values in some data set if there was really a lot of data? For example, we might have a service that measures the number of unique users on some large website, or even on a whole .cz/.com/.whatever domain or something like that.

The naive approach

OK, there’s nothing to it: we simply go through the data and store each value exactly once in some suitable data structure. In Python we could write it roughly like this (the code is needlessly wordy, on purpose):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

It works. Fine, but what if the data are 36-character unique v4 identifiers and what if there are, say, ten million of these unique IDs? Well, the program still computes the correct value, but how much memory does it take? We can try to work it out. For simplicity, we will assume that we store each UUID as a 36-character string. One UUID therefore takes 36 bytes, and ten million IDs take 360 MB.

That’s not exactly small, let’s admit it. If there were a hundred million unique IDs, we would already be into gigabytes of memory. And that is still counting only what the data themselves take up. Add some overhead from Python or JavaScript and you can reach gigabytes even with ten million IDs:

You don’t want that. How do we get out of it?

We can try to store the IDs themselves more efficiently, or we can use C instead of Python, which cuts the memory requirements substantially, but it still won’t be right and such a program would still take an incredible amount of space. That leaves the question: do we really need to know to the exact digit whether there are 9,563,618 distinct values? Would anything happen if we worked with 9,547,666? If your answer is that yes, it would, and that you want it exact, then be my guest. Otherwise, let’s look at ways to estimate the number of distinct values in a data set as accurately and as quickly as possible, with minimal memory requirements.

Hash functions: our salvation

Consider a hash function that takes a string as input and returns some n-bit number. If you are used to hash functions that “return a string”, just imagine that the string is then converted to a number, which is nothing special. The number of bits says how big the number is. An 8-bit function returns a number that takes up eight bits, and eight bits can hold 2⁸ different values, typically the integers from 0 to 255. From now on we will work with a 24-bit hash function. Such a function returns 2²⁴ different values, which is 16,777,216.

Instead of storing the values themselves, we will store their 24-bit hashes. To store ten million 24-bit hashes we need 30 MB. That is an order of magnitude better than the previous 360 MB. The code could look like this:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

The hash function is a native Python function and returns an integer. The nhash function shows a naive implementation of an n-bit hash function; it isn’t important to understand how it works, because it doesn’t work correctly anyway — its result doesn’t fit in 24 bits, but that doesn’t matter now, I’m after the principle.

Then comes the function count_unique_using_nhash, which counts the distinct values. It goes through all the values, computes their hashes and stores each one in the variable found if it isn’t there already.

The problem with this approach is that a hash function can return the same checksum for different strings — a collision can occur. The more such collisions occur, the less accurate the result. The function count_unique_using_nhash will almost always return a smaller number of distinct values than there really are.

And which hash function should we choose? It doesn’t matter all that much, but generally some variant of MurmurHash is recommended.

Bitmaps

Did you pay attention in your C programming classes? If so, you know bitmaps. How could we use them?

We’ll outline the idea with an array. We don’t have to keep the computed checksums at all: we can create an array of length 2²⁴ and initialise all its elements to zero. Then, whenever we come across a checksum — which is a number! — we write a one into the array at the index checksum, marking that we have already found this checksum. The number of distinct items is then approximately equal to the number of ones in this array. The code could look like this:

def count_unique_using_array(values):
    # a list of length 2^24 initialised to all zeros
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

However, using an array is very memory-hungry here, because in every cell we need to store either a one or a zero. Instead, we can use a bit array. To see how, note that an integer can be stored in, say, 32 bits. If we convert the number 354 to binary, we get 101100010. The number 354 would thus be stored in a computer as a 32-bit integer (let’s skip the details, shall we?) like this:

00000000 00000000 00000001 01100010

That’s quite a nice format that we could make use of, isn’t it? In our function we only want to store ones and zeros, and we have just found out that an ordinary number is nothing but a heap of zeros and ones (like everything in a computer, I suppose…). In short, using bitwise operators we can store a one so that it really takes up just one bit.

Back to our function with the array. If we rewrote it using bit arrays, a bit array of size 2²⁴ bits would be enough for a 24-bit hash function, which is 2 MiB. That’s a decent upgrade!

With a 32-bit hash function, which has 2³² different output values, that is 4,294,967,296, we would need a bit array of half a gigabyte. That’s not bad at all, considering that it lets us count distinct values up to somewhere in the billions.

Linear counting

I have already mentioned that with a hash function we only get an estimate of the number of distinct values. This estimate gets less accurate the closer the number of distinct values gets to the number of different output values of the hash function. It makes sense that if we have a data set with five billion distinct values, a 24-bit hash function simply can’t count them.

However, the estimate we compute using hash functions can be refined further. It uses a simple idea — the more distinct values there are in the data set, the more likely it is that collisions will occur over time. (A collision = two different inputs have the same output from the hash function, the same checksum.) Now we are going to do a bit of calculation, so let’s introduce a few variables:

• We will work with an n-bit hash function h.
• The number of all possible outputs of the function h is therefore equal to 2n. We will denote this number by the letter m, that is: m=2n.
• The bit array in which we store which checksums we have found will be denoted by the capital letter A. The array A has length m.
• When our algorithm has gone through the whole data set, some values in the bit array will be zero and some will be one. What interests us most is the ratio “number of zeros divided by the length of the array”, which gives the relative proportion of zeros in the bit array. At the start this ratio is equal to 1, because the array is initialised to all zeros. If it were fifty-fifty, the ratio would be one half, and so on. We will denote this value by Z and compute it as Z = number of zeros / m.

At this point, the higher the value of Z, the more confident we can be that our estimate of the number of distinct values is accurate. For example, if we go through an empty data set, the bit array stays all zeros and the value of Z is equal to one — so we are completely certain that our data set contains as many distinct items as there are ones in the bit array — zero.

If the value of Z is 0.99, it means that one hundredth of the bit array is filled with ones. 99% of the array contains zeros. That’s still good: it is likely that not too many collisions occurred during the computation, and perhaps no correction at all, or only a minimal one, will be needed. But if the value of Z is 0.05, only 5% of the array remained zero, and we have probably run into many, many collisions during the computation — a big correction will be needed.

But how do we work out this correction? We will use a logarithm, which is a function of this shape:

We are interested in the red part on the interval (0, 1]. If we plot the value of Z on the x-axis, then the higher Z is, the closer the value of y gets to zero. And conversely — the smaller Z is, the smaller y will be. We calculate the final estimate by multiplying this number by -m. Notice that for a sufficiently low value of Z we get a number that is even less than -1, and if we multiply it by -m, we get an estimate greater than m: we have estimated that the number of distinct values is greater than the number of all possible checksums that can come out of the hash function h.

The whole formula for calculating the number p of distinct values would look like this:

$$p=-m\cdot \ln Z$$

An implementation (without bit arrays, with plain arrays only) could look like this:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log here is the natural logarithm with base e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

In the function linear_counting we first compute an initial estimate using the previous algorithm, which uses an n-bit hash function. Then we compute the proportion of zeros in the array and apply the correction according to the formula. The logarithm in the code is the natural logarithm. The variable nonunique_values contains number_of_unique_values distinct strings, so in this example the list nonunique_values contains ten thousand distinct values. The odd-looking code on the sixth line makes sure there are repeated values in the array: we simply append the same list of values to the end of the list, so each value appears in it twice. And then we count. Ideally, the function should return that the list contains ten thousand distinct values. The output:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Because a different list nonunique_values is generated each time, the results will differ from call to call. We used a 16-bit hash function. We can see that the first estimate from the function count_unique_using_array was that the list contains 9,289 distinct values. We refined this estimate with the correction to 10,017, which is quite decent: our estimate is too high by only 0.17%, whereas before it was too low by 7.11% — which is quite a lot.

If we took a “bigger” hash function, for example a 24-bit one, we would get a more accurate result:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

Even the original estimate was OK, and the refinement brought us to exactly ten thousand. For demonstration, we can try a million unique IDs, that is, number_of_unique_values = 1000000. With a 24-bit hash function we get these results:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

That works. And if we implement it as a bit array, the array would eat up only the two megabytes mentioned (+ whatever the language eats up). Pretty good, if you ask me. But we can do better! Much better. But that’s for next time.

In the meantime, you can read the article A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Or you can carry on to the next part of the series: the min-value algorithm.