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，Algorithms 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):哈希编码中的空间/时间权衡与允许的错误，见:Communications of the ACM，Vol.1。 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 查找网络等中。