Bloom filter

Have we seen this star before? A star catalogue squeezed into a row of bits. Each star lights k bits; a new star whose bits are all lit already is a ghost, a false yes. A "no" is always right.

m bits512 k hashes3 n stars80 width w24 depth d4 sightings800 seed

The numbers

false positives as stars arrivemeasured vs formula

false positives against kbest k marked

bits litfill against 1 - e^(-kn/m)

How it works

A Bloom filter is m bits, all off, and k hash functions. To add a star, hash its name k ways and switch on those k bits. To ask "have we seen it?", hash it the same way and look: if any of its bits is off, the answer is a certain no. If all are on, the answer is maybe, because other stars may have lit those bits between them. That maybe-but-wrong is a false positive, a ghost star.

More hashes mark each star more firmly but fill the array faster. The sweet spot is k = (m / n) ln 2, which leaves about half the bits lit. At that k, about 9.6 bits per star give 1% false positives, whatever the stars are, against storing every name in full.

The count-min sketch swaps bits for counters to answer "how often?". It keeps d rows of w counters; each sighting adds one in every row, and a star's count is the smallest of its d counters. Collisions only ever add, so the estimate is never too low, and the overcount is at most εN with high probability.

a few hundred bits answer "never seen it" with certainty, and you choose exactly how often "maybe" is allowed to lie.

P(false positive) ≈ (1 - e^-kn/m)^km bits, n stars added, k hashes. Each bit stays off with chance e^-kn/m.

k* = (m / n) ln 2 m / n = -ln p / (ln 2)²the best k, and the bits per star needed for a target false positive rate p.

count ≤ estimate ≤ count + εN
ε = e / w, δ = e^-dcount-min: the upper bound holds with probability 1 - δ. N is the total of all counts.