4. Approximate Membership and Bloom Filters

A different problem from dictionaries: the membership problem. 48:12 48:42

Problem statement

Maintain S ⊆ U under two operations: 48:42
- update(x): S ← S ∪ {x} (insertions only, no deletions). 49:14 52:27
- query(x): is x ∈ S? 49:14
No values, only keys — unlike dictionaries, which associate values with keys. 49:14
The space goal drives everything: dictionaries use n words (≈ n log|U| bits); membership aims for n bits. 49:57

Assume n is known and the problem is static. 52:27

Correctness:

No false negatives is immediate: the bit was set on insertion. 53:39
For x ∉ S, a false positive means ∃ y ∈ S with h(x) = h(y). 54:18
Union bound over the n candidates y, each colliding with probability 1/m: n · (1/m) = 1/2. 54:50 56:56
Only 2-wise independence is needed, because every argument reasons about exactly two hash evaluations at a time. 1:05:33 1:05:54

A 50% false-positive rate is unusable in practice — a user wants 0.01%, not 50%. 56:56 57:27

Two options are proposed by the class:

Approach	Space	Query time
Widen the array to `m = n/ε` (so `n/m = ε`) `58:22` `58:35`	`n/ε` bits	`O(1)`
`log(1/ε)` independent copies, each of length `m = 2n` `58:45`	`n·log(1/ε)` bits	`O(log 1/ε)`

The repetition scheme — this is the Bloom filter: 58:45 1:00:21

k = log(1/ε) hash functions h_1 … h_k, one per bit array. 58:45
Update writes into every array; query answers yes only if all k bits are set. 59:16
To be fooled you must be fooled k times: 2^{-k} = ε. 59:41
Repeating the same query on the same structure always returns the same answer — boosting requires genuinely independent copies. 52:03 52:14
Due to Bloom, 1970. More sophisticated variants get query time down to constant and support deletions, but are not covered. 1:00:21 1:00:39