什么是 XOR 过滤器？

Question

有一个相对较新的数据结构 (2020) 称为 XOR filter，它被用作布隆过滤器的替代品。

什么是异或过滤器？它比布隆过滤器有什么优势？它是如何工作的？

Answer 1

XOR 过滤器被设计为在预先知道要存储在过滤器中的所有项目的情况下，直接替代 Bloom 过滤器。与 Bloom 过滤器一样，它表示不允许假阴性但允许假阳性的集合的近似值。

与布隆过滤器一样，XOR 过滤器存储大量位。但是，与我们将每个位视为其自己的数组槽的布隆过滤器不同，在 XOR 过滤器中，这些位被分组到 L 位序列中，对于我们稍后选择的某些参数 L。例如，异或过滤器可能如下所示：

 +-------+-------+-------+-------+-------+-------+-------+-------+-------+
 | 11011 | 10010 | 11101 | 11100 | 01001 | 10101 | 01011 | 11001 | 11011 |
 +-------+-------+-------+-------+-------+-------+-------+-------+-------+

接下来，我们选取三个哈希函数h₁,h₂，和 h₃，就像布隆过滤器一样，将项目散列到数组中的槽中。这些哈希函数让我们获取一个项目 x 并计算其 table 代码 ，我们通过将点 h₁(x), h₂(x) , 和 h₃(x)。此处显示了一个示例：

 +-------+-------+-------+-------+-------+-------+-------+-------+-------+
 | 11011 | 10010 | 11101 | 11100 | 01001 | 10101 | 01011 | 11001 | 11011 |
 +-------+-------+-------+-------+-------+-------+-------+-------+-------+
             ^                       ^       ^
             |                       |       |
            h3(x)                   h1(x)   h2(x)
              
            Table code for x:   10010 xor 01001 xor 10101
                              = 01110

为了完成这幅图，我们还需要一个哈希函数，称为 指纹函数，表示为 f(x)。指纹函数将一个值作为输入并输出一个 L 位数字，称为 x 的 fingerprint。要查看 x 是否存储在 table 中，我们检查 x 的 table 代码是否与 x 的指纹匹配。如果是这样，我们就说 x（可能）在 table 中。如果不是，我们说 x（肯定）不在 table.

中

将此想法与布隆过滤器进行比较会很有帮助。使用 Bloom 过滤器，我们将 x 散列到多个位置，然后通过对所有内容进行 AND 运算从这些位置得出一个值，最后检查我们得到的值是否等于 1。使用 XOR 过滤器，我们将 x 散列到三个位置，通过对它们进行异或运算从这些位置得出一个值，最后检查我们得到的值是否等于 f(x).

要更改 XOR 过滤器的误报率，我们只需更改 L 的值。具体来说，f(x) 巧合地匹配 XOR 的可能性h₁(x), h_{2[=给出的三个位置85=](x)，而 h₃(x) 是 2^-L，因为那是随机 L 位值与另一个匹配的概率。因此，为了得到 ε 的误报率，我们只需设置 L = log₂ ε^-1.}

具有挑战性的部分是填写table。事实证明，这样做有一个非常简单的策略。要存储 n 个元素的列表，请创建大小为 1.23n 的 table。然后，使用这个递归过程：

如果没有剩余物品可放置，您就完成了。
选择一个具有以下属性的项目 x：x 散列到没有其他项目散列到的 table 槽（例如，槽 k）。
从要放置的项目列表中删除 x 并递归放置剩余的项目。
将槽 k 的值设置为一个数字，使得 table 槽 x 哈希的 XOR 等于 f(x)。（这总是可能的：简单地将其他两个 table 槽和 f(x) 的内容异或在一起，然后将其存储在槽 k 中。）

如果每个 table 槽至少有两个项目散列到它，这个过程有一个小的机会卡在步骤 (2)，但它可以证明，只要你至少使用 1.23 ntable槽出现这种情况的概率极小。如果发生这种情况，只需选择新的哈希函数并重试。

异或过滤器与常规布隆过滤器相比有几个优点。

为了降低布隆过滤器的误报率，我们必须添加更多的功能。具体来说，对于 ε 的错误率，我们需要使用 log₂ ε^-1 哈希函数。另一方面，XOR 过滤器总是恰好使用三个哈希函数。
因此，Bloom 过滤器中的查找通常比 XOR 过滤器中的查找慢，因为每个 table 槽探测基本上是在一个随机位置，并且可能导致缓存未命中。使用 Bloom 过滤器，我们有 log₂ ε^-1 每个项目的缓存未命中。使用 XOR 过滤器，每个项目我们有三个缓存未命中。
Bloom 过滤器使用更多 space。错误率为 ε 的布隆过滤器需要大小为 1.44n log₂ ε^-1 的 table。 XOR 过滤器有一个包含 1.23n 个项目的数组，每个项目的长度为 log₂ ε^-1 位，总共 space 1.23n的用法 log₂ ε^-1.

XOR 过滤器相对于 Bloom 过滤器有一个主要缺点，那就是在构造过滤器之前必须事先知道要存储在 XOR 过滤器中的所有项目。这与布隆过滤器形成对比，布隆过滤器可以在很长一段时间内逐渐添加项目。不过，除此之外，异或过滤器提供了更好的性能和内存使用率。

有关 XOR 过滤器的更多信息，以及它们在时间方面的比较以及 space 与 Bloom 过滤器和布谷鸟过滤器的比较，请查看 this set of lecture slides，其中解释了它们的工作原理，以及1.23 常数从何而来以及为什么我们总是使用三个哈希函数。

什么是 XOR 过滤器？

What is an XOR filter?

xor

bloom-filter

data-structures