布隆过滤器在交叉点/联合上的误报率会增加吗？

Question

没有找到任何关于此的内容，所以我希望我的问题能在这里找到答案。

问题集：

一切都属于使用布隆过滤器的提升挖掘。

我有数千个布隆过滤器，最大容量为 M，每个过滤器中的项目数为 N。

对于N在任何情况下都不会到达 M的情况。

误报概率 P - 0.001%

在我的问题中，我需要从几个到 ±5 个增量交叉点逐步执行，

像A？乙？C ？迪...

将针对不同长度的不同集合组合的任意大数量（或小数量，取决于我的成本函数）执行此类操作

一种 ？乙; 一种 ？? K; ? ? ……？Z; 等等。

所有接收到的（新的）交集作为布隆过滤器（BF?i），将通过联合操作进行组合，

BF1 U BF2 U ... U BFi

---

问题：

布隆过滤器上的此类操作是否会影响最终组合布隆过滤器（多个交叉点的并集）的误报率，因为我可能有很多这样的操作？

我如何估计我的案例可能的准确度/精确度损失（或者误报率增加）？

将非常感谢对相关材料的任何提示或指导！

Answer 1

下面的讨论假设所有有问题的布隆过滤器都是使用相同的参数（容量和哈希）创建的。如果不是这样，那么你的问题就更难回答了。

两个布隆过滤器A和B的交集将产生一个布隆过滤器，该过滤器最多具有两者中较小者的条目数。也就是说，如果A的条目少于B，那么A的结果？B包含的项目不能多于A包含的项目。假设生成的布隆过滤器是用与A相同的参数（即容量和哈希）构造的，那么结果中的误报率不能比A或B 中的高，因为结果不能包含比较小的项更多的项目他们俩。

两个 Bloom 过滤器的并集（再次假设所有过滤器都是使用相同参数创建的）将始终具有至少与具有最高误报率的 Bloom 过滤器一样高的误报率。也就是说，如果B的 FP 率高于A 的，那么AUB的 FP 率将始终大于或等于B的 FP 率。原因是生成的布隆过滤器将始终具有至少与两者中较大者一样多的项目。

重要的是要了解，当您构建一个 Bloom 过滤器来保存给定数量的项目时，目标误报率是针对您将那么多项目添加到 Bloom 过滤器时的。例如，如果您创建一个 Bloom 过滤器以容纳 1,000,000 个项目，FP 率为 0.0001，那么在您将 1,000,000 个项目添加到 Bloom 过滤器后，您可以预期误报率为万分之一。但是如果你只向 Bloom filter 添加 100,000 个项目，实际的误报率会低很多。

只要不超过布隆过滤器的设计容量，误报率就不会超过设计值。