Question 2: Bloom Filters A bloom filter is a fast set data structure that maintains a set 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 I different hash functions hi....,h. Initially. T[i] = FALSE for all i. If a key k is to be inserted we first compute i = hi(k), ... , l = hi(k) and then we set T[i] = ... T[i] = TRUE. Note: A bloom filter is not a hash table, but they both use hash functions in interesting ways. (A) Suppose we wish to find out if an element k is a member of the set by checking if T[h1(k)),...,1[h(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 k does not belong to the set when it does. (B) Suppose our hash functions are guaranteed to be uniform. Ie, for any randomly chosen key k, for any hash function h; and cellj, 1 P(h: (k) = j) = m 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.l.e, some I cells i1, 12, ..., i are simultaneously set to TRUE. Question 2: Bloom Filters A bloom filter is a fast set data structure that maintains a set 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 I different hash functions hi....,h. Initially. T[i] = FALSE for all i. If a key k is to be inserted we first compute i = hi(k), ... , l = hi(k) and then we set T[i] = ... T[i] = TRUE. Note: A bloom filter is not a hash table, but they both use hash functions in interesting ways. (A) Suppose we wish to find out if an element k is a member of the set by checking if T[h1(k)),...,1[h(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 k does not belong to the set when it does. (B) Suppose our hash functions are guaranteed to be uniform. Ie, for any randomly chosen key k, for any hash function h; and cellj, 1 P(h: (k) = j) = m 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.l.e, some I cells i1, 12, ..., i are simultaneously set to TRUE
