用来确定一个家族中的哪些集是给定集的子集的Bloom过滤器

Question

我试图使用一个Bloom过滤器来确定来自一个集合( A1、A2、.、Am )的哪些集合是另一个固定集Q的子集。我希望有人能验证所述方法的正确性或提供任何改进。

设Q是一组给定的整数，包含来自宇宙集合U = {1,2,...,10000}的1-10000个元素。

另外，假设有一个集合( A1，A2，.，Am )，每个集合包含来自同一个宇宙集合U的1-3个元素。m的尺寸是5000左右。

算法概要：

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

另外，对于每个Ai，i = 1,...,m集，将哈希函数应用到Ai的每个元素，生成位集(也是大小n)，表示Ai_b。

要检查Ai是否是Q的子集，请在两个位集Q_b & Ai_b上执行逻辑操作，并检查它是否等于位集Ai_b。也就是说，如果Q_b & Ai_b == Ai_b是假的，那么我们就知道Ai不是Q的子集；如果它是真的，那么我们不确定(可能出现假阳性)，我们需要使用确定性的方法检查给定的Ai。

希望过滤器能告诉我们Ai的大部分不在Q中，我们可以更仔细地检查那些返回真的。

，这是解决我问题的好方法吗？

(附带问题：n应该有多大？有哪些好的哈希函数可以使用？)

Answer 1

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

1. 让我们创建一个数组was (索引从1到10000，即通用集合的每个元素只有一个单元格)，最初填充的是false值。
2. 对于每个元素q of Q，我们设置了was[q] = true。
3. 现在我们遍历了这个家族的所有集合。对于每个集合A_i，我们迭代集合的所有元素x，并检查was[x]是否为真。如果不是针对至少一个x，那么A_i就不是Q的子集。否则，它就是。

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

Answer 2

请试着在你的问题中只问一个问题。

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

这可能不是一个好办法。

首先，Q很小；来自{1,...,10k}的10,000个元素意味着Q可以以10k位或大约1.2个基字节的位集存储。非常非常小。例如，它比您的问题要小，它使用了几乎1.5个基字节。

第二，Ai包含一到三个元素，所以Ai_b很可能比Ai大，除非您选择它们太小以至于假阳性率很高。

最后，哈希函数的计算是不自由的。

如果您检查每个Ai的每个元素和一个表示Q的位集，您可以做得更简单。