What is the point of Bloom's filter if its false positive rate is so high?

Question

This and this agree that there will be near 100% false positive rate with Bloom's filter should number of elements in the set ($n$) be greater than the number of bits in the filter ($m$).

E.g. if $n=100$, $m=10$ with a single hashing function $k=1$, then we get a probability of false positives worth:

$$\begin{split} p &= \left(1-e^{kn/m}\right)^k\\ &= \left(1-e^{k100/10}\right)^1\\ &= 0.9999546000702375\\ \end{split}$$

I.e. almost every query will be a false positive.

I find this to be useless, as such small filters are meant to reduce set membership queries to a database with much larger number of elements that there are bits in the filter.

In this example ($n=100$, $m=10$), I can achieve a much lower false positives rate if I simply use the first $10$ bits of a cryptographically secure hash function. E.g.

for i in 0,1,...,99:
  print(hash10bit(i))

where hash10bit(i) returns the first $10$ bits of a cryptographically secure hash function, such as ChaCha20, when given $i$ as input. This implies a logarithmic growth in number of bits.

---

Question:

So, why would one use Bloom's filter, if simply using the few bits of a cryptographically hashing function does a much better job?

Or is it that I'm missing something fundamental? What is it?

Answer 1

$m$ is the total size of the filter in bits, not the number of bits per entry. With $m=1000$ the formula gives a false positive rate of around 10%, roughly the same as the 1000-bit list of hashes (whose false positive rate is 100/1024 if all hashes are distinct).

With $k=3$ and $m=500$ you get a false positive rate of around 9% at half the size of the list of hashes. The advantage is larger for larger $n$ because the (approximate) false positive rate only depends on $m/n$. E.g., with 1,000,000 items, a list of 10-bit hashes would be useless, but you can still get a 9% false-positive rate at 5 bits per item with the Bloom filter.

Answer 2

No, your proposed scheme with cryptographic hash functions does not do a better job than Bloom filters. Your scheme outputs $10n$ bits, which is way more than $m$ bits. You are comparing a Bloom filter that uses just 10 bits to your scheme, which uses 1000 bits. Obviously those two are not comparable. Obviously a scheme that uses 1000 bits can achieve a far lower false positive rate than a Bloom filter.

Your scheme uses 1000 bits, because it outputs 100 values, and each value is 10 bits long (it is the first 10 bits of a cryptographic hash).

Answer 3

Sure, you can store an approximate representation with only log storage, but the error rate will be insanely high, so it will likely be useless in practice. For instance, one approximate representation is to store the first $\log |\mathcal{S}|$ entries of $\mathcal{S}$.

Note that, at least with the most natural representation, the space complexity of $f$ is $O(|\mathcal{S}| \log n)$, not $O(|\mathcal{S}|)$, since you have to store $\mathcal{S}$ entries and each entry takes $\lg n$ bits to store.

I recommend reading about Bloom filters.

Answer 4

Bloom's filter has a high false positive rate because it only detects whether an element is in the set or not, without providing any information about the position of the element.

However, despite its high false positive rate, Bloom's filter can be very useful in certain situations. For example, if you only need to know whether an element is in a set or not, and you don't need to know its position, then Bloom's filter is a good choice. Additionally, Bloom's filter can be more efficient than other data structures when storing large sets of data.