Why do Bloom filters work?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

The short answer is yes. Because of information theoretical bounds, any probabilistic data structure representing a set that stores arbitrarily large keys with bounded space per key and lets you query arbitrary data for membership must use $\log_2(1/\epsilon)$ bits per inserted element, where $\epsilon$ is the false positive rate. Afaik, optimal bloom filters use $\sqrt{2}\log_2(1/\epsilon)$ bits per element. Cuckoo filters can outperform in space but have other tradeoffs.

The advantage of probabilistic filters is not that you avoid linear space bounds, but that they don't require you to store the elements (so the coefficient of the linear growth is very small), and so their size is independent of the type of data you originally stored in them. Furthermore, adding a new element is cheap.

However, bloom filters specifically do not actually save space or lookup time over taking the last $\log_2(1/\epsilon)$ bits of a good hash function (any suboptimality of hash functions affects bloom tables as well), storing them in a sorted array, and checking set membership with binary search. What they do offer over that is that it is cheap to store one extra element in the filter. Putting the last-bits of hashes in an exact set (BTree, cuckoo hash, etc etc) is the other way to do this, with a few practical tradeoffs vs bloom filters. Bloom filters have the advantage of having reliable asymptotics for every operation and no amortized big-O's.