bloom filter实现如何保持干净？

Question

既然它们被填满了，假阳性的百分比也增加了，那么有哪些技术可以防止它们饱和呢？似乎您不能清空位，因为这将立即对存储在该节点中的数据产生负面影响。

即使你有一个已知大小的集合，在使用像Cassandra这样的bloom过滤器的数据存储中，让我困惑的是节点中的数据将被添加和删除，对吧？但是当您删除一个键时，您不能将其bloom filter bucket设置为0，因为这可能会对散列到一个或多个与删除的键相同的bucket的节点中的数据产生漏报。所以随着时间的推移，就好像过滤器被填满了

Answer 1

我认为你需要对布隆过滤器覆盖的集合的大小设置一个上限。如果设置超过该大小，则需要重新计算布隆过滤器。

正如在cassandra中使用的那样，bloom过滤器覆盖的集合的大小在创建过滤器之前是已知的，因此这不是问题。

另一种方法是Scalable Bloom Filters

Answer 2

你应该意识到的第一件事是布隆过滤器只是累加性的。有一些近似删除的方法：

• 重写bloom filter
  • 您必须保留旧的data
  • 您需要支付性能费用

​

• 负面布隆过滤器
  • 比上面便宜得多，如果可以检测到bloom，还可以帮助处理误报

​

对布隆过滤器进行计数(递减count)

• Buckets

• 保持多个已分类的布隆过滤器，在不再需要某个类别时丢弃该类别(例如‘星期二’，‘星期三’，‘星期四’，...)

​

• Others?

如果您有时间限制的数据，使用存储桶并丢弃太旧的筛选器可能是有效的。