hash - 差异布隆过滤器和 FM 草图

Question

布隆过滤器和散列草图（也是 FM 草图）有什么区别，它们的用途是什么？

Answer 1

哈希草图/Flajolet-Martin 草图

Flajolet, P./Martin, G. (1985)：用于数据库应用的概率计数算法，载于：计算机和系统科学杂志，卷。31，第 2 期（1985 年 9 月），第 182-209 页。

Durand, M./Flajolet, P. (2003)：大基数的对数对数计数，见：Springer LNCS 2832，算法 ESA 2003，第 605-617 页。

哈希草图用于计算集合中不同元素的数量。

给定：

• 长度为 l 的位数组 B[]
• 映射到 [0,1,...2^l) 的（单个）散列函数 h()
• 一个函数 r()，它给出其输入的二进制表示中最低有效 1 位的位置（例如 000101 返回 1，001000 返回 4）

插入元素 x：

• pn := h(x) 返回一个伪随机数
• 应用 r(pn) 将位数组的位置设置为 1，因为 h() 的输出是伪随机的，每个位 i 设置为 1 ~n/(2^(i+1)) 次

集合中不同元素的数量：

• 在位数组中找到最右边 0 的位置 p
• p = log2(n)，求解 n 得到集合中不同元素的数量；结果可能高达 1.83 级

用法：

• 在数据挖掘、P2P/分布式应用程序、文档频率估计等方面。

---

布隆过滤器

Bloom, H. (1970)：散列编码中允许错误的空间/时间权衡，载于：ACM 通信，卷。13，第 7 期（1970 年 7 月），第 422-426 页。

布隆过滤器用于测试元素是否是集合的成员。

给定：

• 长度为 m 的位数组 B[]
• k 个不同的哈希函数 h_k() 映射到 [0,...,m-1]，即映射到 m 位数组的位置之一

插入元素 x：

• 将 h_k 应用于 x (h_k(x))，对于所有 k，即你得到 k 个值
• 将数组 B 中的结果位设置为 1（如果已设置为 1，则不要更改任何内容）

检查 y 是否已经在集合中：

• 使用所有散列函数 h_k (h_k(y)) 获取要检查的位置 p_k，即对于每个函数 h_k，您都会得到一个位置 p_k
• 如果数组 B 中的位置 p_k 之一设置为 0，则元素 y 肯定不在集合中
• 如果 p_k 给出的所有位置都是 1，则元素 y 可能（！）在集合中
• 误报率约为 (1 - e^(-kn/m))^k，不可能出现误报！
• 通过增加散列函数的数量，可以降低误报率；但是，与此同时，您的布隆过滤器会变慢；k 的最优值为 k = (m/n)ln(2)

用法：

• 一开始用作数据库中的廉价过滤器，以过滤掉与查询不匹配的元素
• 当今的各种应用程序，例如在 Google BigTable 中，以及用于 IP 查找的网络等。

Answer 2

Bloom Filter 是一种用于成员查找的数据结构，而 FM Sketch 主要用于元素计数。这两种数据结构提供了各自的解决方案，优化了执行查找/计算所需的空间，权衡的是结果的准确性。