阻塞布隆过滤器

  • 我们首先选择一个内存块。
  • 然后我们选择每个块内的局部布隆过滤器。
  • 这可能会导致内存块之间不平衡。
  • 这种过滤器效率很高，但假阳性率 (FPR) 较差。
  • 首先，阻塞布隆过滤器的假阳性率 (FPR) 应该与相同大小的标准布隆过滤器相同。
  • 阻塞布隆过滤器由一系列块 b 组成，这些块 b 比标准布隆过滤器 (布隆过滤器块) 小得多，每个块都适合一个缓存行。
  • 阻塞布隆过滤器方案与分区方案不同，在分区方案中，每个比特都插入到不同的块中。

阻塞布隆过滤器可以通过以下方式实现：

位模式 (pat)

在本主题中，我们讨论了如何通过实现预计算位模式来实现阻塞布隆过滤器。与其通过评估 k 个哈希函数来设置 k 个比特，不如使用单个哈希函数从一个包含宽度为 B 的随机 k 位模式的表中选择一个预计算模式。在许多情况下，此表将适合缓存。使用此解决方案，只需要一个小的（就比特而言）哈希值，并且可以使用少量 SIMD（单指令多数据）指令来实现该操作。在传输布隆过滤器时，无需在数据中显式包含该表，而是可以通过实现种子值来重建该表。

位模式方法的主要缺点是，当两个元素被哈希到相同的模式时，它们可能会导致表冲突。这会导致 FPR 增加。

多路复用模式

为了进一步改进这个想法，我们可以通过将 x 个模式进行按位或运算来从单个表中获得更多种类的模式，这些模式的平均设置位数为 k/x。

多块

另一种有助于提高 FPR 的变体称为多块。我们允许查询操作访问 X 个布隆过滤器块，分别在每个块中设置或测试 k/X 个比特。（当 k 不能被 X 整除时，我们在前 k mod X 个块中设置一个额外的比特。）多块的性能优于将块大小简单地增加到 XB（B-每个块大小），因为这样可以引入更多变化。如果我们将设置的位分布在几个块中，则每个块中 1 位的预期数量保持不变。但是，在访问元素时，每个参与块中只考虑 k/X 个比特。

更新于：2020年1月3日

747 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告