Telescoping Filter: A Practical Adaptive Filter
Telescoping Filter: A Practical Adaptive Filter
复制标题
DOI：
10.4230/lipics.esa.2021.60
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
David J. Lee;Samuel McCauley;Shikha Singh;Maximilian Stein
中科院分区：
文献类型：
--
作者：
David J. Lee;Samuel McCauley;Shikha Singh;Maximilian Stein
过滤器是小型、快速且近似的集合成员数据结构。它们通常用于过滤掉对远程集合 S 进行否定查询的昂贵访问（即过滤掉查询 x ∉ S）。过滤器存在单方面错误：对于否定查询，过滤器可能会以可调的误报概率 e 表示“存在”。正确性是以空间为代价的：过滤器每个元素仅使用 log (1/e) + O(1) 位。然而，大多数过滤器的误报保证仅适用于单个查询。特别是，如果 x 是误报，则对 x 的后续查询是误报的概率为 1，而不是 e。考虑到这一点，最近的工作引入了自适应滤波器的概念。如果每个查询都是概率为 e 的误报，则无论先前查询的答案如何，过滤器都是自适应的。这需要在误报发生时“修复”它们。自适应过滤器不仅在对抗环境中提供强大的误报保证，而且还通过消除重复的误报来提高实际工作负载的查询性能。自适应滤波器的现有工作分为两类。一方面，有一些基于布谷鸟过滤器的实用过滤器，试图在不满足自适应保证的情况下启发式地修复误报。另一方面，扫帚滤波器是一种非常复杂的自适应滤波器，满足最佳理论界限。在本文中，我们通过设计伸缩自适应滤波器（TAF）来弥补这一差距，这是一种实用的、可证明的自适应滤波器。我们为我们的过滤器提供理论误报和空间保证，以及将其性能与最先进的过滤器进行比较的经验结果。我们还实现了扫帚过滤器并将其与 TAF 进行比较。我们的实验表明，理论自适应性可以改善实际输入的误报性能，并且可以在保持与非自适应滤波器类似的吞吐量的同时实现。
Filters are small, fast, and approximate set membership data structures. They are often used to filter out expensive accesses to a remote set S for negative queries (that is, filtering out queries x ∉ S). Filters have one-sided errors: on a negative query, a filter may say "present" with a tunable false-positive probability of e. Correctness is traded for space: filters only use log (1/e) + O(1) bits per element. The false-positive guarantees of most filters, however, hold only for a single query. In particular, if x is a false positive, a subsequent query to x is a false positive with probability 1, not e. With this in mind, recent work has introduced the notion of an adaptive filter. A filter is adaptive if each query is a false positive with probability e, regardless of answers to previous queries. This requires "fixing" false positives as they occur. Adaptive filters not only provide strong false positive guarantees in adversarial environments but also improve query performance on practical workloads by eliminating repeated false positives. Existing work on adaptive filters falls into two categories. On the one hand, there are practical filters, based on the cuckoo filter, that attempt to fix false positives heuristically without meeting the adaptivity guarantee. On the other hand, the broom filter is a very complex adaptive filter that meets the optimal theoretical bounds. In this paper, we bridge this gap by designing the telescoping adaptive filter (TAF), a practical, provably adaptive filter. We provide theoretical false-positive and space guarantees for our filter, along with empirical results where we compare its performance against state-of-the-art filters. We also implement the broom filter and compare it to the TAF. Our experiments show that theoretical adaptivity can lead to improved false-positive performance on practical inputs, and can be achieved while maintaining throughput that is similar to non-adaptive filters.