The Variable-Increment Counting Bloom Filter
The Variable-Increment Counting Bloom Filter
复制标题
DOI：
10.1109/infcom.2012.6195563
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
Ori Rottenstreich;Josef Kanizo;I. Keslassy
中科院分区：
文献类型：
--
作者：
Ori Rottenstreich;Josef Kanizo;I. Keslassy
计数布隆过滤器（CBF）广泛用于网络设备算法中。它们实现快速集合表示以支持错误有限的成员资格查询，并支持与Bloom Filters不同的元素删除。但是，它们会消耗大量的内存。在本文中，我们介绍了一种新的通用方法的基础上，可变增量，以提高CBF及其变种的效率。与CBF不同，在每次插入元素时，散列计数器都以散列变量增量而不是单位增量递增。然后，要查询一个元素，需要考虑计数器的确切值，而不仅仅是它的正性。我们提出了两个简单的方案，基于这种方法。在实际系统中，我们证明了这种方法总是可以获得比CBF更低的误报率和更低的溢出概率界。我们还展示了它如何可以很容易地实现在硬件中，有限的增加复杂性和内存开销。我们进一步解释了这种方法如何可以扩展许多变体的CBF已发表在文献中。最后，使用模拟，我们展示了它如何可以提高CBFs的误报率高达一个数量级给定相同的内存量。
Counting Bloom Filters (CBFs) are widely used in networking device algorithms. They implement fast set representations to support membership queries with limited error, and support element deletions unlike Bloom Filters. However, they consume significant amounts of memory. In this paper we introduce a new general method based on variable increments to improve the efficiency of CBFs and their variants. Unlike CBFs, at each element insertion, the hashed counters are incremented by a hashed variable increment instead of a unit increment. Then, to query an element, the exact value of a counter is considered and not just its positiveness. We present two simple schemes based on this method. We demonstrate that this method can always achieve a lower false positive rate and a lower overflow probability bound than CBF in practical systems. We also show how it can be easily implemented in hardware, with limited added complexity and memory overhead. We further explain how this method can extend many variants of CBF that have been published in the literature. Last, using simulations, we show how it can improve the false positive rate of CBFs by up to an order of magnitude given the same amount of memory.