Cuckoo Filter

news/2024/3/29 12:54:22/文章来源:https://blog.csdn.net/m0_61567378/article/details/130300812

其他判重数据结构

  • Bloom Filter
  1. 无法支持删除计数的功能,
  2. 需要更多的存储空间来存储数据

因为在CS中,删除计数是常见的操作,但是这会对布隆过滤器的存储空间产生影响,同样为了实现这一操作,需要更多的存储空间

  1. 数据量一旦达到了一定的层级,就需要进行一个扩容,对数据进行一个rehash

理论篇

如何工作

Cuckoo Filter可以支持删除有限计数有界FPP1来优化布隆过滤器,其存储效率高于标准布隆过滤器

Cuckoo hash table in action

  • cuckoo的每个元素使用两个bucket(每个元素对应到两个不同的bucket索引位置)
  • cuckoo的每个bucket可能会存储多个元素,不只有一个元素
  • bucket中存储的是data的低f位指纹而不是真实的数据(根据FPP确定的)
  • 使用部分对称密钥来计算两个bucket的索引位置

基础操作

  1. 查找元素的时候,cuckoo会使用哈希函数并检查两个桶中的指纹,没有找到匹配的指纹,说明数据一定不在,如果找到了指纹,那么数据可能在
  2. 当另一个元素将匹配到的指纹插入到两个已检查桶的任何一个时,就会报错
  3. 删除:删除该值对应存储桶中的指纹
  4. 计数:在cuckoo 中维护一个count来实现
  5. 插入:计算出两个bucket索引位置,将元素的指纹存放到两个bucket的其中一个空闲的位置中,冲突就需要进行递归的对元素迁移,重复上诉操作

实现

获得索引位置

bucketi=h1(x) = hash(x),
//使用对称加密
bucketj=h2(x) = h1(x) ⊕ hash(x’s fingerprint).
//使用对称加密很方便获得另一个hash位置
bucketi=bucketj^hash(x’s fingerprint).

    void generateIndexHash(const string &data, uint32_t fp, uint32_t &b1, uint32_t &b2) //根据该finger生成获得对应的存储位置{b1 = finger_hash_(data) % num_bucket_; //生成两个索引位b2 = (b1 ^ finger_hash_(to_string(fp))) % num_bucket_;}

插入

