布隆过滤器阻塞
我们首先选择一个存储块。
然后，我们在每个块中选择本地布隆过滤器。
可能导致内存块之间不平衡
该过滤器有效，但误报率(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位。
以上是 布隆过滤器阻塞 的全部内容， 来源链接： utcz.com/z/317027.html
