首页 > 其他分享 >Cuckoo Filters 及其变体的整理

Cuckoo Filters 及其变体的整理

时间:2024-04-16 20:55:05浏览次数:22  
标签:元素 Hash Cuckoo 位置 Filter Filters fingerprint 变体

Basic Cuckoo Filter

Cuckoo Filter 是一种 Cuckoo Hash 的变体,使用 \(fingerprint\) 来派生出元素在表中的另一个备选位置。在正确的配置下,Cuckoo Filter 的错误率约为0.19%。

Cuckoo Filter 相对于 Bloom Filter 的优势

  1. 支持元素的动态删除
  2. 比 Bloom Filter 更高的查找效率
  3. 实现简单
  4. 在实际实现时所需的存储空间比 Bloom Filter 低

构造

  • 每个元素的两个位置为:

\[\begin{gather}BUCKET_1=Hash(x)\nonumber\\ BUCKET_2=BUCKET_1\,xor\,Hash(fingerprint(x))\nonumber\end{gather}\]

    • 如果目标位置为空则直接插入,其中\(Fin(x)=fingerprint(x)\)。
      增加操作
    • 如果目标位置不为空,则将目标位置的元素 \(t\) 踢出到 \(t\) 的备选位置。
      增加操作-2
    • 找到待删除元素 \(x\) 对应的两个备选位置,如果其中包括\(fingerprint(x)\),则将其删除。
      删除操作
    • 找到查找元素 \(x\) 对应的两个备选位置,如果其中包含\(fingerprint(x)\),则返回 True,否则返回 False。
  • 扩展

    • 可以为 filter 的每个位置设置多个“框”,每个“框”都可以装入元素的\(fingerprint\)。
    • 增加、删除、查询元素的操作与上述操作类似,只不过每个位置可以装入的元素数量变多。
      Cuckoo Filter 扩展

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 方案的异或运算明显不支持多个备选位置:

\[\begin{multline}Hash(x)\oplus Hash(fingerprint(x))\oplus Hash(fingerprint(x))=Hash(x)\nonumber\end{multline} \]

因此 d-ary Cuckoo Hash 方案定义了一种新的运算 \(xor_d\),这也是一种类似于异或的运算,我们用 \(d=3\) 举例:
$xor_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.

标签:元素,Hash,Cuckoo,位置,Filter,Filters,fingerprint,变体
From: https://www.cnblogs.com/Hi-tsuki/p/18134581

相关文章

  • nestJs中 Guards ,Interceptors ,Pipes ,Controller ,Filters的执行顺序
    执行顺序:Guards(守卫):Guards是最先执行的中间件,用于确定是否允许请求继续处理。Guards在请求被路由到控制器之前执行,通常用于身份验证、角色检查或权限验证。如果Guards返回一个布尔值 false 或者抛出一个异常,请求处理流程将终止,不会执行后续的Pipes、Interceptors或控......
  • LoRA及其变体概述:LoRA, DoRA, AdaLoRA, Delta-LoRA
    LoRA可以说是针对特定任务高效训练大型语言模型的重大突破。它被广泛应用于许多应用中。在本文中,我们将解释LoRA本身的基本概念,然后介绍一些以不同的方式改进LoRA的功能的变体,包括LoRA+、VeRA、LoRA-fa、LoRA-drop、AdaLoRA、DoRA和Delta-LoRA。Lora低秩自适应(Low-Rankadapt......
  • SARS-CoV-2变体的筛选
    1.DesignofmolecularswitchandNOTlogicgate分子开关和非逻辑门的设计作者设计了两个基于DNA的链位移反应,以模拟两个半导体器件(图1a和b)。作为开关信号的A1和A0分别定义为输入1和输入0。A1是特异性的SARS-CoV-2序列。A0是特定的SARS-CoV-2β变体(B.1.351)序列。每个MS......
  • vue中filters和computed有什么区别
    在Vue.js中,filters和computed都是用来处理模板中的数据的方式,但它们有不同的应用场景和使用方式。filters是一种简单的函数,可以在模板中对数据进行格式化。它们可以用于在显示数据之前对其进行处理,例如对日期格式进行转换、将文本转换为大写或小写字母等。filters没有缓存......
  • fiddleer - Filters 网页过滤
     Fiddler工具—Fiddler过滤器(Filters)详解1、Filters介绍Filters:过滤器,帮助我们过滤请求。如果需要过滤掉与测试项目无关的抓包请求,更加精准的展现抓到的请求,而不是杂乱的一堆,那功能强大的Filters过滤器能帮到你。总结:Filters过滤器的作用,过滤出我们想要的请求......
  • 【设计模式】单例模式——单例模式变体之“多例模式”
    所谓“多例模式”并不在GoF的23种设计模式之内,是单例模式中的一种特例,在很多资料中也被称为单例模式的容器式实现。“多例模式”可以理解为在一定数量范围内创建类的多个实例(简称“说法一”);还有一层理解就是不同类型的对象可以创建多个,但相同类型的对象只能创建一个(简称“说法二”)......
  • Sigmoid核与其变体: 探索不同激活函数的表现
    1.背景介绍激活函数是深度学习中的一个关键概念,它在神经网络中的主要作用是为了解决模型的非线性问题。在神经网络中,每个神经元的输出是通过一个激活函数进行处理的,这个激活函数将输入的线性组合映射到一个非线性空间中。因此,选择合适的激活函数对于模型的性能至关重要。在这篇文章......
  • Java-与斐波那契数列相关的变体问题
    变体问题指的是提问的方式不一样了,但是解决问题的方法还是用斐波那契数列来解。——写在前面的话。一、变体1-兔子问题1.问题描述第一个月,有一对未成熟的兔子第二个月上述的一对兔子成熟第三个月,他们能产下一对小兔子所有兔子遵循相同规律,求第n个月的兔子个数2.分析例子假设我要求......
  • delphi 变体Variant数组常用操作
    变体Variant数组常用操作代码procedureTForm1.Button1Click(Sender:TObject);varArr1,Arr2,Arr3:Variant;I,J:Integer;begin//创建包含10个整数类型元素的变体数组Arr1:=VarArrayCreate([0,9],varInteger);//创建2维数组,其中第1维是3个元素,第2维是5......
  • pure::variants—产品平台化及变体管理工具
    产品概述    pure::variants是德国pure-systems公司的产品,其目的是帮助企业实现对产品线的变体管理,提高企业项目资产的复用效率。pure::variants的核心理念是运用产品线管理方法对项目资产(项目计划、需求、模型、功能模块、代码、测试用例)进行系统的复用管理,将管理的关注......