计算机应用

作者：华文镝, 高原, 吕萌, 谢平

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

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

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

布隆过滤器（BF）是一种基于哈希策略的二进制向量数据结构，凭借分摊哈希碰撞的思想、存在单向误判性的特点以及极小常数查询时间复杂度，常用于表示集合元素并作为进行集合元素查询操作的“加速器”。作为计算机工程中解决集合元素查询问题最好的数学工具，BF在网络工程、存储系统、数据库、文件系统、分布式系统等领域得到了广泛的应用和发展。近几年来，为了适用于各种硬件环境和应用场景，BF出现了大量基于改变结构、优化算法等思想的变种方案。随着大数据时代的发展，对BF自身特点和操作逻辑进行改进已经成为现有集合元素查询研究的一个重要方向。

来源：2022年第6期

《计算机应用》期刊编辑部

查看计算机应用杂志2022年第6期