
Filters are fast, small 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, a query x not in S). Filters have one-sided errors: on a negative query, a filter may say "present" with a tunable false-positve probability of epsilon. Correctness is traded for space: filters only use log (1/��) + 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 of a filter, a subsequent query to x is a false positive with probability 1, not epsilon. With this in mind, recent work has introduced the notion of an adaptive filter. A filter is adaptive if each query has false positive epsilon, regardless of what queries were made in the past. This requires "fixing" false positives as they occur. Adaptive filters not only provide strong false positive guarantees in adversarial environments but also improve performance on query practical workloads by eliminating repeated false positives. Existing work on adaptive filters falls into two categories. First, there are practical filters based on cuckoo filters that attempt to fix false positives heuristically, without meeting the adaptivity guarantee. Meanwhile, the broom filter is a very complex adaptive filter that meets the optimal theoretical bounds. In this paper, we bridge this gap by designing a practical, provably adaptive filter: the telescoping adaptive filter. We provide theoretical false-positive and space guarantees of our filter, along with empirical results where we compare its false positive performance against state-of-the-art filters. We also test the throughput of our filters, showing that they achieve comparable performance to similar non-adaptive filters.
FOS: Computer and information sciences, cuckoo filters, Bloom filters, quotient filters, Filters, approximate-membership query data structures (AMQs), 004, adaptivity, succinct data structures, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), ddc: ddc:004
FOS: Computer and information sciences, cuckoo filters, Bloom filters, quotient filters, Filters, approximate-membership query data structures (AMQs), 004, adaptivity, succinct data structures, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), ddc: ddc:004
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
