科创中国

本发明提供了一种有限二叉树布隆过滤器，以及基于该有限二叉树布隆过滤器的去冗文件系统及其构建方法。本发明有限二叉树布隆过滤器每层的节点数设置有上限，每个节点是一个二阶段布隆过滤器，每个二阶段布隆过滤器包括标准布隆过滤器和存储了各数据块的指纹和地址的第二部分。对数据块的指纹首先在标准布隆过滤器中查找，若未查找到，则该节点未命中，否则，继续查找第二部分，在第二部分找到完全匹配的指纹时，该节点命中，否则，该节点未命中。去冗文件及构建方法基于有限二叉树布隆过滤器实现文件的写入、读取和删除。本发明通过二次查询，减少了误判，具备低内存占用、低CPU使用、低额外空间占用、高去冗率存取和可扩展性优良的特点。

一种有限二叉树布隆过滤器，其特征在于，该布隆过滤器具有L层节点，L为正整数，第1层具有两个节点，设每层的节点数上限为Q，A通过对以2为底Q的对数取整得到，则第i层的每个节点在第i+1层都具有两个子节点，i为1到A?1；第j层的每个节点在第j+1层都具有1个子节点，j为A到L；每个节点是一个二阶段布隆过滤器，每个二阶段布隆过滤器包括两部分，第一部分是标准布隆过滤器，第二部分存储了各数据块的指纹和存储地址；第一部分的标准布隆过滤器，包括一个包含有K个哈希函数h11~h1K的集合和一个位数组；位数组中包含w个元素，依次对应1~w的整数，对每个待查找的数据块指纹，分别通过哈希函数h11~h1K计算哈希值，得到K个整数值；当位数组中对应K个整数值的元素都设置为1时，表示该指纹在标准布隆过滤器中命中，否则表示该指纹在该节点中不存在；第二部分包括哈希函数h2、起始位置数组、结束位置数组和大数组；将指纹对应的K个整数值通过哈希函数h2计算，得到一个整数index；整数index所表示的一类数据块指纹，在大数组中存储的起始位置和结束位置，分别存储在起始位置数组和结束位置数组的第index元素中；将经过

布隆过滤器（BLOOM FILTER）是1970年由布隆提出的，它产际上是由一个很长的二进制向量和一系列随意映射函数组成。它是一种基于概率的数据结构，主要用来判某个元素是否在集合骨，它具有运行速度快（时间效率），占用内存小的优点（空间效率），但是有一定的误识别率真和删除困难问题。它能够告诉你苛某个元素一定不在集合内或可能在集合内。 因此，布隆进滤器具有非常广泛的应用场景，它可以快速检索大量数据，准确识别特定元素，高效确定元素是否存在于集合中，并有助于提高网络安全性。它被广泛应用于商业、生物信息学、大数据、机器学习等领域，有助于企业实现良好的效率真和安全。其发展前景广阔。

来自北京航空航天大学，可为本项目的研究开展提供良好的研究工作条件。项目的研究团队由姜博;刘俊龙;王星河;龙翔;高小鹏;万寒组成。团队负责人多年从事相关方面的科研与教学工作，负责完成过科技重大专项课题等以及横向合作等多项课题的研究工作，曾获得国防技术发明奖、国防科学技术奖等多项奖励。团队人员构成合理，技术基础好，研发能力强，为本项目的研究开展提供了良好的人员保障。

本发明提供了有限二叉树布隆过滤器，本发明通过二次查询，减少了误判，具备低内存占用、低CPU使用、低额外空间占用、高去冗率存取和可扩展性优良的特点。随着相关产业的不断发展，该市场规模还将继续扩大。

目前处于何种研发阶段： ☒研发 ☐小试 ☐中试 ☐小批量生产 ☐产业化； 样机： ☒ 有 ☐无 其他：□如选择“其他”，请说明：已投入成本： 500000元。 推广应用情况：已用于学术研究。转化方式：合作开发