Ns3 Projects for B.E/B.Tech M.E/M.Tech PhD Scholars.  Phone-Number:9790238391   E-mail: ns3simulation@gmail.com

A Comment on “Fast Bloom Filters and Their Generalization”

A Bloom filter is a data structure that provides probabilistic membership checking. Bloom filters have many applications in computing and communications systems. The performance of a Bloom filter is measured by false positive rate, memory size requirement, and query (or memory look-up) overhead. A recent paper by Qiao et al. proposes the Fast Bloom Filter, also called Bloom-1, which requires only a single memory look-up for a membership test.

Bloom-1 achieves a reduced query overhead at the expense of a slightly higher false positive rate for a given memory size. The false positive rate of Bloom-1 has been analyzed theoretically by Qiao et al. relying on a well-known, but flawed, approximation for the false positive rate for a Bloom filter. In this comment paper we show that the Qiao et al. analysis of Bloom-1 under-estimates the false positive rate for low loads. We provide a correct analysis of Bloom-1 yielding an expression for the exact false positive rate.