bloom filter 备忘(2)

Bloom 过滤器(以下称 Bloom Filter 或 BF) 采用位数组表示数据集合并有效支持集合元素的成员查询，由于其能显著节省存储空间，在对错误率不敏感的领域(如字典查询、数据库)，Bloom Filter 有着广泛的应用。
随着网络及数据流处理技术的飞速发展使 Bloom Filter 焕发了新的活力，数据流等新应用场景也推动了 Bloom Filter 理论的发展，产生了计数型 Bloom 过滤器(Counting Bloom Filter, CBF) 、光谱 Bloom 过 滤 器 (Spectral Bloom Filter, SBF)和动态计数过滤器(Dynamic Counting Filter, DCF)等多种 Bloom Filter。

标准 Bloom Filter：
已经示例了一个 bloom filter 的 Toy Demo 实现. 并简要介绍了 bf 的基本原理.
参考文档：Bloom Filter概念和原理
数 学之美系列 － 布隆过滤器

标准 Bloom Filter 不支持从集合中删除元素，如果删除元素时把相应的位置为 0，而别的元素也哈希到这一位，那么 Bloom Filter 就不再正确地反映集合中的所有元素，而产生假阴性。同时也不能完成计数等功能，于是一些变种出现了。

计数型 Bloom Filter (CBF)
Counting Bloom Filter的出现解决了这个问题，它将标准Bloom Filter位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。
基本结构：

参考文档：Counting Bloom Filter

光谱Bloom过滤器(SBF)
标准 Bloom Filter 和 CBF 解决了元素与集合的成员查询问题。在最近涌现的数据流应用中，用户不仅关注元素的成员归属，而且关注多个元素出现的频数。SBF扩展了CBF，利用 CBF的计数器支持计数查询。
基本结构：

参考文档：Counting Bloom Filter

动态计数过滤器(DBF)
SBF解决了由于计数器大小变动带来的动态存储问题，但是引入了复杂的索引结构，每个计数器的访问变得复杂而耗时，元素频数出现剧烈变化时的索引重建也十分耗时。于是 DCF 出现了，DCF支持元素出现频数查询，结构又相对简单。
基本结构：

参考文档：Dynamic Count Filter

计数型 Bloom Filter 的简单比较

	计数器大小	内存占用	访问速度	重建率	计数器溢出
CBF	固定	少	快	无	会
SBF	动态	较多	慢	高	最终会
DCF	动态	较多	快	低	不会

可以看出，CBF虽然内存占用少、访问速度快、无重建操作，但是存在无法解决的计数器溢出问题。SBF与DCF相比，在内存占用方面，由于DCF中计数器的最大值决定了整个DCF所占的空间，因此在元素分布比较均匀、增删
操作相对平均的情况下，计数器的值相差不大，而且DCF不用维护复杂的索引结构，占用空间比SBF少。如果少数计数器的值显著大于其他计数器，SBF在空间使用方面会占据优势；在计数器的存取时间方面，DCF占有绝对的优势，它仅比标准CBF多了一次内存访问，而SBF的访问相对复杂；在处理数据抖动方面，SBF和DCF都不够理想，前者需要数据访问索引的重建，后者可能面临开销巨大的OFV数组重建工作。如何设计和维护计数器的结构也是CBF一个重要的研究方向。