布隆过滤器在处理动态集时可能出现的问题

Question

我在理解动态集布隆过滤器可能存在的问题时遇到了麻烦。

你能告诉我在set中添加/删除元素时可能会出现的一些问题吗？

Answer 1

主要的问题是bloom过滤器不是为删除而设计的。

例如。假设

h1(x) = x %5
h2(x) = (x+2) % 5

假设您在集合中有两个元素：2,4。

你已经有了位集：

bitset = { 0, 1, 1, 0, 1 }

现在，您想要从集合中删除2。你是怎么做到的？您不知道bitset4对这两个元素都是通用的，一旦删除它，就会得到新的位集：

bitset' = { 0, 0, 1, 0, 0 } 

但是现在，如果您尝试检查4是否在其中，您将得到一个错误的答案。

允许删除布隆过滤器的一种可能的解决方案是counting bloom filters，但它也有其缺点。

另一个问题是，如果你的集合是动态的，并且可以保持增长，那么增加它的大小并不是一件微不足道的事情。您不能简单地分配双倍的空间，并重新散列整个集合，您根本不知道原始元素是什么。

因此，当布隆过滤器的大小是先验的(或有界的)时，就使用布隆过滤器。