Questions: Bloom Filters: Space-Efficient Probabilistic Set Membership

Question 1

A Bloom filter query returns 'yes, this element is present.' What can you conclude?

• A. The element is definitely in the set
• B. The element is probably in the set, but a false positive is possible
• C. The element is definitely not in the set
• D. The element was inserted but may have been deleted

Answer: (B)

A 'yes' from a Bloom filter is probabilistic — the k bits could have been set by other elements coincidentally. Only a 'no' answer is definitive: if any of the k bits is 0, the element was definitely never inserted. This asymmetry — guaranteed false negatives are impossible, false positives are possible — is the central property of Bloom filters.

Question 2

A Bloom filter has a 5% false positive rate. You want to reduce it without changing the number of hash functions. What is the most direct approach?

• A. Remove elements you know are in the set to clear their bits
• B. Increase the bit array size m
• C. Decrease the bit array size m to make queries faster
• D. Switch to a standard hash table for the frequently queried elements

Answer: (B)

A larger bit array means fewer bits are 1 per element on average, reducing the probability that all k query bits are coincidentally set by other insertions. The false positive rate falls as m/n (bits per element) increases. You cannot remove elements from a standard Bloom filter — bits are never cleared — so option A is impossible.

Question 3

A Bloom filter can return a false negative — reporting that an element is absent when it was actually inserted.

• T. True
• F. False

Answer: False

This is the core guarantee. When an element is inserted, all k of its hash positions are permanently set to 1. A membership query computes the same k positions — if all are 1, the answer is 'possibly yes'; if any is 0, the element was definitively never inserted. Since bits are never reset to 0, a false negative is structurally impossible in a standard Bloom filter.

Question 4

Increasing the number of hash functions k typically reduces the false positive rate of a Bloom filter.

• T. True
• F. False

Answer: False

More hash functions means more bits are set per insertion, filling the array faster. Past the optimal k = (m/n) · ln 2, adding more hash functions actually increases the false positive rate because the array becomes too dense. The optimal k balances two opposing effects: more checks per query (good) vs. more bits set per insertion (bad).

Question 5

Why can a Bloom filter guarantee no false negatives but cannot guarantee no false positives?

Model answer: When an element is inserted, all k of its hash positions are permanently set to 1 and never cleared. A membership query checks those same k positions — if any is 0, the element was never inserted (guaranteed true negative). But if all k bits are 1, they might have been set by k different other elements, producing a false positive. The guarantee flows from the permanence of 1-bits; the false positive risk flows from bit sharing across inserted elements.

The asymmetry is structural: insertion only sets bits (never clears them), so a missing bit proves absence absolutely. But presence of all k bits only proves that those k positions were set at some point — it cannot distinguish between 'this element set them' and 'other elements coincidentally set them all.' False positive probability depends on how full the array is.