Aleph Filter: To Infinity in Constant Time

简介

过滤数据结构被广泛应用于计算机科学的各个领域，以回答近似的集合成员查询。在许多应用中，数据是动态增长的，需要它们的过滤器随着它们所代表的数据扩展。然而，现有的扩展过滤器的方法不能同时保持稳定的性能、内存占用和误报率。我们通过 Aleph Filter 来解决这个问题，它做出了以下贡献：(1)它支持所有操作（插入、查询、删除等），不论数据增长多少，都是常数时间。(2)给定数据最终增长的任何粗略估计，即使估计偏差很大，Aleph Filter 也提供了更好的内存与误报率的权衡。
作者讲解

目前尚无作者解读视频，你可点击下方【许愿开讲】按钮，许愿作者开讲~
图表
解决问题

设计一个数据结构，能够在数据增长时保持稳定的性能、内存占用和误报率。
关键思路

提出了一种名为Aleph Filter的数据结构，支持常数级时间复杂度的插入、查询和删除操作，并且能够根据数据增长的估计量，在内存占用和误报率之间提供更好的权衡。
其它亮点

实验表明，Aleph Filter在多个数据集上的表现都优于现有的方法。此外，Aleph Filter的设计思路也可以应用于其他数据结构的设计中。
相关研究

与此相关的研究包括Bloom Filter及其变体、Cuckoo Filter等。