Sketches and Sampling: Counting Big Streams in Small Memory

Why summaries. Counting exactly how many different visitors saw a page needs a set of every visitor id, which grows with the audience. Counting every word's frequency needs a counter per word. On a stream of billions of events, memory and merging across machines are the real limits. A sketch has a fixed size, can be updated in one pass, and can be combined across servers.

HyperLogLog (distinct count). Hash every item to a random-looking bit string. If you have seen a hash that starts with k zeros, you have probably seen about 2^k distinct items, because that pattern is rare. One such guess is noisy, so the sketch splits items into m buckets by the first bits and keeps the longest run of zeros per bucket, then averages. The relative error is about 1.04 divided by the square root of m. With m = 16,384 buckets (about 12 KB) the error is about 0.8%, whether the stream holds a thousand or a billion distinct items. Two sketches merge by taking the larger value in each bucket.

Count-min sketch (frequency). Keep a small grid of counters with several rows, each row with its own hash function. To count an item, add one to one counter in every row. To estimate it, read its counter in every row and take the smallest. Collisions only ever add to a counter, so the estimate never undercounts and can overcount. More columns reduce the overcount; more rows reduce the chance of a bad one.

Misra-Gries (heavy hitters). To find items that make up more than 1/k of the stream, keep k minus 1 counters. If the item has a counter, add one. If there is a free counter, start one. Otherwise subtract one from every counter and drop those that reach zero. Any item that occurs more than n/k times is guaranteed to still be there at the end. The counts are lower bounds, so a second pass (or a count-min sketch) can confirm them.

def misra_gries(stream, k):
    counters = {}
    for x in stream:
        if x in counters:
            counters[x] += 1
        elif len(counters) < k - 1:
            counters[x] = 1
        else:
            for key in list(counters):
                counters[key] -= 1
                if counters[key] == 0:
                    del counters[key]
    return counters

stream = list('aabacabadaeaabaa')   # 16 items: 'a' appears 10 times
print(misra_gries(stream, k=3))      # {'a': 7}   'a' is above 16/3, so it survives (true count 10)

Bloom filter (seen before?). A bit array and k hash functions. Adding an item sets its k bits; checking an item says 'maybe present' only if all k of its bits are set, and 'definitely not present' otherwise. It can give false positives but never false negatives. With about 10 bits per item and 7 hash functions, the false positive rate is roughly 1%. A deduplication service uses one to skip the expensive lookup for items it has definitely never seen, and an LSM tree uses one to skip files that cannot hold a key.

Reservoir sampling (a fair sample). To keep k items chosen uniformly from a stream of unknown length, fill a reservoir with the first k. For the item at position i (counting from 1), pick a random number from 1 to i; if it is at most k, the item replaces a random slot in the reservoir. Every item ends up in the sample with probability exactly k/i at the end, and you never need to know the length ahead of time.

import random

def reservoir(stream, k, rng):
    sample = []
    for i, x in enumerate(stream, start=1):
        if i <= k:
            sample.append(x)
        else:
            j = rng.randint(1, i)
            if j <= k:
                sample[j - 1] = x
    return sample

rng = random.Random(1)
hits = [0] * 10
for _ in range(20000):
    for x in reservoir(range(10), 3, rng):
        hits[x] += 1
print([round(h / 20000, 2) for h in hits])   # every item lands near 3/10 = 0.3

Choosing. Use HyperLogLog for unique visitors, distinct users and cardinality in a database. Use a count-min sketch plus a small heap of the top items for trending topics. Use Misra-Gries when you want the heavy items with a guarantee and almost no memory. Use reservoir sampling for fair samples of logs or traces. In an interview, say the error is the price of the fixed memory and name how you would merge sketches from many servers.