Counting Bloom Filter - Bloom Filter - CSDN博客

来源：百度文库 编辑：神马文学网 时间：2024/04/28 08:29:51
Counting Bloom Filter
焦萌 2007年1月30日 从前面几篇对Bloom Filter的介绍可以看出，标准的Bloom Filter是一种很简单的数据结构，它只支持插入和查找两种操作。在所要表达的集合是静态集合的时候，标准Bloom Filter可以很好地工作，但是如果要表达的集合经常变动，标准Bloom Filter的弊端就显现出来了，因为它不支持删除操作。 Counting Bloom Filter的出现解决了这个问题，它将标准Bloom Filter位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。下一个问题自然就是，到底要多占用几倍呢？   我们先计算第i个Counter被增加j次的概率，其中n为集合元素个数，k为哈希函数个数，m为Counter个数（对应着原来位数组的大小）： 
上面等式右端的表达式中，前一部分表示从nk次哈希中选择j次，中间部分表示j次哈希都选中了第i个Counter，后一部分表示其它nk – j次哈希都没有选中第i个Counter。因此，第i个Counter的值大于j的概率可以限定为： 
上式第二步缩放中应用了估计阶乘的斯特林公式： 
在Bloom Filter概念和原理一文中，我们提到过k的最优值为(ln2)m/n，现在我们限制k ≤ (ln2)m/n，就可以得到如下结论： 
如果每个Counter分配4位，那么当Counter的值达到16时就会溢出。这个概率为： 
这个值足够小，因此对于大多数应用程序来说，4位就足够了。   关于Counting Bloom Filter最早的论文：Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/jiaomeng/archive/2007/01/30/1498283.aspx
Counting Bloom Filter - Bloom Filter - CSDN博客 Bloom Filter概念和原理 - Bloom Filter - CSDN博客 Compressed Bloom Filter - Bloom Filter - CSDN... bloom filter bloom filter bloom filter Bloom Filter概念和原理 布隆过滤器（Bloom Filter） Bloom Filter概念和原理 - medie2005的专栏 - CSDNBlog 二十一 － 布隆过滤器（Bloom Filter） Air filter 瑞恩·法瑞什《Bloom绽放》 Filter Servlet实例应用 深入浅出DirectShow Filter 深入浅出DirectShow- Filter 创建filter笔记1 logback-Filter机制 educational-origami - Bloom's Digital Taxonom... Bloom 认知领域分类法与深度学习 开发Filter的一般过程以及Filter Graph的构建 深入浅出DirectShow Filter（一） 深入浅出DirectShow Filter（二） Kalman filter toolbox for Matlab Inside the Linux Packet Filter