BLOOM-FILTER 的误报率

Time: 一月 31, 2012
Category: storage
目录索引

先来解决 false-positives 与 false-negatives 的定义

  • false-positives: 将不属于该集合中的元素错误地以为是该集合中的,为误报
  • false-negatives: 将属于该集合中的元素错误地以为不是该集合中的,此为漏报

Bloom-filter 的设计是,漏报不可能发生,误报允许存在,但是概率要控制在一定的范围内。Bloom-filter 的问题实质上是分析 false-positives 的问题

Bloom 是这样计算的:

经过 kn 次 hash 之后,集合 S 中任意一位为 0 的概率是,也可以说是集合中 0 的比率

(1 - \frac{1}{m})^{kn}


可能为 1 的概率是

p = 1 - (1 - \frac{1}{m})^{kn}

而产生误报的条件是,k 个 hash 的结果都为 1,所以 false-positives 的概率应该是,Bloom 说的

f = p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

我同样认为 Bloom 的论文中关于 false-positives 的估算是不算妥当,有兴趣的请移步:> ON THE FALSE-POSITIVE RATE OF BLOOM FILTERS 虽然这篇论文我只看了前部分,但是仍然觉得很有意思,Prosenjit Bose 等按照 Bloom 的方法讨论了一种较简单的情况,然后通过枚举计算出与实际误报率之间的偏差偏差。我的看法是,Bloom 的分析建立在非常理想的情况下,不足为奇
此外,我还另从两个角度去思考了一下 false-positives 的问题,仅作为讨论,请指正。

其一:

方便理解,因为 false-positives 是指将不属于这个集合的元素错误的以为是这个集合里的,这个概率用 e 来表示,那么 S 容量的上限为 (1 + e)*n
假设情况相当理想,种种随机。

于是有
经过 kn 次 hash 之后,集合 S 中任意一位可能为 1 的概率是

p = 1 - (1 - \frac{1}{m})^{kn}


所以,

f = p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

f 是指集合 S 中任意 k 位均为 1 的概率。这是产生一个 false-positive 的必要条件。那么实质上就是计算 S 的可能容量 g 的问题

g = (^{m}_{k}) * f \ge n


因为:

  1. 如果不存在 false-positives,那么 S 的可能容量 g 等于实际容量 n
  2. 如果存在 false-positives,那么 S 的可能容量 g 一定大于实际容量 n

所以 e 的值应该表示为

\frac{g- n}{n} = \frac{(^{m}_{k}) * f - n}{n} = \frac{(^{m}_{k}) * \left(1 - (1 - \frac{1}{m})^{kn}\right)^k - n}{n}

其二:

同理前面已论述,全部元素插入之后,任意 k 位均为 1 的概率是

p^k = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k

但是还不能说这就是 Bloom filter 的误报率,因为这里还包含着很小一部分正确的概率,只有发生错误时存在误报。如果一个元素确定存在,则对应的 k 位均为 1

(\frac{1}{m})^k


所以 false-positive rate 是理应是这样的:

f = \left(1 - (1 - \frac{1}{m})^{kn}\right)^k - n * (\frac{1}{m})^k

上式两边取对数并求 k 偏导可得

ln(f) = k * ln\left(1 - e^{\frac{-kn}{m}}\right) - ln\left(\frac{n}{m^k}\right)

\frac{1}{f}*f^' = ln(1 - e^\frac{-kn}{m}) - \frac{\frac{-kn}{m} * e^\frac{-kn}{m}}{1 - e^\frac{-kn}{m}} - ln(m)

然后令 -kn/m = x, ln(m) = y, 看其在二维坐标图上的分布,以寻求是否存在某种隐藏的关系

 y = ln(1 - e^x) - \frac{e^x*x}{1 - e^x}

Why ?

Leave a Comment