异或过滤器

https://doi.org/10.48550/arXiv.1912.08258

布隆过滤器提供了快速的近似集合成员性能，并且占用很少的内存。 工程师们经常使用这些过滤器来避免诸如磁盘或网络访问等慢速操作。 作为一种替代方案，Cuckoo过滤器可能需要比布隆过滤器更少的空间，并且速度更快。 Chazelle等人提出了布隆过滤器的一种推广形式，称为Bloomier过滤器。 Dietzfelbinger和Pagh描述了布鲁米尔过滤器的一个变体，可以有效地用于近似成员查询。 据我们（原论文作者，下同）所知，它从未经过实证测试。我们回顾了他们方法的一个高效实现，我们称之为异或过滤器。 我们发现，异或过滤器可以比布隆过滤器和Cuckoo过滤器更快地使用更少的内存。 我们进一步表明，异或过滤器的更紧凑版本（异或+）可以使用比高度紧凑的替代方案（例如Golomb压缩序列）更少的空间，同时提供与布隆过滤器相竞争的速度。

一种用于近似成员的经典数据结构是布隆过滤器[4]。它可能是最知名的概率性数据结构之一。布隆过滤器类似于集合数据结构，我们可以添加键，并检查给定的键是否存在于集合中。存在一小概率出现将一个键错误地报告为存在的情况，我们称之为误报。然而，布隆过滤器可以使用比原始集合更少的内存。因此，布隆过滤器在减少内存使用的同时接受了一小概率的错误。

近似集合成员具有许多应用，例如使用负载签名扫描病毒[18]，过滤不良关键词或地址，以及对字符串进行快速语言识别[22]。写优化的键值存储[11]，例如日志结构化合并（LSM）树[29]，是另一个重要的用例。在这种存储中，内存中的数据结构避免了昂贵的磁盘访问。我们希望我们的数据结构既快速又使用少量的内存。在这方面，传统的布隆过滤器可能会被超越：

• 布隆过滤器会生成许多随机访问查询。为了实现高效的内存使用，具有误报概率 ϵ 的布隆过滤器应该使用约 -log2 ϵ 个散列函数[10]。在误报概率为1%的情况下，因此需要使用七个散列函数。即使散列函数的计算是免费的，进行多次随机内存访问可能是昂贵的。

• 具有误报概率 ϵ 的近似成员数据结构的理论下界是 -log2 ϵ 位每个键[10]。在最优方式下应用时，布隆过滤器使用的内存比理论下界多出44%。实际上，布隆过滤器通常比诸如 cuckoo 过滤器[20] 等其他选择更慢且更大。我们能比 cuckoo 过滤器做得更好吗？

Bonomi等人[5]以及Broder和Mitzenmacher [10]指出，对于静态集合，使用完美哈希函数和指纹可以实现基本上最优的内存使用。他们部分地对这种可能性不予考虑，因为计算完美哈希函数可能太昂贵。然而，Dietzfelbinger和Pagh [17]描述了一个看似实用的这一想法的实现，我们称之为异或过滤器。它基于与布鲁米尔过滤器[12, 13]

据我们所知，异或过滤器从未被实现和进行基准测试。我们进行了第一次实验评估。我们发现它们表现良好，通常比布隆过滤器和 cuckoo 过滤器更快。对于常见的使用情况，它们需要更少的内存。此外，我们可以通过一种相对简单的压缩技术（见第3.3节）在只有适度性能损失的情况下改进它们的内存使用。为确保可重现性，我们免费提供我们的软件。我们的主要结果是异或过滤器作为一种实用的数据结构具有优点。它们快速、紧凑，并且我们发现它们易于实现。

我们发现在数据库系统中有许多布隆过滤器和相关数据结构[11]，以避免磁盘访问。用于设计必须支持频繁更新的数据库引擎的一种常见策略是日志结构化合并（LSM）树[29]。在高层次上，LSM树维护一个快速的内存组件，批量地将其合并到持久存储的数据中。内存组件累积数据库更新，从而将更新成本分摊到持久存储中。为了加速查找，许多LSM树的实现（例如levelDB、RocksDB、WiredTiger）使用布隆过滤器。在合并组件时，通常会构建一个新的过滤器。相反，我们可以更新现有的过滤器。然而，支持快速合并的数据结构（例如布隆过滤器）要么需要原始过滤器具有额外的容量，要么需要合并结果具有更高的误报概率[2]。

布隆过滤器和相关数据结构的许多应用都存在于网络领域，我们希望避免不必要的网络访问。通常情况下，当一个过滤器必须通过网络连接发送到其他计算机（例如用于缓存和防止网络查询）时，我们可以将过滤器视为在接收机上是不可变的[27]。

布隆过滤器的变种

标准布隆过滤器[4]由一组哈希函数 h1、h2、...、hk 和一个初始化为零的位数组 B 组成，其中每个可能的键被映射到一个固定的整数，我们将其解释为索引值。数组的大小和哈希函数的数量 k 是过滤器的参数。当我们添加一个键 x 时，我们使用每个哈希函数对其进行哈希，并设置相应的位：

$B[h_1(x)]\to 1,$ $B[h_2(x)]\to 1,$ $⋮$ $B\left[h_3(x)\right]\to 1,$

为了判定给出的值是否存在，我们检查数组中对应位是否被设置：
$(B[h_1(x)]=1)and(B[h_2(x)=1])and\cdots and(B[h_k(x)]=1).$

因此，如果有 k 个哈希函数，我们可能需要检查多达 k 个位。对于已添加的键，我们保证所有位都被设置：不会发生误报。但如果这些位是由其他键设置的，就可能发生误报。标准布隆过滤器不允许我们删除键。无论位数组的大小和哈希函数的数量如何，布隆过滤器都支持添加键，但随着添加更多条目和设置更多位，误报概率会增加。通常选择数组 B 的大小，以便在最大条目数的情况下能够保证一定的误报概率，并计算最佳参数 k。最佳布隆过滤器的预期空间开销为 44%：需要设置 k = -log2 ϵ，其中 ϵ 是期望的误报概率上限。布隆过滤器可以并发地使用[39]。Blocked 布隆过滤器[24, 35]由许多小的布隆过滤器组成，可能每个 CPU 缓存行一个，这样每个操作只需进行一次内存访问。然而，这些小过滤器的负载可能不均匀，因此在相同的误报概率下，它们通常需要比标准布隆过滤器多约30%的空间。先进的 CPU 指令可以加速正常布隆过滤器和 Blocked 布隆过滤器的成员测试[32]。布隆过滤器还有许多其他变种，包括计数布隆过滤器[5, 36]（以更多的存储空间为代价支持删除键），压缩布隆过滤器[27]，多维布隆过滤器[14]，稳定布隆过滤器[15]等等。

基于指纹的变种

to be continue