rDBF: A r-Dimensional Bloom Filter for massive scale membership query

摘要

Bloom Filter is a data structure for membership filtering that is deployed in various domains to boost up the lookup performance and to lower the memory consumption. Bloom Filter has gained a massive popularity nowadays, and thus, it is deployed in diverse domains, namely, Big Data, Cloud Computing, Networking and Security, Bioinformatics, and IoT. Large scale computing uses a huge memory space, on the contrary, Bloom Filter uses a tiny amount of memory space. However, contemporary solution uses large amounts of memory per input item, and uses very complex arithmetic operations. Therefore, in this article, we propose a novel algorithm, called r-Dimensional Bloom Filter which comprises of Two Dimensional Bloom Filter (2DBF), Three Dimensional Bloom Filter (3DBF), Four Dimensional Bloom Filter (4DBF), and Five Dimensional Bloom Filter (5DBF), and it features a) a very fast filtering system, b) less false positive, c) low extra space consumption, d) free from false negative, e) high adaptability, and f) high scalability. Also, multidimensional Bloom Filter is not found in our literature search. But, many solutions claim the development of multidimensional Bloom Filter. However, these are hierarchical Bloom Filters. To evaluate our proposed data structure, we conduct has carried out an extensive experimentation. 2DBF, 3DBF, 4DBF, and 5DBF outperforms Cuckoo Filter in every aspect. We have experimented using Microsoft trace data and Twitter tweets data.