HFil: A High Accuracy Bloom Filter
Ripon Patgiri · 2019
Bloom Filter is a data structure for membership filter that deployed in diverse domains. Bloom Filter is able to reduce on-chip memory consumption on an order of magnitude. Therefore, Bloom Filter has been deployed in Big Data, Networking, Bioinformatics, Cloud Computing and IoT. However, there is a critical issue in Bloom Filter, called false positive which reduces accuracy of Bloom Filter. Therefore, in this paper, we present a novel technique, called HFil (High accuracy Filter) to reduce false positive and achieve high accuracy. HFil deploys several 3D Bloom Filters (3DBF) to achieve high accuracy and low false positive. HFil is a multilevel Bloom Filter by deploying multidimensional Bloom Filter. HFil derives nL HFil where n=1,2,3,4, ... In our experiment, we show the performance, accuracy, and false positive of 4L HFil, 6L HFil, 8L HFil, 12L HFil, 14L HFil, and 16L HFil. The 4L HFil outperforms all other variants of HFil in terms of performance. On the contrary, 16L HFil has higher accuracy than its lower level HFil. Moreover, 16L HFil has the highest accuracy of 99.99% while the 4L HFil has the lowest accuracy of 98.77%. The asymptotic behavior of the 4L HFil, 6L HFil, 8L HFil, 10L HFil, 12L HFil, 14L HFil and 16L HFil have same which is O(1) for insertion and lookup operation.