A*******e
发帖数: 2419 | 1 吴军的讲解：
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和
一系列随机映射函数。我们通过上面的例子来说明起工作原理。
假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字
节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们
用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8
）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数
g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个
email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。
现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单
中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指
纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,
t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这
样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。
问题：
1. 一亿个邮件地址，为何要十六亿的位图？
2. 这八个随机数生成器指的是散列函数？如何保证这些函数相互独立？比如一个随机
数生成器可以加参数，当八个用。但这八个结果显然是相关的。 | s******c
发帖数: 1920 | 2 1. 一亿个邮件地址，为何要十六亿的位图？
八个hash function，每一个元素（这里就是一个单独的邮件地址）分配到16个bit, 这
样保证false positive rate < 0.0574%
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
2. 这八个随机数生成器指的是散列函数？如何保证这些函数相互独立？比如一个随机
数生成器可以加参数，当八个用。但这八个结果显然是相关的
使用一个随机数生成器加param生成的8个随机数都是相关的。
但是Mitzenmarcher的论文显示， 在Bloom filter的case里， 2个随机数就足够模拟出
其他N个随机数了
f8
【在 A*******e 的大作中提到】
: 吴军的讲解：
: 布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和
: 一系列随机映射函数。我们通过上面的例子来说明起工作原理。
: 假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字
: 节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们
: 用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8
: ）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数
: g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个
: email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。
: 现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单
| j**********3
发帖数: 3211 | |
|
