布隆过滤器研究综述  

Research on Bloom filter:a survey

作　　者：华文镝 高原 吕萌 谢平[1,2,3,4] HUA Wendi;GAO Yuan;LYU Meng;XIE Ping(Computer College,Qinghai Normal University,Xining Qinghai 8100016,China;Key Laboratory of Internet of Things of Qinghai Province,Xining Qinghai 810008,China;State Key Laboratory of Tibetan Intelligent Information Processing and Application,Xining Qinghai 810018,China;Institute of Plateau Science and Sustainability,Xining Qinghai 810016,China)

机构地区：[1]青海师范大学计算机学院,西宁810016 [2]青海省物联网重点实验室,西宁810008 [3]省部共建藏语智能信息处理及应用国家重点实验室,西宁810008 [4]高原科学与可持续发展研究院,西宁810016

出　　处：《计算机应用》2022年第6期1729-1747,共19页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61762075);青海省自然科学基金资助项目(2020⁃ZJ⁃926)。

摘　　要：布隆过滤器(BF)是一种基于哈希策略的二进制向量数据结构,凭借分摊哈希碰撞的思想、存在单向误判性的特点以及极小常数查询时间复杂度,常用于表示集合元素并作为进行集合元素查询操作的“加速器”。作为计算机工程中解决集合元素查询问题最好的数学工具,BF在网络工程、存储系统、数据库、文件系统、分布式系统等领域得到了广泛的应用和发展。近几年来,为了适用于各种硬件环境和应用场景,BF出现了大量基于改变结构、优化算法等思想的变种方案。随着大数据时代的发展,对BF自身特点和操作逻辑进行改进已经成为现有集合元素查询研究的一个重要方向。Bloom Filter(BF)is a binary vector data structure based on hashing strategy.With the idea of sharing hash collisions,the characteristic of one-way misjudgment and the very small time complexity of constant query,BF is often used to represent membership and as an“accelerator”for membership query operations.As the best mathematical tool to solve the membership query problem in computer engineering,BF has been widely used and developed in network engineering,storage system,database,file system,distributed system and some other fields.In the past few years,in order to adapt to various hardware environments and application scenarios,a large number of variant optimization schemes of BF based on the ideas of changing structure and optimizing algorithm appeared.With the development of big data era,it has become an important direction of membership query to improve the characteristics and operation logic of BF.

关 键 词：布隆过滤器 集合元素查询 近似成员查询结构 哈希策略 误判率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]