1
$\begingroup$

My first question here. Please do not judge me much if this is a too simple.

Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ probability of false positives. Using well known formulas, the optimal filter size $m$ is computed as

$$m=-\frac{n\log\epsilon}{\log(2)^2}\approx 120\, 000.$$

The optimal number of hash functions $k$ is computed as

$$k=\frac{m}{n}\log{2}\approx 6.6.$$

It is suggested that suboptimal number, i.e. $k=6$ might even be better for performance reason.

That's all very fine in theory. In practice, we have excellent (and probably too expensive, but let's use them as an illustration) hash functions SHA-256. They have length of only 256 bits. Thus, $m=256$ necessarily! We put $n=12500$ and $m=256$ in the formula for the probability of false positives $$\epsilon=\left(1-e^{-kn/m}\right)^k$$ and get this plot

enter image description here

Thus, no matter what I do, with 256-bits hash functions I cannot reduce the probability even below 99%! What can I do? Is the Bloom filter useless in my case?

I was thinking to "glue" $120000/256\approx 469$ hash functions together. But then I need $469\times6 =2814$ expensive SHA-256 evaluations per one filter operation.

$\endgroup$

1 Answer 1

1
$\begingroup$

When using SHA256, the maximum possible filter size is $m=2^{256}$. A 256-bit value can index into $2^{256}$ possible indices into the array. This is more than adequate.

For instance, a 3-bit hash function could be used to index into an array of length $m=8$.

$\endgroup$
1
  • $\begingroup$ Right, that was a stupid question as I was suspecting, embarrassing. Thank you for your patience! $\endgroup$
    – yarchik
    Feb 11 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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