如何计算布卢姆过滤器百分比

cwtwac6a  于 2021-05-30  发布在  Hadoop
关注(0)|答案(1)|浏览(482)

我正在使用hadoop,并在 Bloom Filter ,上面写着:
假阳性率用公式近似

(1 – exp(-kn/m))k

其中k是所使用的散列函数的数量,m是用于存储bloom过滤器的位数,n是要添加到bloom过滤器的元素的数量。在实践中,m和n是由系统的要求决定的,因此,选择k来最小化给定m和n的假阳性率,这(经过一点计算)是

k = ln(2) * (m/n) ≈ 0.7 * (m/n)

给定k时的假阳性率为0.6185m/n,k必须是整数。假阳性率只是一个近似值。从设计的Angular 来看,人们应该考虑(m/n),每个元素的位数,而不是仅仅考虑m。例如,我们必须存储一个包含一千万个URL(n=10000000)的集合。分配­ 为每个url设置8位(m/n=8)将需要一个10 mb的bloom筛选器(m=80000000位)。此布卢姆过滤器的假阳性率为(0.6185)8,约为2%。如果我们要通过存储原始url来实现set类,并且假设url的平均长度是100字节,那么我们必须使用1gb。bloom filter将存储需求缩减了2个数量级,但仅以2%的误报率为代价!稍微增加分配给bloom过滤器的存储量将减少错误的posi­ 进一步提高利率。在每个url 10位的情况下,bloom过滤器将占用12.5 mb,误报率仅为0.8%。
所以这里说假阳性率是0.6185*8,也就是4.948,但是文件怎么说大约是2%?有人能帮我计算一下百分比吗?
根据大卫的回答详细解释:
根据书中的解释:

n = 10,000,000 = 1e7

m/n = 8 which means m = 8*n

k = ln(2) * (m/n), Value of ln(2) is 0.693 = 0.7, so value of k = 0.7 * (m/n)

现在我的表情是:

(1 – exp^(-kn/m))^k = (1 - exp^(-0.7))^(0.7*8) = (1 - 0.4965)^(5.6) = (0.5034)^(5.6) = 0.0214 (Here ^ represents power)

为了计算百分比,我们必须乘以100。
所以百分比是 0.0214*100 = 2%

carvr3hs

carvr3hs1#

正确的公式是

k
(1 – exp(-kn/m)) ,

将带圆括号的表达式取k的幂,而不是乘以k。近似方法主要是假设bloom滤波器的每个单元的值是独立的(写入exp时有一点误差,而不是真正的单单元概率);假阳性率是k细胞全部被标记的概率。
下面是如何计算给定示例的假阳性概率。

>>> from math import *
>>> n = 1e7
>>> m = 8*n
>>> k = log(2) * (m/n)
>>> (1 - exp(-k*n/m))**k
0.021415847120683718

要将概率转换成一个百分比,乘以100。

>>> 100*_
2.1415847120683718

相关问题