布隆过滤器研究综述

Research on Bloom filter:a survey

布隆过滤器(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.