cuckoo 会使用hash函数将与元素hash到两个bucket中,并将指纹(低f位,根据hash函数计算出来的(和选择插入位置的哈希函数不同))插入到任意一个开放的位置(每个hash桶可以存储多个元素,而不仅仅只有一个)

  • 如果两个桶都有位置,那么cuckoo会将该元素的指纹随机选择一个桶插入(不是插入到两个桶),插入到该桶中的任意一个空闲的位置(由hash函数计算出来)
  • 如果随机选择的其中一个桶位置被占了,就会插入到另一个桶中
  • 如果两个桶都满了,cuckoo会将其中一个桶的某个元素踢走,新元素插入到该位置上,如果被题的元素有备用位置,就将其插入到备用的位置上,递归(递归的进行插入,在两个桶捣腾,重复上诉过程)这一过程,如果所有备用位置都完了,就认为失败
    在这里插入图片描述
    bool InsertImpl(uint32_t fp, uint32_t bucket_index){vector<uint32_t> &bucket = table_[bucket_index]; //获得对应的桶//因为每个桶存4个元素for (uint8_t i = 0; i < num_entry_per_bucket_; i++){if (!bucket[i]){max_entry_++; //存储的元素++bucket[i] = fp;return true;}}return false;}bool Insert(const string &data){//获得指纹,获得低finger位置uint32_t fp = finger_hash_(data) & ((1 << fingerprint_size_) - 1); //这个是对应的指纹位最大也才10位,所以不会超出限制uint32_t b1, b2;                                                   //每个元素对应两个索引位置generateIndexHash(data, fp, b1, b2);if (InsertImpl(fp, b1))return true;if (InsertImpl(fp, b2))return true;//两个都满了(2个bucket的8个位置都满了),所以需要进行一个迭代kickfor (uint32_t i = 0; i < kMaxNumKicks; i++){//选择其中一个桶的元素,并让该元素离开uint32_t b = (rand() % 2 == 0) ? b1 : b2;uint32_t r = rand() % num_entry_per_bucket_; //获得要替代的元素uint32_t tmp_fp = table_[b][r];table_[b][r] = fp; //插入fp = tmp_fp;       //将该kick出去的fp要获得他其他的索引位//根据该fingerprint获得其对应的两个索引位置//还是b1和b2两个位置if (b == b1){//因为在转化的时候,要替换的元素只有一个位置不一样if (b2 = (finger_hash_(to_string(fp)) ^ b1) % num_bucket_; InsertImpl(fp, b2))return true;}if (b == b2){if (b1 = (finger_hash_(to_string(fp)) ^ b2) % num_bucket_; InsertImpl(fp, b1))return true;}}return false;}

查找

bool lookUpImpl(uint32_t fp, uint32_t index){vector<uint32_t> &bucket = table_[index];for (uint8_t i = 0; i < num_entry_per_bucket_; i++){if (bucket[i] == fp){return true;}}return false;}bool lookUp(const string &data) //查找一个元素{uint32_t fp = finger_hash_(data) & ((1 << fingerprint_size_) - 1); //这个是对应的指纹位最大也才10位,所以不会超出限制uint32_t b1, b2;generateIndexHash(data, fp, b1, b2);if (lookUpImpl(fp, b1) || lookUpImpl(fp, b2)){return true;}return false;}

删除

    bool DeleteImpl(uint32_t fp, uint32_t index) //实现删除的逻辑{vector<uint32_t> &bucket = table_[index];for (uint8_t i = 0; i < num_entry_per_bucket_; i++){if (bucket[i] == fp){//找到了max_entry_; //总个数减少bucket[i] = 0;return true;}}return false;}bool Delete(const string &data) //删除一个元素{uint32_t fp = finger_hash_(data) & ((1 << fingerprint_size_) - 1); //这个是对应的指纹位最大也才10位,所以不会超出限制//获得他的索引位置uint32_t b1, b2;generateIndexHash(data, fp, b1, b2);//因为一个元素只会出现一个bucket中,所以找到一个就算可以了if (DeleteImpl(fp, b1) || DeleteImpl(fp, b2)){return true;}return false;}

有什么用

  1. 可以帮助我们快速的检查一个元素是否在某个集合中
  2. 数据库查询优化,将数据插入到cuckoo中,可以通过查询过滤器,来测试某个数据是否存在,如果查询失败,就不需要访问数据库
  3. 边缘过滤,可以帮助我们快速的过滤掉一些无用的请求,提高网络传输效率。
    类似于边缘缓存,但原始数据不需要存储在过滤器中

    1.利用网络边缘的缓存节点CDN边缘节点缓存数据的技术,可以更快的向用户提供所需的内容,用户在请求特定的数据,即使在远程的服务器上,也能在较短的时间进行访问,常用在静态网页图像视频音乐等多媒体内容的分发
    2. 原始数据不需要存在过滤器中:可以在数据流传输过程中通过算法技术架构。进行实时的分析和过滤操作,提高数据处理和应用的效率可靠性

如何选择

  1. Cuckoo Filter如果不会影响时间敏感度2,优先选择Cuckoo Filter,Cuckoo相比拥有更好的查询速度更低的误判率,时间敏感度更好,可以快速的响应各种请求并且缩短响应时间
  2. Cuckoo的插入上随着数据的增多,效率会逐渐低下
  3. 对于相同的误报率,Cuckoo需要更少的空间
  4. Cuckoo还可以支持删除操作

参考

Cuckoo filter [Explained]
Cuckoo Filter: Practically Better Than Bloom
Bloom Filters by Example


  1. False Positive Probability,假阳性的概率,概率容器可以错误返回true ↩︎

  2. 时间敏感度指完成任务所需要的响应时间或处理时间的要求或限制,对任务的响应和处理时间要求高 ↩︎

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_102414.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ArcGIS Pro导航工具

主要导航工具为浏览工具 、屏幕导航器 、书签 、转到XY工具 。 其它还包括链接视图、地图比例&#xff08;2D&#xff09;、场景高度&#xff08;3D&#xff09;、暂停并刷新绘制、照相机属性、在3D模式下导航、键盘快捷键等。 1 主要导航工具 地图和场景的默认工具为浏览工具…

C++ “类与对象”

类与对象的概念 类相当于是结构体的声明&#xff0c;是结构体的设计图&#xff0c;而对象是利用设计图的创造的产物. &#xff08;1&#xff09;.类的大小计算 类的大小计算时与结构体类似&#xff0c;但函数是不计入大小的&#xff08;函数放在单独的公共空间&#xff09;. 在…

Unity API详解——Object类

Object类是Unity中所有对象的基类&#xff0c;例如GameObject、Component、Material、Shader、Texture、Mesh、Font等都是Object的子类。本博客介绍Object类的一些实例方法和静态方法。 一、Object类实例方法 在Object类中&#xff0c;涉及的实例方法主要有GetInstanceID方法…

8. 优先队列

8. 优先队列 普通的队列是一种先进先出的数据结构&#xff0c;元素在队列尾追加&#xff0c;而从队列头删除。在某些情况下&#xff0c;我们可能需要找出队列中的最大值或者最小值&#xff0c;例如使用一个队列保存计算机的任务&#xff0c;一般情况下计算机的任务都是有优先级…

ROS1学习笔记:常用可视化工具的使用(ubuntu20.04)

参考B站古月居ROS入门21讲&#xff1a;常用可视化工具的实现 基于VMware Ubuntu 20.04 Noetic版本的环境 文章目录 一、日志输出工具&#xff1a;rqt_console二、绘制数据曲线&#xff1a;rqt_plot三、 图像渲染工具&#xff1a;rqt_image_view四、图形界面总接口&#xff1a;r…

kong(4):限流配置

Kong 提供了 Rate Limiting 插件&#xff0c;实现对请求的限流功能&#xff0c;避免过大的请求量过大&#xff0c;将后端服务打挂。 Rate Limiting 支持秒/分/小时/日/月/年多种时间维度的限流&#xff0c;并且可以组合使用。例如说&#xff1a;限制每秒最 多 100 次请求&…

初识Android内存优化

一、简介 Android 内存优化是指优化 Android 应用程序的内存使用&#xff0c;以减少可用内存的消耗&#xff0c;提高应用程序的性能和可靠性。Android 内存优化可以通过减少内存使用量&#xff0c;减少对资源的消耗&#xff0c;以及提高内存利用率来实现。 安卓系统对每个应用…

什么才是好CDN

选择一种领先于网络和移动技术不断进步以及不断演变的威胁格局的CDN&#xff0c;将使您能够始终如一地为客户提供尽可能好的在线体验&#xff0c;同时最大限度地降低运营复杂性和管理成本。 但问题来了&#xff1a;什么才是最好的CDN&#xff1f; 这个问题的唯一答案是&#x…

Tomcat概述以及部署与优化

一、Tomcat概述 1、Tomcat的概念 Tomcat是Java语言开发的&#xff0c;服务器是一个免费的开放源代码的Web应用服务器&#xff0c;属于轻量级应用服务器&#xff0c;在中小型系统和并发访问用户不是很多的场合下被普遍使用&#xff0c;是开发和调试JSP程序的首选。一般来说&am…

Flutter开发日常练习-小猫咪杂货店(新增动画和跳转抖音)

之前的练习加了个详情页面,然后跳转第三方页面抖音用户详情页面 跳转详情页添加了Hero的动画,共享元素过度 一个 标准 hero 动画 使 hero 从一页飞至新页面&#xff0c;通常以不同大小到达不同的目的地。 设定好每个图片的id,通过id作为 Hero 组件的标识,id不能重,否则会报错&…

OSCP-Medjed(重置用户密码、mysql写webshell、可写文件替换提权)

目录 扫描 FTP WEB 提权 扫描 FTP 尝试登录到FTP服务器,该服务器位于端口30021 使用Filezilla,并能够浏览文件。那里有一些配置文件,但找不到任何值得注意的东西,不能写入目录。

算法--前缀和技巧 (蓝桥杯123-灵能传输)

文章目录 什么是前缀和用途什么时候用例题[蓝桥杯 2021 国 ABC] 123题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路代码 灵能传输(蓝桥杯96%&#xff0c;洛谷ac)[蓝桥杯 2019 省 B] 灵能传输题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1…

【Leetcode -21.合并两个有序链表 -83.删除排序链表中的重复元素】

Leetcode Leetcode-21.合并两个有序链表Leetcode-83.删除排序链表中的重复元素 Leetcode-21.合并两个有序链表 题目&#xff1a;将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 […

【Web3.0大势所趋】我看到了互联网未来的模样

前言 Web3.0 是一个越来越受到关注的话题&#xff0c;它被认为将会带来天翻地覆的变化。本文我们一起来谈谈 Web3.0 的概念、特点和优势&#xff0c;并探讨它为什么如此重要和具有革命性的。 文章目录 前言Web3.0是什么Web3.0的技术Web3.0的优势总结 Web3.0是什么 Web3.0: 是下…

MATLAB实现图像滤波及噪声消除

图像增强是指根据特定的需要突出一幅图像中的某些信息&#xff0c;同时削弱或去除某些不需要的信息的处理方法。其主要目的是使处理后的图像对某种特定的应用来说&#xff0c;比原始图像更适用。因此&#xff0c;这类处理是为了某种应用目的而去改善图像质量的。处理的结果使图…

最短路径Floyd与区间DP

floyd算法是求最短路径的算法&#xff0c;算法复杂度为n(o^3),其优点在于能够一次求解所有点到其他点的最短路径&#xff0c;不需要其他运算&#xff0c;使用二维数组存储。其三层循环自外向内分别为&#xff1a;中间点&#xff0c;起始点和终点。状态方程为&#xff1a; num[…

JVM原理

JVM 什么是JVM&#xff1f; JVM是一种虚拟出来的计算机&#xff0c;是通过在实际的计算机上仿真模拟各种计算机功能来实现的。 JVM有自己完善的硬件架构&#xff0c;如处理器、堆栈、寄存器等&#xff0c;还具有相应的指令系统。Java语言最重要的特点就是跨平台运行。 使用J…

智慧管廊监控与报警管控一体化系统解决方案

摘要&#xff1a;智慧管廊监控与报警管控是一项综合性质较高的管控操作系统。在各项系统结构之间因为技术管理体系之间的差异&#xff0c;所评价的标准也有着不同的区分&#xff0c;导致各项标准之间难以实现相互之间的联通。这种形式下就需要实现环境与设备之间的监控管理、通…

(IPC)进程间通信的常用的两种方式——管道、共享内存

前言&#xff1a; 众所周知&#xff0c;不同的进程之间&#xff0c;在正常情况下&#xff0c;由于其拥有独立的PCB、上下文等原因&#xff0c;每个进程都是独立且互不干扰&#xff0c;这不仅保证了进程的安全&#xff0c;也降低了OS对于进程的管理成本。 但是通常情况下&…

01-yolo算法

要点&#xff1a; 归纳 YOLOv5 github 1 YOLO v1 1) 将一幅图像分成SxS个网格(grid cell)&#xff0c;如果某个object的中心 落在这个网格中&#xff0c;则这个网格就负责预测这个object。 2)每个网格要预测B个bounding box&#xff0c;每个bounding box 除了要预测位置之…