Basic Cuckoo Filter
Cuckoo Filter 是一种 Cuckoo Hash 的变体,使用 \(fingerprint\) 来派生出元素在表中的另一个备选位置。在正确的配置下,Cuckoo Filter 的错误率约为0.19%。
Cuckoo Filter 相对于 Bloom Filter 的优势
- 支持元素的动态删除
- 比 Bloom Filter 更高的查找效率
- 实现简单
- 在实际实现时所需的存储空间比 Bloom Filter 低
构造
- 每个元素的两个位置为:
-
增
- 如果目标位置为空则直接插入,其中\(Fin(x)=fingerprint(x)\)。
- 如果目标位置不为空,则将目标位置的元素 \(t\) 踢出到 \(t\) 的备选位置。
- 如果目标位置为空则直接插入,其中\(Fin(x)=fingerprint(x)\)。
-
删
- 找到待删除元素 \(x\) 对应的两个备选位置,如果其中包括\(fingerprint(x)\),则将其删除。
- 找到待删除元素 \(x\) 对应的两个备选位置,如果其中包括\(fingerprint(x)\),则将其删除。
-
查
- 找到查找元素 \(x\) 对应的两个备选位置,如果其中包含\(fingerprint(x)\),则返回 True,否则返回 False。
-
扩展
- 可以为 filter 的每个位置设置多个“框”,每个“框”都可以装入元素的\(fingerprint\)。
- 增加、删除、查询元素的操作与上述操作类似,只不过每个位置可以装入的元素数量变多。
Improved Structure of Cuckoo Filter
不同的 Cuckoo Filter 变体提供了不同的性能和功能性,以下介绍一些常见的 Cuckoo Filter 变体:
d-ary Cuckoo Filter
基础的 Cuckoo Filter 的每个元素 \(x\) 只有两个备选位置,分别为:\(Hash(x)\) , \(Hash(x)\oplus Hash(fingerprint(x))\)。
d-ary Cuckoo Filter 为每个元素提供了 \(d\) 个备选位置,然而使用 basic 方案的异或运算明显不支持多个备选位置:
因此 d-ary Cuckoo Hash 方案定义了一种新的运算 \(xor_d\),这也是一种类似于异或的运算,我们用 \(d=3\) 举例:
横纵坐标上的数据为参与运算的数,对应的数字为结果,例如:\(1\; xor_3\; 1=2\),\(2\; xor_3\; 2=1\),容易看出这也是一种循环运算,即循环对某一个相同数字进行运算 \(d\) 次,最终会回到最开始的数据,因此我们可以利用这种运算来构造新的 d-ary Cuckoo Filter。
- 增
- 如果目标位置 \(Hash(x)\) 空,则插入该位置。
- 如果目标位置不空,即有一个元素 \(fingerprint(y)\),则将该元素踢出,放在 \(Hash(x)\;xor_d\;fingerprint(y)\) 位置中;将 \(fingerprint(x)\) 放在 \(Hash(x)\) 处。
- 删
- 遍历待删除元素 \(x\) 的所有可能位置,如果其中含有 \(fingerprint(x)\),则将其删除。
- 查
- 遍历查找元素 \(x\) 的所有可能位置,如果其中含有 \(fingerprint(x)\),则返回 True,否则返回 False。
待续,整理到了再发出来
参考资料:
[1]Fan B, Andersen D G, Kaminsky M, et al. Cuckoo filter: Practically better than bloom[C]//Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. 2014: 75-88.
[2]Xie Z, Ding W, Wang H, et al. D-Ary Cuckoo Filter: A space efficient data structure for set membership lookup[C]//2017 IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 2017: 190-197.