Uniformity and Independence of H3 Hash Functions for Bloom Filters

Date

2024-01-01

Author

Koltuk, Furkan
Schmidt, Şenan Ece

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

30
views

0
downloads

Cite This

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.

Subject Keywords

Bloom Filters, Computers, Filters, Hardware, Hash function uniformity and independence, Hash functions, Memory management, Testing, Universal hash functions, Vector subspaces in GF(2), Vectors

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85192764556&origin=inward
https://hdl.handle.net/11511/109604

Collections

Department of Electrical and Electronics Engineering, Article