0
$\begingroup$

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?

$\endgroup$

4 Answers 4

4
$\begingroup$

$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.

$\endgroup$
7
  • $\begingroup$ I know that $m$ is total bits in filter (not per entry). But makes no sense. A hashing function would identify approximately $2^m$ many inputs uniquely. $\endgroup$
    – caveman
    Oct 15, 2022 at 6:57
  • 1
    $\begingroup$ @caveman, "A hashing function would identify approximately $2^m$ many inputs uniquely" - I think you would want to clarify in the question what exactly you mean: i.e. exactly which data structure you suggest which achieves a much smaller error rate (and what this error rate is) and uses only 10 bits overall. In the question, "simply using the few bits of a cryptographically hashing function" doesn't describe what "using" means. I believe the benrg's answer fully addresses the concern currently stated in the question. $\endgroup$
    – Dmitry
    Oct 15, 2022 at 7:16
  • $\begingroup$ @Dmitry - from my understanding is that the bloom filter can be used to tell whether an input element is member of a set, without actually storing the entire set. I was hoping that the number of elements that a bloom filter can tell whether they're members in a set to be exponentially more than its filters bit length, but it turns out not the case. $\endgroup$
    – caveman
    Oct 15, 2022 at 7:21
  • 1
    $\begingroup$ @caveman, It is exponentially more (in fact, infinitely more, but one-sided). What you suggest (if I understood you correctly) answers the question "is $x$ in the set" 100% correctly for $m$ fixed elements, and knows nothing else about the rest of the domain. On the other hand, if at least one bit in Bloom's filter is not set (which in your example happens with small, but non-negligible probability), then Bloom's filter gives a correct reply "$x$ is not in the set" for infinitely many elements (for the rest of the domain, it again doesn't know). $\endgroup$
    – Dmitry
    Oct 15, 2022 at 7:38
  • 3
    $\begingroup$ @caveman, I thought you would add a few clarifications to your question. Since you changed the question completely, you should instead revert your changes, accept this answer (if you agree that it answers the question as it was stated), and ask the new question. A general rule: you shouldn't change the question in a way that completely invalidates the existing answers. $\endgroup$
    – Dmitry
    Oct 15, 2022 at 15:40
2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Where did you get 1000 bits? Also my scheme's fault is that it does not store set membership (it only gives unique-ish identifiers). $\endgroup$
    – caveman
    Oct 16, 2022 at 23:51
  • 1
    $\begingroup$ @caveman, see edited answer. $\endgroup$
    – D.W.
    Oct 17, 2022 at 3:55
1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.