Optimization,then Compression Optimize to minimize false positive. p=Pr[cell is empty ]=(1-1/m)kn e-knim f=Pr[false pos]=(1-p)(1-e-kon/m)k k=(mln 2)/n is optimal At k=m (In 2)/n,p=1/2. Bloom filter looks like a random string. Can't compress it. 1919 Optimization, then Compression  Optimize to minimize false positive.  At k = m (ln 2) /n, p = 1/2.  Bloom filter looks like a random string.  Can’t compress it. kn kn m p m e / Pr[cell is empty ] ( 1 1 / )      k kn m k f Pr[false pos ] ( 1 p ) ( 1 e )  /      k  ( mln 2 ) / n is optimal