过滤器数据结构研究综述  

Filter Data Structures:A Survey

作　　者：王瀚橙 戴海鹏[1] 陈树森 陈志鹏 陈贵海[1] WANG Hancheng;DAI Haipeng;CHEN Shusen;CHEN Zhipeng;CHEN Guihai(State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China)

机构地区：[1]计算机软件新技术国家重点实验室(南京大学),南京210023

出　　处：《计算机科学》2024年第1期35-40,共6页Computer Science

基　　金：国家自然科学基金(62272223)。

摘　　要：过滤器数据结构可以近似地判断某个元素是否属于给定集合。典型的过滤器数据结构,如布隆过滤器、布谷鸟过滤器、商过滤器,以牺牲查询准确性为代价换取更低的内存空间消耗和查询时间开销。因此,得益于空间时间高效性,过滤器数据结构现已被广泛应用于计算机网络、物联网、数据库系统、文件系统、生物信息学、机器学习等领域的近似成员资格查询操作中。自20世纪70年代以来,过滤器数据结构受到了广泛的研究,在诸多领域取得了重要的进展,其研究思路也在不断变化。文中整理了近五十年来关于过滤器数据结构的经典研究成果,从过滤器数据结构的原理出发对已有工作进行分类总结,并比较不同工作之间的引证关系和改进思路,最后讨论了过滤器数据结构的未来研究方向。Filter data structures can approximately determine whether an element exists in a given set.Typical filter data structures,such as Bloom filters,cuckoo filters,and quotient filters,sacrifice query accuracy for lower memory space consumption and lower query time overhead.Due to their spatial and temporal efficiency,filter data structures are now widely used in approximate membership query operations in computer networks,the Internet of Things,database systems,file systems,bioinformatics,machine learning,and other fields.Since the 1970s,filters have been extensively studied.Their research ideas are constantly changing.This paper compiles the classic studies on filter data structures in the past fifty years,summarizes existing studies based on the mechanism of filter data structures and analyze the relationship between different studies.Finally,future research directions in filter data structures are discussed.

关 键 词：过滤器 近似成员资格查询 概率数据结构 布隆过滤器 布谷鸟过滤器 商过滤器 

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