A bloom filter is a fast set data structure that maintains a set S of keys. One can insert keys into the set and test whether a given key k belongs to the set. It may used in applications where the keys are "complicated" objects such as TCP packets or images that are expensive to compare with each other.

The data structure is an array T of Booleans size m with l different hash functions 1,,h1,,hl. Initially, T[i] = FALSE for all i.

If a key k is to be inserted we first compute 1=1(),,=()i1=h1(k),,il=hl(k) and then we set [1]=[]=TRUET[i1]=T[il]=TRUE.

(A) Suppose we wish to find out if an element k is a member of the set by checking if [1()],,[()]T[h1(k)],,T[hl(k)] are all true. Explain whether this can lead to a false positive i.e, the approach wrongly concludes that k belongs to the set when it was never inserted; or false negative i.e, the approach wrongly concludes that kdoes not belong to the set when it does.

(B) Suppose our hash functions are guaranteed to be uniform. I.e, for any randomly chosen key k, for any hash function hi and cell j,

(()=)=1P(hi(k)=j)=1m

If n keys are chosen at random and inserted into the filter, compute that probability that any given cell []T[j] is set to FALSE after this.

(C) Use the results from previous set to estimate the probabilisty of a false positive. I.e, some l cells 1,2,,i1,i2,,il are simultaneously set to TRUE.