Problem Detail: 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?
Asked By : user220201
Answered By : Wandering Logic
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12834
