布卢姆是否过滤掉交叉路口/工会的误报率?

问题描述 投票:0回答:1

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

问题集:

一切都属于采用布隆过滤器的隆起采矿。

我有成千上万的布隆过滤器,有一些最大容量M,每个过滤器N中的项目数量。

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

假阳性的可能性P - 0.001%

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

喜欢A∩B∩C∩D...

这种操作将针对不同长度的不同组合组合的任意大数(或小,取决于我的成本函数)执行

A∩B; ∩J∩K; ∩W∩...∩Z;等等

所有收到的(新的)交叉点作为bloomfilters(BF∩i),将通过联合操作组合,

BF1在BF2 U ...在BFi


问题:

布隆过滤器上的这种操作是否会影响最终的组合布隆过滤器(多个交叉点的并集)的误报率,因为我可能有很多这样的操作?

如何估计我的案例可能的准确性/精确度损失(或者说误报率增加)?

非常感谢相关材料的任何暗示或指示!

data-structures bigdata probability data-science bloom-filter
1个回答
2
投票

下面的讨论假定所有使用相同参数(容量和散列)的Bloom过滤器都是使用相同的参数创建的。如果情况并非如此,那么你的问题就更难回答了。

两个布隆过滤器A和B的交集将导致布隆过滤器,该过滤器最多将具有两者中较小的条目数。也就是说,如果A的条目数少于B,则A∩B的结果不能包含比A包含的项目更多的项目。假设生成的布隆过滤器使用与A相同的参数(即容量和散列)构造,则结果中的误报率不能高于A或B中的误报率,因为结果不能包含比他们俩。

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

重要的是要了解当您构造Bloom过滤器以容纳给定数量的项目时,目标误报率是指您将这么多项目添加到Bloom过滤器时。例如,如果您创建Bloom过滤器以保存FPF为0.0001的1,000,000个项目,那么在您向Bloom过滤器添加1,000,000个项目后,您可以预期误差率为10,000(10,000)。但是,如果您只向Bloom过滤器添加100,000个项目,则实际误报率将会低得多。

只要您不超过Bloom过滤器的设计容量,误报率就不会超过设计值。

© www.soinside.com 2019 - 2024. All rights reserved.