布隆过滤器阻塞

  • 我们首先选择一个存储块。

  • 然后,我们在每个块中选择本地布隆过滤器。

  • 可能导致内存块之间不平衡

  • 该过滤器有效,但误报率(FPR)较差。

  • 首先,阻塞的布隆过滤器应具有与相同大小的标准布隆过滤器相同的FPR(误报率)。

  • 块状布隆过滤器由一系列比标准布隆过滤器(布隆过滤器块)少的块b组成,每个布隆过滤器都适合一条高速缓存行。

  • 块式布隆过滤器方案不同于分区方案,在分区方案中,每个位都插入到不同的块中。

阻止布隆过滤器通过以下方式实现-

位模式(拍)

在本主题中,我们讨论如何实现阻塞的Bloom滤波器,从而实现预计算的位模式。单个哈希函数不是通过评估k个哈希函数来设置k位,而是从宽度为B的随机k位模式表中选择一个预先计算的模式。在许多情况下,该表将适合高速缓存。利用该解决方案,仅需要一个小的(就位而言)哈希值,并且可以使用很少的SIMD(单指令多数据)指令来实现该操作。在传输布隆过滤器时,该表无需明确包含在数据中,但可以通过实现种子值进行重构。

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

复用模式

为了再次完善这个想法,我们可以通过平均数量为k / x个设置位的x个模式按位与或运算从一张表中获得更多种模式。

多块

帮助改善FPR的另一种变体称为多块。我们允许查询操作访问X Bloom过滤器块,分别在每个块中设置或测试k / X位。(当k不能被X整除时,我们在前k个mod X块中设置一个额外的位。)多块执行比将块大小增加到XB(每个B块大小)要好,因为引入了更多种类方式。如果我们将设置位分配到几个块中,则每个块1位的预期数量保持不变。但是,访问元素时,每个参与块中仅考虑k / X位。