Bloom Filters with Efficient Hash Functions $(10$ points$)$

In the Bloom filter analysis in class, we assume use of a fully independent hash function. Here we

will analyze a variant of Bloom filters that just uses $2-$universal hashing.

Consider a Bloom filter variant consisting of $k$ bit arrays: $A_1,$dots,$A_k,$ each of length $m,$ along

with $k2-$universal hash functions $h_1,$dots,$h_k$:$U[m].$ Assume the hash functions are chosen

independently of each other. To insert an item $x,$ we mark $A_i[h_i(x)]=1$ for all iin$[k].$ To query

if an item $x$ is in the dataset, we check if $A_i[h_i(x)]=1$ for all iin$[k]$ and return 'YES' if this

condition is true.

$(2$ points$)$ Let $x$ be some item that has not been inserted into the filter. Give an upper bound

on $Pr[A_t[h_i(x)]=1]$ as a function of the number of inserted items $n$ and the number of bits

in the array $m.$

$(2$ points$)$ Use the above to give an upper bound on the false positive rate of the filter, as a

function of $n,m,$ and $k.$

$(2$ points$)$ The total space complexity used by the filter is $s=m*k.$ Given a fixed space

budget $s>0,$ prove that the optimal setting of $k($which minimizes the false positive rate

upper bound from part $(2))$ is $k=\frac{1}{e}*\frac{}{n}.$ Note: As with standard Bloom filters, this optimal

setting may not be an integer.

$(2$ points$)$ Using the above optimal setting of $k,$ to store $n$ items with false positive rate $$ in

this data structure, how many bits of space do you need? Give your answer without using

big$-$O notation, i$.$e$.,$ explicitly calculate the leading constant. Note: Do your computations

using the exactly optimal setting of $k,$ even if it is not an integer.

$(2$ points$)$ Compare the above bound to what you would get using the standard Bloom filter

analysis in class assuming a false positive rate of $(1-e^{\frac{-kn}{m}}{)}^k.$ Is the leading constant on the

space usage better or worse? Note: Be careful about the bases of your logarithms, as which

base you use will affect the leading constants.