用于确定家族中的哪些集合是给定集合的子集的Bloom过滤器

Question

我正在尝试使用Bloom过滤器来确定集合家族中的哪些集合A1,A2，...，Am是另一个固定集合的子集Q。我希望有人能够验证所述方法的正确性或提供任何改进。

让Q为给定的整数集合，其中包含来自宇宙集合中的1-10000个元素的任何地方集合U = {1,2,...,10000}。

此外，让有套A1，A2，一个家庭...，Am每个从相同宇宙1-3元件的任何位置含有设置U。大小m是5000

轮廓算法的顺序：

要有的k哈希函数的集合。对于Q的每个元素，应用散列函数并将其添加到大小为n的位集，表示为Q_b。

此外，对于每个Ai，i = 1,...,m套，应用散列函数到的Ai每个元素，生成位集（也的大小n），表示为Ai_b。

要检查是否Ai是Q的子集，执行逻辑与上两个bitset，Q_b & Ai_b，并检查是否是等于位集Ai_b。也就是说，如果Q_b & Ai_b == Ai_b为假，那么我们知道Ai不是Q的子集;如果它是真的，那么我们不知道（误报的可能性），我们需要使用确定性方法检查给定的Ai。

希望是过滤器告诉我们大多数Ai的不在Q中，我们可以更仔细地检查那些返回true的东西。

这是一个很好的方法来解决我的问题吗？

（边问题：？n应该有多大有什么好的哈希函数使用？）

Answer 1

如果值的范围很小（如您的示例中所示），则可以使用具有线性时间复杂度的简单确定性解决方案。

1. 让我们创建一个数组was（具有从1至10000的索引，即，用于通用集合的每个元素的一个单元）时，最初充满false值。

2. 对于每个q的Q，我们设置was[q] = true。

3. 现在我们遍历所有家族的集合。对于每个集合A_i，我们迭代该集合的所有元素x，并检查was[x]是否为真。如果它不是至少有一个x，那么A_i不是Q的子集。否则，它是。

该解决方案显然是正确的，因为它根据定义检查一个集合是否是另一个集合的子集。这也相当简单和确定性。它唯一潜在的缺点是它需要一个10000个元素的辅助数组，但它在大多数实际应用中看起来是可以接受的（无论如何，布隆过滤器也需要一些额外的空间）。

Answer 2

请试着问只有一个问题你的问题。

我会解决第一个问题：“这对我的问题是一个好方法吗？”，但不是最后两个，“应该多大？有什么好的散列函数可用？”

这可能不是一个好方法。

首先，Q很小;来自{1,...,10k}的10,000个元素意味着Q可以以10k位或约1.2千比特的位集存储。这是非常非常小的。例如，它比你的问题更小，它使用了近1.5千字节。

其次，Ai包含一到三个元素，因此Ai_b可能会大于Ai，除非您选择它们​​太小以至于误报率非常高。

最后，散列函数计算不是免费的。

如果您针对代表Q的位集检查每个Ai的每个元素，则可以更简单地执行此操作。