Bloom Filter is an important probabilistic data structure to reduce memory consumption for membership filters. It is applied in diverse domains such as Computer Networking, Network Security and Privacy, IoT, Edge Computing, Cloud Computing, Big Data, and Biometrics. But Bloom Filter has an issue of the false positive probability. To address this issue, we propose a novel robust Bloom Filter, robustBF for short. robustBF is a 2D Bloom Filter, capable of filtering millions of data with high accuracy without compromising the performance. Our proposed system is presented in two-fold. Firstly, we modify the murmur hash function, and test all modified hash functions for improvements and select the best-modified hash function experimentally. Secondly, we embed the modified hash functions in 2D Bloom Filter. Our experimental results show that robustBF is better than standard Bloom Filter and counting Bloom Filter in every aspect. robustBF exhibits nearly zero false positive probability with more than $10\times$ and $44\times$ lower memory consumption than standard Bloom filter and counting Bloom Filter, respectively.
翻译:Bloom 过滤器是一个重要的概率数据结构, 用于减少会员过滤器的记忆消耗。 它应用于计算机网络、 网络安全和隐私、 IoT、 边缘计算、 云计算、 大数据、 和生物量学等不同领域。 但是 Bloom 过滤器有一个错误的正概率问题。 为了解决这个问题, 我们提议了一个新的强大的 Bloom 过滤器, 强大的Broom 过滤器是 2D Bloom 过滤器, 能够以高精确度过滤数百万数据, 而不会影响性能。 我们提议的系统是用两部分来显示的。 首先, 我们修改 murmur hash 功能, 测试所有修改后的 hus 函数, 并实验选择最优化的 hash 。 其次, 我们将修改后的 hash 函数嵌入 2D Bloom 过滤器。 我们的实验结果显示, 强大的 Broom 过滤器比标准的 Bloom 过滤器和计时都要好。 强的概率几乎为零, 比标准的 Bloom 10\ times 和 44\ times 低的记忆消耗率 。