Bloom Filters, HyperLogLog & MinHash-LSH

The data engineer’s quiet motto: exactly correct costs a lot; probably correct often costs almost nothing.

Probabilistic data structures spend a small, bounded, tunable amount of inaccuracy to buy savings that are otherwise impossible — structures that fit in kilobytes instead of gigabytes, or finish in milliseconds instead of hours. Three of them turn up everywhere, and together they answer the three core questions of scale-out data work: have I seen this before?, how many distinct things have I seen?, and which things are nearly the same?

Bloom filters: probably-in, definitely-out

A Bloom filter answers one question — is this item in the set? — but only in two of the three possible ways. It can say “definitely not” or “probably yes”. It can never say “definitely yes”, and that asymmetry is the whole trick.

The structure is a bit array of m zeros plus k independent hash functions. To add an item, hash it k ways and set each of those bits to 1. To query, hash it the same k ways and read those bits: if any is 0, the item was certainly never added (a 0 can only survive if nothing set it); if all are 1, the item is probably present — though those bits might have been set by other items, which is a false positive.

The false-positive rate is tunable through m, n (items inserted), and k, with the optimum at k = (m/n)·ln 2. The payoff is dramatic: a Bloom filter for one million items at a 1% false-positive rate needs about 9.6 million bits — roughly 1.2 MB — against many gigabytes for an exact hash set of the same keys. The cost is that it cannot delete, cannot list its members, and only ever answers membership. The structure is small enough to keep in code as a sketch:

import math

class BloomFilter:
    def __init__(self, capacity, fp_rate):
        self.m = math.ceil(-capacity * math.log(fp_rate) / (math.log(2) ** 2))
        self.k = max(1, round((self.m / capacity) * math.log(2)))
        self.bits = [0] * self.m
    def _positions(self, item):
        # k independent positions (a real one uses k good hash functions)
        return [hash((seed, item)) % self.m for seed in range(self.k)]
    def add(self, item):
        for p in self._positions(item):
            self.bits[p] = 1
    def __contains__(self, item):
        return all(self.bits[p] for p in self._positions(item))

Whatever you add will always test as present — there are no false negatives, by construction. Only a never-added item can ever wrongly test present, and only at the rate you chose.

HyperLogLog: counting distinct in kilobytes

How many distinct IPs hit the server today? Counting distinct values exactly means remembering every distinct value — gigabytes at scale. HyperLogLog estimates that count to within about 1-2% using a few kilobytes, no matter how many items it sees. The trick: hash each item to a uniform bit string and note the length of its leading run of zeros. A run of k zeros happens with probability 1/2ᵏ, so seeing a run of length k hints that you have processed on the order of 2ᵏ distinct items. Average that signal across many independent buckets to tame the noise, and a 12 KB register array can report “about 4.3 billion distinct values” with ~1.4% error. This is what PFCOUNT in Redis, approx_count_distinct in Spark, and APPROX_COUNT_DISTINCT in BigQuery all run underneath.

MinHash + LSH: near-duplicates without all-pairs

Which of a million documents are nearly identical? Comparing every pair is O(n²) — hopeless. MinHash compresses each document’s set of shingles into a short signature: for each of t hash functions, keep the minimum hash over the set. The lovely fact is that the probability two signatures agree in a position equals the documents’ Jaccard similarity (shared shingles over total shingles) — so the fraction of matching positions estimates similarity directly, and 200 integers stand in for millions of shingles. LSH then avoids the O(n²) pair comparison by banding: split each 200-hash signature into, say, 20 bands of 10, and hash each band to a bucket. Two documents become candidate pairs only if they collide in at least one band — which happens with sharply rising probability above a similarity threshold. You compare a small candidate set instead of every pair.

Practice