Uniformity and Independence of H3 Hash Functions for Bloom Filters

• Published in: IEEE transactions on computers 2024-08, Vol.73 (8), p.1913-1923
• Main Authors: Koltuk, Furkan, Schmidt, Ece Guran
• Format: Article
• Language: English
• Subjects: Bloom filters; Computers; Filters; Hardware; hash function uniformity and independence; Hash functions; Memory management; Testing; universal hash functions; vector subspaces in GF; Vectors
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2024.3398426

In this paper, we investigate the effects of violating the conditions of hash function uniformity and/or independence on the false positive probability of Bloom Filters (BF). To this end, we focus on hash functions of the H3 family with a partitioned memory organization for fast hardware implementations of BFs. We first introduce a dependence metric that quantifies hash function uniformity and independence. We then state and prove the necessary and sufficient conditions on the BF parameters for constructing uniform and independent hash functions. Finally, we derive an analytical expression for the exact false positive probability of a BF with hash functions that are not necessarily uniform or independent. We verify our expression with a hardware test bench and explore the effects of losing uniformity and independence through an experimental study that systematically sweeps different dependence metric values and numbers of hash functions. We demonstrate the effects of violating hash function uniformity and independence on the stated target false positive probability for selected previous works in the literature. As an important finding, we show that uniformity of individual hash functions is essential, whereas limited dependencies between hash functions can be tolerated without a negative effect on the false positive probability.