Min Value: how to estimate the number of distinct values

In the previous article about Linear Counting we went through the basic algorithms for calculating and estimating the number of distinct values in a data set. Today we have another probabilistic algorithm, one that can estimate the number of distinct values with decent accuracy and a small memory footprint.

Min Value

In this article we will only work with real numbers from the unit interval (0, 1). Imagine a set of numbers from this interval that is spread out evenly, for example the set {0.25, 0.5, 0.75}. Neighbouring numbers are always exactly 0.25 apart (and the outermost ones are 0.25 from zero and from one). How does that help us count the distinct elements?

Suppose I tell you that we have an evenly spread set of numbers from the unit interval, and that the distance between neighbouring numbers is exactly 0.2 — can you work out how many elements the set has? Of course, it is the set {0.2, 0.4, 0.6, 0.8}, whose cardinality is four. If the input is evenly spread numbers from the unit interval and we know the distance between neighbouring numbers, we can easily calculate the number of elements.

The distance between neighbouring numbers is equal to the smallest element of the set — the distance between neighbouring elements of the set {0.25, 0.5, 0.75} is 0.25, and so on. To calculate the number of evenly spread elements, all we need is some way of finding the smallest element. Then we can calculate the number of elements p with a simple formula:

$$p=\frac{1}{m}-1$$

where m is that smallest element.

And we are going to hash again…

All very well, but how do we use this when the input is strings or other values that do not happen to be evenly spread over the unit interval? Once again we can turn to a good old hash function, which can turn any input into a rational number from the unit interval. Building such a hash function is easy.

That gives us rational numbers from the data, but how do we make sure they are evenly spread? We cannot, strictly speaking, but there is a way round it. From our point of view, a hash function behaves quite “randomly”. For very similar words such as “hello”, “hellp” and “hellq”, the hash function will most likely return very different checksums. In other words: if we hash a thousand different values into the unit interval, it is very unlikely that a clear majority of the numbers will, say, be smaller than one half. On the contrary, it is very likely that the numbers will be spread more or less regularly. The more data we hash, the more regular the spread becomes.

This idea gives us a simple algorithm: go through the input data, hash each element into the unit interval and remember the smallest one. Then estimate the number of distinct elements using the formula above. An implementation in Python:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

The function unit_interval_hash returns a decimal number from the interval (0, 1]. The function count_unique_using_minimum first converts all the input values into such a number, finds the minimum and returns 1 / minimum - 1. Notice that it makes no difference how many identical values there are in the data — for two identical values the hash function returns the same rational number, which does not affect the resulting minimum at all. That is why this algorithm counts distinct elements.

So what are the results? (Each line shows an estimated cardinality; the true cardinality is 10,000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Not great, is it? The algorithm ran through ten different sets of IDs, each with ten thousand distinct values. The estimates it came up with are mostly well off. If we averaged them, we would get 18,352. Still well off, but on the other hand look at the memory requirements — they are constant! To find the minimum, all you need to keep in memory is one variable holding the current minimum, and that is it. So yes, the estimate is rubbish, but it costs almost nothing.

Improving it

We can see that the algorithm is above all unstable — one time it gives us a fairly good estimate (9362), another time an estimate that is completely off (65536). How do we get out of this? We can split the input data into several parts, count the distinct elements in each part and finally average it all out. We could decide by the first character of our ID. So we count the distinct values separately for IDs starting with the letter “a”, then for those starting with “b”, and so on. The code:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

The changes are in the function count_unique_using_minimum. In the variable min_values we keep the minimum for each group. At the end we add up all the minima and divide by the number of stored values — this gives us the average minimum. The expression 1/average_minimum tells us the average number of distinct values in each group — we then multiply this by the number of groups, and that gives the estimated number of distinct values in the data set we were given. And how does this modified procedure perform?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Well, it is still not good, but it is certainly better. The algorithm is more stable. We can try changing the function so that the groups are formed not by the first character but, for example, by the first two characters of the ID, like this:

first_char = str(item)[0:2] # ToDo: choose better name for variable

The results would then look like this:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Well now, that’s not too bad, is it? If we also try a hundred thousand distinct values, the first two characters and n = 24, we get these results:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

That is reasonably good. But there are still better algorithms, don't worry.

And what about memory? We have to keep the minimum for each group, nothing more. If the IDs are in hex format, that means we have to remember at most 16^x minima, where x is the number of characters we build the group key from. One minimum is one rational number, that is, some double or float type.

A final note: we could afford to split the input into several groups because the input was IDs that behaved like random strings. If the input were not random strings but data in some particular format, we would have to do the split differently. If, for example, every ID started with the prefix userid-, splitting into groups by the first character probably wouldn’t work very well, would it?