时间戳

首页 > 解决方案 > 布谷鸟过滤器必须使用 2 的下一个幂作为容量吗？

filter - 布谷鸟过滤器必须使用 2 的下一个幂作为容量吗？

问题描述

我发现大多数布谷鸟过滤器实现都将调用者提供的容量增加到了 2 的下一个幂。我没有在论文中看到任何提到“m”必须是 2 的幂的地方。这样做会导致较小的平均负载因子。

标签： filterbloom-filter

解决方案

我认为没有必要使容量为2的幂，但需要对原始方法进行一些更改。

我之前搜索过这个问题。从这个答案中，Giuseppe Ottaviano 认为论文给出的 95% 负载系数取决于表格大小的 2 次方，否则负载系数可能差到 50%。在那里，DW 推广了一种替代公式，该公式与非 2 的幂一起使用来解决这个问题。

虽然负载因子不依赖于此（我将在下面的实验中展示），但使用 xor 选择候选位置确实需要杜鹃滤波器的容量为 2 的幂。例如，如果指纹是 128 并且 i1 = 32，哈希（128）= 73，容量= 100。i2 = (i1 xor hash(fingerprint)) mod 100 = 5 而不是105。

但是，(105 xor hash(128)) mod 100 = 32, (5 xor hash(128)) mod 100 = 76。这意味着 xor 不是对合，会导致 cuckoo 滤波器的意外行为。

所以在这种情况下，它应该使用其他对合方法来选择候选位置，就像 DW 提到的那样h_2(x) = hash(fingerprint) - h_1(x) mod n。

使用上述数据，h1(x) = i1 = 32, hash(fingerprint) = 73, h2(x) = hash(fingerprint) - h1(x) = 41。如果 hash(fingerprint) 小于 h1(x ) 这种方法仍然有效。当 h1(x) = 89, h2(x) = (73-89) +100 = 84, 时h1(x) = (73-84) + 100 = 89，它仍然是对合的。

实验

然而，与异或不同，替代方法可以使用与候选相同的位置。仍在使用capacity = 100, lethash(fingerprint)=70和h1(x) = 85, h2(x) = hash(fingerprint) - h1(x) mod capacity = 85 = h1(x)。这可能对负载系数有一些影响，因为插入更容易失败。我最近在 go 中完成了一个布谷鸟过滤器，并对负载因子进行了测试。

我测试了许多具有不同容量和桶大小的参数。单元测试代码如下。它将随机整数插入 cuckoo 过滤器，直到交换操作的时间超过 500。

ckflter := cuckooFilter.CuckooFilter{}
ckflter.NewCuckooFilter(tt.args.capacity,tt.args.bucketSize)

over := false
for !over{
    element := rand.Intn(123456789000)
    ok,_ := ckflter.Add(bloomfilter.CFElement{ElementValue: strconv.Itoa(element)})
    if !ok{
        over = true
    }
}
fmt.Printf("Go test %s. Load factor %f",tt.name,ckflter.CalculateLoadFactor())

不同场景和论据的结果(capacity,bucket_size)。那里的容量意味着布谷鸟过滤器中的桶数。Bucket_size 表示一个bucket中的指纹个数，b在paper中。

原始数据发布在此答案的末尾。我计算了不同存储桶大小的平均负载因子，并在下面列出。

情况 不使用 2 的下一个幂 使容量成为 2 的次幂 替代方法
桶大小 1 0.393278 0.45014 0.40673
桶大小 2 0.884191 0.878049 0.872531
桶大小 4 0.970461 0.963951 0.964365
桶尺寸 8 0.990913 0.989525 0.990372

no use next power of 2表示即使容量不是 2 的幂，也使用 xor 计算候选位置。alternative method表示不使用 2 的下一个幂，并h2(x) = hash(fingerprint) - h1(x) mod capacity根据这篇文章计算候选位置

结果表明，上述所有三种方法的负载因子都非常相似。因此，替代方法适用于不是 2 的幂的容量。

PS：很抱歉我不能在互联网上发布我的代码，因为它被一家公司用于商业用途。我的实现是基于seiflotfy/cuckoofilter

PS2：原点数据

情况 不使用 2 的下一个幂 使容量成为 2 的次幂 替代方法
(100,1) 0.170000 0.656250 0.460000
(128,1) 0.539062 0.507812 0.546875
(800,1) 0.591250 0.417969 0.582500
(1024,1) 0.517578 0.488281 0.593750
(10000,1) 0.565100 0.491699 0.362200
(16384,1) 0.458374 0.505737 0.483582
(100000,1) 0.302530 0.451401 0.238530
(131072,1) 0.372047 0.341164 0.315895
(1000000,1) 0.145227 0.328159 0.125209
(1048576,1) 0.271615 0.312927 0.358754
(100,2) 0.935000 0.898438 0.885000
(128,2) 0.875000 0.898438 0.878906
(800,2) 0.887500 0.886719 0.872500
(1024,2) 0.868164 0.886230 0.894043
(10000,2) 0.916100 0.868591 0.871800
(16384,2) 0.868042 0.874420 0.871399
(100000,2) 0.895480 0.867485 0.861490
(131072,2) 0.867046 0.871918 0.861286
(1000000,2) 0.868981 0.863855 0.859927
(1048576,2) 0.860598 0.864397 0.868959
(100,4) 0.997500 0.974609 0.972500
(128,4) 0.980469 0.953125 0.972656
(800,4) 0.967187 0.975098 0.965000
(1024,4) 0.968750 0.973389 0.969971
(10000,4) 0.974725 0.967117 0.962075
(16384,4) 0.967117 0.965134 0.966309
(100000,4) 0.966420 0.960672 0.957130
(131072,4) 0.963726 0.960442 0.961651
(1000000,4) 0.959142 0.954331 0.956140
(1048576,4) 0.959578 0.955596 0.960214
(100,8) 1.000000 0.995117 1.000000
(128,8) 1.000000 0.989258 0.995117
(800,8) 0.992031 0.992798 0.988125
(1024,8) 0.994751 0.991211 0.993896
(10000,8) 0.987962 0.989838 0.989287
(16384,8) 0.991455 0.989746 0.991959
(100000,8) 0.985891 0.987493 0.987804
(131072,8) 0.987256 0.987178 0.987913
(1000000,8) 0.984694 0.986127 0.983695
(1048576,8) 0.985085 0.986484 0.985922
总时间 14.74s 15.22s 14.49s

推荐阅读