Counting uniques using only O(1 byte)

There are occasions when you need to know how many unique entries there are in an array or how many unique values have been seen in a stream, but do not need the exact number.

You may have limited storage, or it is inconvenient to store structured and ever-growing data such as sets or hash tables. It may also be the case that the values themselves cannot be stored for privacy reasons, or even that the data is too vast to be kept in memory, even in a compressed form.

Examples might be counting the number of unique IP addresses that have made requests to a Web server, counting the number of unique words or word groupings in a large corpus of text, or counting the unique gene sequences across gigabytes of genetic data.

There is a method of approximately counting the number of unique values using only a single byte of storage, which can account for up to 2^255 unique values and takes O(1) time to add a value.

Each value only needs to be seen once, the process of adding the value to the count is idempotent and takes O(1).

Custom buckets can be used to increase the accuracy of the count in ranges that matter.

How it works

The data structure is a single byte, which starts at 0.

To add a value to the structure, it is hashed and the number of zeroes at the end of the hash is counted. On average every 1/2 of the values will have one zero at the end of its hash, 1/4 will have two, 1/8 will have three, etc.

The byte is updated to the highest number of zeroes seen at the start of any hash so far.

That's it.

To get the approximate number of unique values you use the fact that if the byte's value is 1, there have been around 2 unique values seen, if it is 2, around 4 unique values, if it is 3, then around 8 values, etc.

The approximate number of unique values is 2 ^ byte_value, or 1 << byte_value.

Implementation

Here is the Rust code to implement this, which takes a mutable byte and the 256-bit hash of the value being added:

fn add_value(byte: &mut u8, hash: &[u8; 32]) {
    let mut count = 0;
    for i in (0..32) {
        if hash[i] == 0 {
            //  Skip over a whole byte, adding 8 zeros to the count
            count += 8;
        } else {
            //  Count individual zeros
            let mut value = hash[i];
            while value & 1 == 0 {
                count += 1;
                value >>= 1;
            }
            break;
        }
    }
    if count > *byte {
        *byte = count;
    }
}

And an example of its usage:

```rust

fn main() {
    //  Initialise the data structure
    let mut byte = 0;

    //  Calculate the hashes of 5 strings and add them to the byte
    let hash1 = sha256::digest("String 1".as_bytes());
    let hash2 = sha256::digest("String 1".as_bytes());
    let hash3 = sha256::digest("String 1".as_bytes());
    let hash4 = sha256::digest("String 1".as_bytes());
    let hash5 = sha256::digest("String 1".as_bytes());
    add_value(&mut byte, &hash1);
    add_value(&mut byte, &hash2);
    add_value(&mut byte, &hash3);
    add_value(&mut byte, &hash4);
    add_value(&mut byte, &hash5);

    //  Show the estimate
    println!("Unique values (approximate): {}", 1 << byte);
}

Conclusion

Often you do not require exact counts of unique values, and there is a lot of machinery involved to get the exact count, including managing the storage of an ever-growing data structure.

Sometimes one byte is all you need.

Future work

This method could be extended to allow for custom buckets, each with a range of unique value counts, for instance you might be interested in whether the count is 1..100, 100..1000, etc. The byte can support any 256 bucket ranges, by suitably mapping the hash value before counting the zeros.