wire / wire-format / bloom-filter

Bloom filter

A Bloom filter is a probabilistic data structure for set membership testing. Structure: bit array of m bits, k hash functions. Insert: set bits at positions h_1(x), h_2(x), ..., h_k(x). Query: check if all k bits are 1. False positives possible; false negatives impossible. False positive rate ≈ (1 - e^(-kn/m))^k. Optimal k = (m/n) * ln(2).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Bloom filter

wire format

spec: Bloom filter (Burton Bloom, 1970)

A Bloom filter is a probabilistic data structure for set membership testing. Structure: bit array of m bits, k hash functions. Insert: set bits at positions h_1(x), h_2(x), ..., h_k(x). Query: check if all k bits are 1. False positives possible; false negatives impossible. False positive rate ≈ (1 - e^(-kn/m))^k. Optimal k = (m/n) * ln(2).

fieldsizemeaning
Bit arraym bitsAll bits initialized to 0.
Hash functionsk functionsk independent hash functions, each mapping to [0, m-1].
InsertO(k)Set bits at h_1(x), h_2(x), ..., h_k(x) to 1.
QueryO(k)Check if all bits at h_1(x), ..., h_k(x) are 1. If yes, probably in set. If any is 0, definitely not in set.
False positive rateformulaP ≈ (1 - e^(-kn/m))^k. With optimal k = (m/n)ln(2), P ≈ 0.6185^(m/n).
Counting Bloom filtervariantUses counters instead of bits. Supports deletion (decrement counters).
Cuckoo filtervariantUses cuckoo hashing. Supports deletion and has better cache locality.

example:

00 00 00 00

Bloom filter (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/bloom-filter or /wire-format/bloom-filter.json