The Power of 1 + α for Memory-Efficient Bloom Filters

Abstract

This paper presents a cache-aware Bloom-filter algorithm with improved cache behavior and lower false-positive rates compared to prior work. The algorithm relies on the power-of-two choice principle to provide a better distribution of set elements in a blocked Bloom filter. Instead of choosing a single block, we insert new elements into the less-loaded of two blocks to achieve a low false-positive rate while performing only two memory accesses on each insert or query operation. The paper also discusses an optimization technique to balance cache effectiveness with the false-positive rate to fine-tune the Bloom-filter properties.

Acknowledgments

The authors would like to thank the anonymous reviewers, whose comments helped us to improve the paper significantly. We would also like to thank Isaac Keslassy for fruitful discussions at the early stages of this research and Mehmet Basoglu for his help with preparing this manuscript for publication. Finally, we thank Intel corporation for providing equipment and funds in support of this research.