过滤器数据结构研究综述

摘要：

过滤器数据结构可以近似地判断某个元素是否属于给定集合.典型的过滤器数据结构,如布隆过滤器、布谷鸟过滤器、商过滤器,以牺牲查询准确性为代价换取更低的内存空间消耗和查询时间开销.因此,得益于空间时间高效性,过滤器数据结构现已被广泛应用于计算机网络、物联网、数据库系统、文件系统、生物信息学、机器学习等领域的近似成员资格查询操作中.自20世纪70年代以来,过滤器数据结构受到了广泛的研究,在诸多领域取得了重要的进展,其研究思路也在不断变化.文中整理了近五十年来关于过滤器数据结构的经典研究成果,从过滤器数据结构的原理出发对已有工作进行分类总结,并比较不同工作之间的引证关系和改进思路,最后讨论了过滤器数据结构的未来研究方向.

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

所属期刊栏目：51

分类号：TP391(计算技术、计算机技术)

在线出版日期：2024-01-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：35-40