Low Computational Cost Bloom Filters

Bloom filters (BFs) are widely used in many network applications but the high computational cost limits the system performance. In this paper, we introduce a low computational cost Bloom filter named One-Hashing Bloom filter (OHBF) to solve the problem. The OHBF requires only one base hash function plus a few simple modulo operations to implement a Bloom filter. While keeping nearly the same theoretical false positive ratio as a Standard Bloom filter (SBF), the OHBF significantly reduces the computational overhead of the hash functions. We show that the practical false positive ratio of an SBF implementation strongly relies on the selection of hash functions, even if these hash functions are considered good. In contrast, the practical false positive ratio of an OHBF implementation is consistently close to its theoretical bound. The stable false positive performance of the OHBF can be precisely derived from a proved mathematical foundation. As the OHBF has reduced computational overhead, it is ideal for high throughput and low-latency applications. We use a case study to show the advantages of the OHBF. In a BF-based FIB lookup system, the lookup throughput of OHBF-based solution can achieve twice as fast as the SBF-based solution.