wire / wire-format / 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).
aka: Bloom filter
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).
| field | size | meaning |
|---|---|---|
| Bit array | m bits | All bits initialized to 0. |
| Hash functions | k functions | k independent hash functions, each mapping to [0, m-1]. |
| Insert | O(k) | Set bits at h_1(x), h_2(x), ..., h_k(x) to 1. |
| Query | O(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 rate | formula | P ≈ (1 - e^(-kn/m))^k. With optimal k = (m/n)ln(2), P ≈ 0.6185^(m/n). |
| Counting Bloom filter | variant | Uses counters instead of bits. Supports deletion (decrement counters). |
| Cuckoo filter | variant | Uses cuckoo hashing. Supports deletion and has better cache locality. |
example:
00 00 00 00
Bloom filter (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/bloom-filter
or /wire-format/bloom-filter.json