4
$\begingroup$

Let's say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a given number of words, wouldn't the whole bit bucket be all 1s? If so then checking for any word will return true? What am I missing here?

$\endgroup$
6
$\begingroup$

Given that you want to insert $n$ words into the Bloom filter, and you want a false positive probability of $p$, the wikipedia page on Bloom filters gives the following formulas for choosing $m$, the number of bits in your table and $k$, the number of hash functions that you are going to use. They give $ m = - \frac{n \ln p}{(\ln 2)^2} $ and $$ k = \frac{m}{n}\ln 2=-\frac{\ln p}{\ln 2}=-\lg_2p, $$ so you should choose $$ m=\frac{nk}{\ln 2}. $$

That actually works out quite nicely. You are going to get a table with about half the bits set and half cleared, so the entropy per bit is going to be maximal, and the probability of a false positive is going to be $0.5^k$.

$\endgroup$
3
$\begingroup$

This is how I use Bloom filter: suppose that full dictionary check is 10x slower than checking a bit in the Bloom filter. Then if you make a Bloom filter having $N$ bits per dictionary word, then average time required for one check would be $1+10/N$. For example, with $N=8$ (i.e., use one byte in Bloom filter per dictionary word), the avg.time will be 2.25 units, i.e., more than 4 times less than 10 units required without Bloom filter.

So, you trade space occupied by Bloom filter for a time spent by each dictionary check. Of course, you also need time to build the filter hash table.

$\endgroup$
2
$\begingroup$

You choose the size of your Bloom filter according to the expected occupancy. If your Bloom filter is full of 1s then it's too small for the number of words you're putting it. Words in a document tend to repeat, so when estimating how big the filter should be, count the number of unique words in your document.

$\endgroup$

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.