我正在使用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%
1条答案
按热度按时间carvr3hs1#
正确的公式是
将带圆括号的表达式取k的幂,而不是乘以k。近似方法主要是假设bloom滤波器的每个单元的值是独立的(写入exp时有一点误差,而不是真正的单单元概率);假阳性率是k细胞全部被标记的概率。
下面是如何计算给定示例的假阳性概率。
要将概率转换成一个百分比,乘以100。