Filters tradeoff accuracy for space and occasionally return false positive matches with a bounded error. Numerous systems use filters in fast memory to avoid performing expensive I/Os to slow storage. A fundamental limitation in traditional filters is that they do not change their representation upon seeing a false positive match. Therefore, the maximum false positive rate is only guaranteed for a single and not an arbitrary set of queries. We can improve the filter's performance on a stream of queries (especially on skewed distributions) if we can adapt after seeing false positives.

Adaptive filters, such as telescoping and adaptive cuckoo filters, update their representation upon detecting a false positive to avoid repeating the same error in the future. Adaptive filters require an auxiliary structure, typically much larger than the main filter and often residing on slow storage, to facilitate adaptation.

However, existing adaptive filters are not practical and have seen no adoption in real-world systems due to two main reasons. Firstly, they offer weak adaptivity guarantees, meaning that fixing a new false positive can cause a previously fixed false positive to come back. Secondly, the sub-optimal design of the auxiliary structure results in adaptivity overheads so substantial that they can actually diminish the overall system performance compared to a traditional filter.

In this paper, we design and implement , the first practical adaptive filter with minimal adaptivity overhead and strong adaptivity guarantees, which means that the performance and false-positive guarantees continue to hold even for adversarial workloads. The is based on the state-of-the-art quotient filter design and preserves all the critical features of the quotient filter such as cache efficiency and mergeability. Furthermore, we employ a new auxiliary structure design which results in considerably low adaptivity overhead and makes the practical in real systems.

We evaluate the by using it to filter queries to an on-disk B-tree database and find no negative impact on insert or query performance compared to traditional filters. Against adversarial workloads, the preserves system performance, whereas traditional filters incur $2\times$ slowdown from adversaries representing as low as $1\%$ of the workload. Finally, we show that on skewed query workloads, the can reduce the false-positive rate $100\times$ using negligible (1/1000th of a bit per item) space overhead.

legend entry/.initial=,
every axis plot post/.code=
/pgfplots/legend entry/pgfplots/forget plot

AQFStyle/.style         = legend entry = AQF, color = cyan!50!blue,   fill = cyan!50!blue,
TQFStyle/.style         = legend entry = TQF, color = cyan,           fill = cyan,
ACFStyle/.style         = legend entry = ACF, color = violet!40!blue, fill = violet!40!blue,
QFStyle/.style          = legend entry = QF,  color = green!80!black, fill = green!80!black,
CFStyle/.style          = legend entry = CF,  color = orange,         fill = orange,
SSStyle/.style          = legend entry = SS,  color = purple,         fill = purple,
CBFStyle/.style         = legend entry = CBF, color = black,         fill = black,

LineStyle/.style        =  fill=none, mark repeat = 2 ,
AQFLineStyle/.style     = AQFStyle, mark = oplus*, LineStyle,
TQFLineStyle/.style     = TQFStyle, mark = square*, LineStyle,
ACFLineStyle/.style     = ACFStyle, mark = Mercedes star, LineStyle,
QFLineStyle/.style      = QFStyle,  mark = triangle*, LineStyle,
CFLineStyle/.style      = CFStyle,  mark = diamond*, LineStyle,
SSLineStyle/.style      = SSStyle,  mark = pentagon*, LineStyle,
CBFLineStyle/.style     = CBFStyle,  mark = diamond*, LineStyle,

AQFBarStyle/.style      = AQFStyle,
TQFBarStyle/.style      = TQFStyle,
ACFBarStyle/.style      = ACFStyle,
QFBarStyle/.style       = QFStyle,
CFBarStyle/.style       = CFStyle,
SSBarStyle/.style       = SSStyle,
CBFBarStyle/.style      = CBFStyle,

ThroughputBarGraph/.style =
width = + 27pt,
height = 115pt,
bar width = 9pt,
xtick = ,
ymin = 0,
error bars/error bar style = color = black,
error bars/y dir = both,
error bars/y explicit,
scaled y ticks = base 10:-6,
ytick scale label code/.code=,
yticklabel =  M ,
y tick label style = rotate = 90,
legend to name=insert-throughput-legend,
legend columns = -1,
ThroughputTable/.style =
table/x = dummy,
table/y = median,
table/y error plus expr = max - median,
table/y error minus expr = median - min,
SpaceTable/.style =
table/x = dummy,
table/y = space,

WorkloadGraph/.style =
width = + 15pt,
height = 110pt,
ticks = major,
try min ticks = 3,
xlabel = Queries,
enlarge x limits = false,
scaled x ticks = base 10:-6,
xtick scale label code/.code=,
xticklabel =  M ,
y tick label style = rotate = 90,
y label style = at = (axis description cs:0.26,0.5), anchor=south,
scaled y ticks = false,
x label style = at = (axis description cs:0.5,0.1), anchor=north,
xmin = 0,
legend columns = -1,
legend to name = trash
WorkloadTableFP/.style =
table/x = queries,
table/y = fprate,
WorkloadTableSpace/.style =
table/x = queries,
table/y = space,
HashAccessesTable/.style =
table/x = queries,
table/y = accesses,

ChurnGraph/.style =
width = + 18pt,
height = 1.55in,
ticks = major,
try min ticks = 3,
xlabel = Queries,
enlarge x limits = false,
scaled x ticks = base 10:-6,
xtick scale label code/.code=,
xticklabel =  M ,
y tick label style = rotate = 90,
y label style = at = (axis description cs:0.26,0.5), anchor=south,
x label style = at = (axis description cs:0.5,0.1), anchor=north,
ymin = 0,
scaled y ticks = false,
legend columns = -1,
legend to name = trash
WorkloadTableFP/.style =
table/x = queries,
table/y = fprate,

BlacklistGraph/.style =
width = + 13pt,
height = 1.55in,
ticks = major,
try min ticks = 3,
xlabel = list/list Ratio,
enlarge x limits = false,
scaled x ticks = base 10:-6,
xtick scale label code/.code=,
xticklabel =   ,
scaled y ticks = false,
y label style = at = (axis description cs:0.26,0.5), anchor=south,
x label style = at = (axis description cs:0.5,0.1), anchor=north,
legend columns = -1,
legend to name = blacklist-legend,
BlacklistTableFP/.style =
table/x expr = ratio / (1 - ratio),
table/y = fprate,
BlacklistTableSpace/.style =
table/x expr = ratio / (1 - ratio),
table/y expr = space + 200,

DiskInsertGraph/.style =
width = + 13pt,
height = 1.55in,
ticks = major,
try min ticks = 3,
xlabel = load factor,
enlarge x limits = false,
xtick scale label code/.code=,
xticklabel =   ,
scaled y ticks = false,
y label style = at = (axis description cs:0.26,0.5), anchor=south,
x label style = at = (axis description cs:0.5,0.1), anchor=north,
legend columns = -1,
legend to name = disk-insert-legend,
DiskInsertTableInserts/.style =
table/x = fill,
table/y = through,
DiskInsertTableQueries/.style =
table/x = queries,
table/y = through,
DiskInsertTableFPRates/.style =
table/x = queries,
table/y = fprate,
DiskInsertTableMapAccesses/.style =
table/x = fill,
table/y = accesses,

DiskQueryGraph/.style =
width = + 13pt,
height = 1.55in,
ticks = major,
try min ticks = 3,
xlabel = throughput (millions of ops/sec),
enlarge x limits = false,
scaled x ticks = base 10:-6,
xtick scale label code/.code=,
xticklabel =   ,
scaled y ticks = false,
y label style = at = (axis description cs:0.26,0.5), anchor=south,
x label style = at = (axis description cs:0.5,0.1), anchor=north,
legend columns = -1,
legend to name = disk-query-legend,
DiskQueryTableHistogram/.style =
table/x = fill,
table/y = through,

DiskAdversarialGraph/.style =
width = + 13pt,
height = 1.55in,
ticks = major,
try min ticks = 3,
xlabel = adversarial,
ylabel = throughput,
enlarge x limits = false,
xtick scale label code/.code=,
scaled x ticks = base 10:2,
xticklabel =   ,
scaled y ticks = false,
y label style = at = (axis description cs:0.26,0.5), anchor=south,
x label style = at = (axis description cs:0.5,0.1), anchor=north,
legend columns = -1,
legend to name = disk-adversarial-legend,
AdversarialQueries/.style =
table/x = freq,
table/y = through,

HighLoadThroughputGraph/.style =
width = + 27pt,
height = 115pt,
bar width = 9pt,
xtick = ,
ymin = 0,
error bars/error bar style = color = black,
error bars/y dir = both,
error bars/y explicit,
ytick scale label code/.code=,
y tick label style = rotate = 90,

HighLoadTable/.style =
table/x = dummy,
table/y = through,

§ INTRODUCTION

Filters <cit.> are a go-to data structure in systems builders' toolkits. Filters maintain a compact representation of a set of items, saving space by allowing a small false-positive rate $\epsilon$:  a membership query to a filter for set $S$ returns for any $x\in S$ and returns with probability at least $1-\epsilon$ for any $x\not\in S$.

Filters are powerful because allowing false-positives dramatically reduces the space required to store $S$. For example, if we are required to answer queries on $S$ with no errors, then the size of a data structure is at least $\log {u \choose n}= \Omega(n \log (u/n))$ bits, where $u$ is the size of the universe <cit.>. In contrast, modern filters have size $n\log(1/\varepsilon) + cn$, where $c$ is between 2 and 3 <cit.>.  This means that, for typical false-positive rates around 1% to 0.1%, a filter can store one or two bytes of information per item, no matter how large the universe.  This bound is tight up to lower-order terms in that any filter requires at least $n\log(1/\varepsilon)$ bits <cit.>.

Filters have been extensively used to compactly summarize a set of items in networks, storage systems, machine learning, computational biology, and other areas <cit.>.

Types of problems
The following problem settings offer challenges for traditional filters and opportunities for improvement:

* Static lists.  Given a set $Y$ of items and a set $N$ of items chosen from a universe $U$, build a data structure that answers to any query for an item in $Y$, for any query for an item in $N$, and answers with probability at least $1-\epsilon$ for any other item in $U$.

* Dynamic lists. This is similar to the static list problem, except that the sets $Y$ and $N$ may be updated dynamically.

* Skewed query distributions. In some settings, the frequency distribution of queries may be highly skewed.
In such settings, the observed false-positive rate of the filter can be very far from the expected rate, $\epsilon$.
For example, if all the queries are for a single item, the observed false-positive rate will be 0 or 1, but not in between.

Avoiding repeated mistakes can reduce the false-positive rate of a filter, or equivalently, reduce the filter size needed to achieve some target error rate.  In summary, filters that ignore the skew may perform arbitrarily poorly, whereas filters that exploit the skew can outperform the lower bounds.

* Adversarial queries.  In this problem, the goal is to design a filter that  guarantees that the fraction of queries from an adversary that are false positives is at most $\epsilon$, even when the queries are chosen by an adversary that is trying to cause the filter to return as many false positives as possible.  Here we assume the attacker can detect when a query results in a false positive and can repeat queries arbitrarily.  This is a more general case of the skewed-query distribution.

Prior work
Prior work has considered each of these problems separately, and consequently has developed distinct approaches to solving each of them.  Chazelle et al. <cit.> describe Bloomier filters, which encode static lists.  Bloomier filters also support a limited form of dynamicity—they support moving items between $Y$ and $N$ but not adding or deleting items.
Tripunitara and Carbunar <cit.> introduce cascading Bloom filters to solve the static list problem, and these are used in many  systems <cit.>. Reviriego et al. <cit.> proposed an extension of the static xor filter to support the static list problem.  Li et al. <cit.> proposed the seesaw counting filter for the dynamic list problem, specifically in the context of detecting malicious URLs.
Mitzenmacher et al. <cit.> proposed adaptive cuckoo filters to solve the skewed-query-distribution problem.
Bender et al. <cit.> define the notion of an adaptive filter, which offers strong guarantees on the number of false positives that an application will see, even with a skewed or even adversarial query distribution, and present the broom filter, which meets their definition.  Bender et al. <cit.> analyzed the performance of broom filters <cit.> on queries that obey Zipfian distributions. Lee et al. <cit.> proposed telescoping filters to address the skewed query distribution problem.

This paper We argue that all of these problems can be naturally solved, with comparable space and better performance than the prior special-purpose solutions, by what we call a monotonically adaptive filter, which is a filter that never forgets a false positive.  Furthermore, we show how to build fully dynamic monotonically adaptive filters from quotient filters <cit.>.  We design, build, and evaluate a fully dynamic monotonically adaptive filter, the , and show that it outperforms several prior solutions to these problems. Finally, we prove lower bounds on the space required to solve the list problem, showing that the is space-optimal.

Like adaptive filters, monotonically adaptive filters can adapt, i.e. they can update their state to correct false positives. Bender defined what it means for a filter to be adaptive: every query has a probability of at most $\epsilon$ of returning a false positive, independent of the outcome of all prior queries <cit.>.  Adaptivity is a very strong property: it guarantees that after $n$ queries—even adversarially generated queries—the upper bound on the number of false positives is tightly concentrated around $\epsilon n$. Specifically, the system will see at most $\epsilon n + O\big(\sqrt{ \epsilon n\log n}+\log n\big)$ false positives with high probability.

Adaptive filters require two things: feedback about their false positives and auxiliary data to correct them.  For example, if an adaptive filter is used by an application to avoid database lookups for non-existent items, then the application can inform the filter that a query for an item $x$ was a false positive if the subsequent database query returned that $x$ is not present in the database.  Adaptive filters also need an auxiliary structure to store information to support adaptation.  Bender showed that this auxiliary information is necessary and in fact must be quite large: the total size of an adaptive filter on a set $S$ essentially must be large enough to store $S$ <cit.>.
The trick is to break the filter into two parts, a small in-memory component that is accessed on every query and a large auxiliary structure that is accessed only during adaptations and hence can reside in slower storage.  Note that all proposed adaptive filters have this overall structure.  In some applications, such as when the filter is in front of a database, the database may be able to serve as the auxiliary structure, so that the total storage requirements of the system remain essentially unchanged. See Bender for more discussion <cit.>.

What makes monotonically adaptive filters special is that, when they adapt, their false-positive set only shrinks. Prior proposed adaptive filters were not monotonic: fixing one false positive could cause other elements to become false positives. Even filters that meet Bender 's strong definition of adaptivity need not be monotonic. For example, Bender 's broom filter periodically rotates its hash function, at which point it forgets all the false positives it corrected under the old hash function.

Fingerprint filters, such as the quotient filter <cit.>, are good candidates for building practical monotonically adaptive filters because they store a set $S$ by compactly storing the set $h(S)=\{h(x) \mid x\in S\}$, where $h$ is a hash function and $h(x)$ is called the fingerprint of $x$.  A query for $y$ simply checks whether $h(y)\in h(S)$, so the only source of false positives is fingerprint collisions. Fingerprint filters support a false-positive rate of $\epsilon$ on a set of size $n$ by using $\log (n/\epsilon)$-bit fingerprints and typically store the first $\log n$ bits of each fingerprint implicitly so that the per-item space is $\log (1/\epsilon) + O(1)$ bits. To make a fingerprint filter monotonically adaptive, we need only to be able to eliminate fingerprint collisions. To do so, we can use a hash function $h$ that outputs a large number of bits and initially store the first $\log (n / \epsilon)$ bits of $h(x)$ for each $x\in S$, where $n=|S|$. Whenever we discover a false positive, i.e. a query $y$ whose fingerprint matches a fingerprint for some $x\in S$, we modify the filter to store a longer fingerprint for $x$ until the collision disappears. In fact, Kopelowitz et al. <cit.> show that this approach is not only natural but necessary: a space-efficient fingerprint filter must have variable-length fingerprints to be adaptive.

We implement a prototype fully dynamic monotonically adaptive filter, the , that uses only $(1 + o(1))n\log(1/\epsilon) + O(n)$ space. We demonstrate experimentally that it outperforms existing purpose-built solutions for skew distribution and list workloads in terms of space efficiency, insertion speed, and query speed. We also show a space lower bound for the static list problem and that the meets the space lower bound up to low-order terms.

The challenge is to store and update these variable-length fingerprints efficiently in terms of space and time.

Prior theoretical proposals for building adaptive filter have had complex mechanisms for managing variable-sized fingerprints <cit.>.  We propose a simple scheme for implementing variable-sized fingerprints within .  Even though adapting requires extending a fingerprint by only two bits in expectation <cit.>, simplifies fingerprint management by over-adapting, i.e. fingerprints grow by multiples of $\log (1/\epsilon)$ bits.  Over-adaptation could cause the filter to use too much space and over-minimize the false-positive probability below $\epsilon$.
However, in practice, this is not an issue.

Our results We evaluated the in isolation and as a component of larger systems.  The high-level summary of our findings is that the can speed up query throughput by delivering far fewer false positives than non-adaptive filters. We compared the performance of the to that of two other adaptive filters, the telescoping quotient filter (TQF) <cit.> and the adaptive cuckoo filter (ACF) <cit.>. We also compared it to two non-adaptive filters, the quotient filter (QF) <cit.> and the cuckoo filter (CF) <cit.>.

* In a disk-based database, is between 10$\times$ — 30$\times$ faster than other adaptive filters (TQF, ACF) for overall insertion performance and is comparable to non-adaptive filters.

* In a disk-based database, achieves between 15% — 6$\times$ faster overall query performance than non-adaptive filters (QF, CF) for adversarial queries and has comparable performance for uniform-random query workloads.

* is dynamic (i.e. support deletes and resizability) but still achieves similar or better space usage compared to purpose-built solutions for the static list problem.

* has negligible adaptivity overhead compared to the quotient filter on which is based.

* preserves all the critical features of the quotient filter such as mergeability, resizeability, and bulk insertions.

In summary, the adaptivity overhead is minimal in compared to non-adaptive filters. It is able to substantially improve overall system performance in scenarios where disk accesses incur a large cost. Furthermore, it matches or beats the performance of custom-built solutions for static list problems.

§ FILTERS AND APPLICATIONS

In this section, we give an overview of general-purpose filters and adaptive filters. We then describe applications that can benefit from adaptive filters and review existing purpose-built filters for these applications. We divide these applications in two broad categories:

* Applications that use traditional filters but have skewed workload patterns where adaptive filters can help.

* Applications that currently use purpose-built solutions where the cost of certain false positives is very high.

§.§ General-purpose filters

For decades, the Bloom filter <cit.> was essentially the only available filter, but Bloom filters are suboptimal in terms of space usage, running time, and data locality, and they support a bare-bones set of operations (insert and lookup).   The Bloom filter has inspired numerous variants <cit.>. The counting Bloom filter (CBF) <cit.> supports deletes at the cost of space.

The blocked Bloom filter <cit.> provides better cache locality than the standard Bloom filter but it comes at a higher false-positive rate.

The quotient filter (QF) <cit.> is a fingerprint filter. It stores fingerprints using Robin Hood hashing <cit.>.
It divides the fingerprint into two parts, higher order $\log(n)$-bits as the quotient and lower order $\log(1/\epsilon)$-bits as the remainder. The quotient bits are used to locate a slot in the table, and the remainder bits are stored in that slot.
It supports insertion, deletion, lookups, enumeration, resizing, and merging. The counting quotient filter (CQF) <cit.>, improves upon the performance of the quotient filter and adds variable-sized counters to count items using asymptotically optimal space, even in large and skewed datasets.

The cuckoo filter <cit.> also stores fingerprints but uses cuckoo hashing instead of Robin Hood hashing. The Morton filter <cit.> is a variant of the cuckoo filter that is designed to speed up insertion using optimizations designed for hierarchical-memory systems.

§.§ Strongly adaptive filters

A strongly adaptive filter modifies its state so that if a false positive is repeated, the probability that it is still a false positive is at most $\epsilon$.

Bender et al. <cit.> introduce the broom filter and the notion of strong adaptivity used in this paper.
The broom filter is based on the quotient filter, but supports variable-length fingerprints to adapt to (and correct) false positives.

Lee et al. <cit.> introduce the telescoping filter, which is also built using the quotient filter <cit.>. The telescoping filter is strongly adaptive but avoids directly extending fingerprints. They change the remainder (or the tag) stored in the filter by using a different lower-order $\log(1/\epsilon)$-bits. Additionally, they maintain a table to record which $\log(1/\epsilon)$-bits they have used as a remainder in the filter for the adapted items. As the filter adapts, the size of this table grows (so in this sense their fingerprints are variable-length and strong adaptivity is possible). The adaptive cuckoo filter of Mitzenmacher et al. <cit.> is adaptive in the sense that it changes its representation in response to false positives, but is not strongly adaptive. See Section <ref>.

§.§ Filters for skewed query distributions

A common and important application of filters is their use in key-value stores based on Log-Structured Merge Trees (LSMs) and $B^\varepsilon$-trees <cit.>. In these key-value stores, filters are used to avoid performing multiple expensive disk accesses per query <cit.>. In some database systems, this type of key-value store is used as the storage engine <cit.>.

In an LSM tree, data is stored in SSTables, which are static, sorted arrays of key-value pairs. The SSTables are organized into levels L0, L1, …, where L0 is the smallest and holds the most recently written data. Each subsequent level is larger by a factor of $g$, where $g$ is a configuration parameter. As data is written, SSTables are moved down the structure and are merged into each other according to a chosen compaction policy. In general, at any point in time, a given key can be present in an SSTable on any level (even multiple SSTables per level in some variants), so queries need to check at least one SSTable on each level, which is expensive.
As a result, in almost all practical systems, each SSTable has a corresponding filter so that queries only read data from the SSTable when the key is present there or due to rare false positives from the filter.  Note that in this application, queries to SSTables on smaller levels are often negative since most of the data is stored in the larger levels. However, the smaller levels may contain recent updates, so they cannot be skipped. Thus, filters in the smaller levels see frequent negative queries <cit.>.

One challenge to applying adaptive filters to LSMs is that the SSTables are typically static and most LSM trees store their filters in their SSTables. However, this is not necessary or universal.  For example, SplinterDB stores its filters separately from the data they cover <cit.>.  An LSM could even store adaptive versions of its filters only in memory.  The adaptivity information would be lost on a crash, meaning that false positives might increase after a crash, but this should be rare enough to be insignificant.

Query workloads to database systems commonly follow a power-law or otherwise skewed distribution <cit.>.  As a result, state-of-the-art benchmark suites YCSB, TPC-C, and TPC-E incorporate data skew into most of their workloads <cit.>. In fact, many systems have tried to mitigate or even exploit the effects of data skew <cit.>.

A skewed database query workload also results in a skewed workload for filters. Moreover, as noted above, many of the queries will be negative. Adaptive filters, such as , can outperform non-adaptive filters on skewed workloads by eliminating repeated false positives on frequently accessed keys.

§.§ Filters for list problems

Detecting Malicious URLs
Malicious websites pose a major threat to internet users. For example, merely visiting a malicious URL may cause a user's web browser to be hijacked <cit.>.

Since URLs are long <cit.> and abundant <cit.>, an effective way for a router to block malicious URLs is to store them as the list of a filter <cit.>.

However, it is important not to block legitimate URls that are false positives <cit.>, so every positive response of the malicious-URL filter must be verified <cit.>, which is expensive.
This additional overhead imposed on false positive (safe) URLs is especially undesirable when the URL is important. For instance, a false positive may block access to a voter registration webpage, or emergency weather information, whereas slowing the loading of other false-positive pages is relatively benign.

One way to address this variability in false positive cost is to store important false positives in a list, so that they are never blocked and so they do not pay the URL-verification penalty.   Chazellete et al. <cit.> introduced the Bloomier filter which solves the list problem. Li et al., <cit.> present the Seesaw Counting Filter (SSCF), which implements a list filter specifically for the malicious URL blocking problem.
Reviriego et al. <cit.> present the Integrated Filter which also implements a list. Both focus on the case where the list is static and known ahead of time.
The SSCF has an extension for adding list items dynamically, but it is not guaranteed to prevent false positives by doing so and can also introduce false negatives.

URL requests may also vary in frequency, and these frequencies may even change over time. However, the existing filters literature on this problem does not consider this generalization. For this work we restrict our focus to the standard assumption that a static set of high-priority elements must never be false positives.

Certificate Revocation Lists
In the TLS PKI (Transport Layer Security Public Key Infrastructure <cit.>), browsers should check whether a certificate has been revoked before trusting connections authenticated by the certificate.  Traditionally this was done via a “pull” approach, i.e., browsers would check with a central repository of revoked certificates when they established a connection.  More recent work has sought to move to a “push” model, where browsers receive frequent updates to the list of revoked certificates, so the browser can perform a purely local check when it establishes a new connection.

Larisch, et al., <cit.> proposed CRLite, which uses cascading Bloom filters to store the set of revoked certificates at the client. They observed that, in the case of TLS certificates, the universe is a small finite set and known at construction time. They can build a cascade of Bloom filters to exactly represent the set of revoked certificates. In the cascading Bloom filter, each subsequent Bloom filter contains false positive set from the earlier Bloom filter until the false positive set is small enough to be stored exactly in a hash table. A central system would periodically push updates to this list to browsers.  The updates are encoded as bitwise deltas on the original filters.  When the space of certificates grows too large, so that they need to resize the filters, then they have to transmit new filters from scratch.

De Bruijn graph traversal  In computational biology, de Bruijn graphs (DBGs) are at the heart of numerous genomic sequence analysis pipelines <cit.>. In a de Bruijn graph, each node is a $k$-length subsequence (of the DNA bases, “A”, “C”, “G”, and “T”) from the underlying biological samples, and two nodes are connected via an edge if they share a $(k-1)$-length subsequence.  Analyses traverse DBGs during assembly, error correction, “contig” detection, and numerous other applications.

De Bruijn graphs are often large enough that they do not fit in the memory.  Numerous methods have been proposed to exploit their special structure for compression.  One of the main tricks is to take advantage of the fact that each node has at most 4 incoming edges and 4 outgoing edges (one for each base that can be prepended or appended to the node).  Thus a traversal can query for the existence of each edge, so we can represent the DBG using an (approximate) set data structure that supports only membership queries, i.e. a filter.  In this application, false positives in the filter result in extra edges in the graph.

To avoid the false edges, Chikhi and Rizk <cit.> proposed to store the de Bruijn graph in a cascading Bloom filter as the set of queries is known in advance. Each Bloom filter stores the false positives from querying the earlier Bloom filter using all possible queries during the dbg traversal.

§.§ Attacking adaptive filters

An adversary who is able to issue queries to a Bloom filter, and detect when the filter returns a false positive, can eventually force the filter to give false positives on nearly every query. It simply issues queries until it observes a false positive and then repeats the query that induced the false positive. Such an attack works on any filter that does not change its representation in response to false positives. Since adaptive filters do change their representations in response to false positives, some of them are more robust to attacks by adversaries.

Reviriego  <cit.> demonstrate that an adversary who is able to issue queries to an adaptive cuckoo filter, and detect when the filter returns a false positive, can eventually force the filter to give false positives on nearly every query. The attack exploits the property that adaptive cuckoo filters will revert to the initial fingerprint for some element in the represented set after a certain number of adaptations. After finding an adaptation loop, a sequence of queries that when queried in order force the filter to 1) yield multiple false positives and 2) revert to its initial state at the end of the loop, the adversary is able to replay this adaptation loop indefinitely, forcing the filter to return many false positives. The attack succeeds even when the adversary does not have exclusive query access to the filter (that is, other processes/users may query the filter at any time), though the time to complete an attack increases in this case.

Further, Kopelowitz  <cit.> show that any variant of the adaptive cuckoo filter, or indeed any space-efficient filter with fixed-length fingerprints, can be forced by such an adversary to suffer a high proportion of false positives.

Filters that are adaptive according to Bender 's definition <cit.>, such as the broom filter and the telescoping adaptive filter <cit.>, are provably robust against this type of adversary because they guarantee a false-positive rate of $\epsilon$ for any sequence of queries, even those generated by an adversary.

§ RELATED WORK

§.§ Filters

For decades, the Bloom filter <cit.> was essentially the only game in town, but
Bloom filters are suboptimal in terms of space usage, running time, and data locality, and they support a bare-bones set of operations (insert and lookup).

In particular,
Bloom filters consume $\log(e)\, \opt$ space, which is roughly $\log(e)\approx
1.44$ times more than the lower bound of $\opt + \Omega(n)$
bits <cit.>.

Bloom filters also incur $\errbits$ cache-line misses on inserts and positive queries, giving them poor insertion and query performance.

The Bloom filter has inspired numerous variants <cit.>.
The counting Bloom filter (CBF) <cit.> replaces each bit in the Bloom
filter with a $c$-bit saturating counter.  This enables the CBF to support
deletes, but increases the space by a factor of $c$.

The blocked Bloom
filter <cit.> provides better cache locality than the standard Bloom
filter but does not support deletion.

The quotient filter (QF) <cit.> uses a new,
non-Bloom-filter design. It is built on the idea of storing small
fingerprints via Robin Hood hashing <cit.>. It supports insertion, deletion, lookups, resizing, and
merging. The counting quotient filter (CQF) <cit.>, improves upon
the performance of the quotient filter and adds variable-sized counters to count items using
asymptotically optimal space, even in large and skewed datasets.

The cuckoo filter <cit.> uses the idea from quotient filters of hashing small
fingerprints but uses cuckoo hashing instead of Robin Hood hashing. The Morton filter <cit.> is a variant of the cuckoo filter that is
designed to speed up insertion using optimizations designed for hierarchical

§.§ Filters for Blocklists/Requirelists
Chazellete et. al. introduced the Bloomier filter <cit.> which was designed to not only guarantee a small false-positive probability but to ensure that a requirelist, a pre-specified list of negative elements, would never be false positives.

Li et. al., present the Seesaw Counting Filter <cit.> (SSCF), which implements a blocklist/requirelist filter specifically for the URL blocklist problem. The SSCF has an extension for adding requirelist items dynamically, but in order to prevent from introducing false negatives into the filter, it must wait to modify the requirelist until associated buckets have been completely vacated. As a result, adaptations are neither immediate nor guaranteed, and the possibility for dynamic adaptation of the requirelist can only exist in situations with enough volatility to ensure that any given bucket will be completely emptied after a reasonable amount of time. Because our experiments were conducted with large load factors, the SSCF could not be reliably expected to adapt. Moreover, the requirelist becomes less effective as it fills up more of the filter, so the filter would need some way to decide which false positives to adapt to and which to ignore, and it would eventually need to stop making adaptations altogether. As a result, the adaptivity of the SSCF does not apply to the same circumstances as the AQF, so it is excluded from the evaluation.

Reviriego et. al. <cit.> present the Integrated Filter which also implements a requirelist. All focus on the case where the requirelist is static and known ahead of time.

§.§ Adaptive filters

Adaptive filters are advanced filters that can update their internal representation when informed of a false positive. Adaptive filters also need a way to map the fingerprints stored in the filter to original keys to safely adapt to avoid future false positive keys. Adaptive filters are typically used as a small in-RAM summary the contents of a set in external storage. When the system issues a query $x$ to the external set, if the filter says $x$ is not in the external set the system can skip the unnecessary I/O to access the external set. A false positive means the system will perform an I/O to access the external set and subsequently discover the false positive item is not present.

Mitzenmacher et. al. <cit.> proposed the adaptive cucko filter (ACF) <cit.>, an adaptive filter based on the cuckoo filter. It is specifically designed to reduce false-positive rate on skew query distributions. Kopelowitz et. al. <cit.> propose an improved version of the ACF and also show that any strongly adaptive filter must use variable-length fingerprints. As a result all existing variants of the ACF are not strongly adaptive. While the ACF is not strongly adaptive, they show that it is support optimal: it guarantees a false-positive rate of at most $\epsilon$ for any fixed query sequence.

Bender et. al. <cit.> introduce the broom filter and the notion of strong adaptivity described in this paper. The broom filter is a quotient filter that adapts by extending the fingerprints of elements that cause false positives. Lee et. al. <cit.> introduce the telescoping filter, which is also built using the quotient filter <cit.>. The telescoping filter is strongly adaptive but avoids directly extending fingerprints. They change the remainder (or the tag) stored in the filter by using a different lower-order $r$-bits. Additionally, they maintain a table to record which $r$-bits they have used as a remainder in the filter for the adapted items. As the filter adapts, the size of this table grows (so in this sense their fingerprints are variable-length and strong adaptivity is possible).

§ DESIGN

In this section, we describe the high-level scheme of our solution, without worrying about how to encode this design in a small number of bits.  The encoding is described in subsequent sections.

The quotient filter <cit.> structure. The upper part shows the logical structure. The lower part shows the encoding of the logical structure in the quotient filter.
It uses two metadata bits per slot. All items that share the same canonical location are stored together in a run. A sequence of items without any empty slot is called a cluster. Note: the items are showed in upper case in the canonical representation and the remainders corresponding to the items in the slots are showed in lower case.

§.§ High-level design

The builds on the idea of fingerprint filters, which store a set $S$ by storing the set of fingerprints $h(S)=\left\{h(x)\mid x\in S\right\}$.  The basic idea behind the is that, initially, we store only enough bits of each fingerprint to ensure a false positive rate of $\epsilon$, i.e. we store a set $F$ of fingerprints, where each fingerprint is actually a prefix of $h(x)$, for some $x\in S$.   A query for $y$ returns if some fingerprint in $F$ is a prefix of $h(y)$.
When we discover a false positive, i.e., an item $y\not\in S$ such that some fingerprint $f\in F$ is a prefix of $h(y)$, we increase the length of $f$ until it is no longer a prefix of $h(y)$.

The main issue that arises is: how can we extend a fingerprint $f$ in our filter without knowing the full hash $h(x)$ of which it is a prefix?  To solve this problem, all adaptive filters maintain a reverse map that maps fingerprints in $F$ back to their full hashes (or even the original keys).  Notably, the need to store full hashes means this map will be much larger than the filter, possibly too large to fit in fast storage. Thus, we would like to minimize how often this reverse map needs to be updated and/or queried.

At the very minimum, one insert needs to be done to the reverse map for each insert to the filter. In addition, one reverse map query needs to be made for each adaptation. However, since adaptations are responses to false positives, a disk access is done at this point anyway, and adapting ensures that the offending query will not cause another disk access in the future. Thus, the maintains its fast performance on general queries. Ideally, we would access the reverse map at no other time.

In the following sections, we describe how we store and update variable-length fingerprints efficiently and how we maintain the reverse map will little overhead.

§.§ Quotient filter

We build the using the  <cit.>. The has the ability to associate small variable-length values with fingerprints. We exploit this feature to extend the fingerprint size to adapt. Using the as the underlying filter helps retain advantages, such as good cache-locality, deletion, resizability, enumerability, mergeability, etc., that the has over other filters. In this section, we give an overview of Pandey et al.'s  <cit.>. Later in <Ref>, we explain how we modify the schema to build the .

The quotient filter (QF) stores an approximation of a multiset $S\subseteq \mathcal{U}$ by maintaining a compact, lossless representation of the multiset $h(S)$, where $h:\mathcal{U}\rightarrow\{0,\ldots,2^p-1\}$ is a hash function that maps items from the universe $\mathcal{U}$ to a $p$-bit fingerprint. To handle a multiset of up to $n$ distinct items while maintaining a false-positive rate of at most $\epsilon$, the QF sets $p=\log_2 \frac{n}{\epsilon}$ (see <cit.>  for the analysis).

The uses Robin-Hood hashing <cit.> to store the fingerprints compactly in a table. It consists of an array $Q$ of $2^q$ slots and a hash function $h$ mapping items from a multiset to $p$-bit integers, where $p \geq q$.

Robin-Hood hashing is a variant of linear probing in which we try to place an item $a$ in slot $h(a) / 2^{p-q}$, but shift items down when there are collisions to create empty space. Robin-Hood hashing maintains the invariant that, if $h(a) < h(a')$, then $a$ will be stored in an earlier slot than $a'$.

The divides $h(x)$ into its first $q$ bits, quotient $h_0(x)$, and its remaining $r$ bits, remainder $h_1(x)$.  Together, the quotient and remainder form the fingerprint of $x$.  The maintains an array $Q$ of $2^q$ $r$-bit slots, each of which can hold a single remainder.  When an element $x$ is inserted, the attempts to store the remainder $h_1(x)$ at index $h_0(x)$ in $Q$
(which we call $x$'s canonical slot).  If that slot is already in
use, then the uses Robin hood hashing to find the next available empty slot to store $h_1(x)$. All the items that share the same canonical slot are stored together in a run and a sequence of runs stored contiguously with no empty space is called a cluster. During an insert operation, the next available empty slot is found at the end of the cluster. If an item lands at the start of the cluster then all the items in cluster must be shifted to create an empty space (see <Ref>).

The also maintains 2 bits of additional metadata (is_occupied and is_runend) per slot in order to determine which slots are in use and the canonical slot of each remainder stored in $Q$. When an item is inserted into the canonical slot, the is_occupied bit for that slot is set to 1. The is_runend bit is set to one for every slot that contains the last remainder in a run.
Please refer to Pandey et al. <cit.> for further details.

The further maintains an extra 8 bits per block of 64 slots (called offset) to more quickly determine the start and end of each run during insertions and queries. Therefore, the total overhead due to metadata in a is 2.125 bits per slot. In order to maintain good performance, the array of slots cannot be filled beyond $95\%$.

To quickly determine the start and end of a run, the uses $RANK$ and $SELECT$[For a given slot $i$, $RANK(i)$ returns the number of 1s in a bit vector $B$ up to $i$. $SELECT(i)$ performs the inverse operation, returning the index of the $i$th 1 in $B$.] operations <cit.>. If the is_occupied bit is set to 0 for a canonical slot, then there is no item with that canonical slot in the table. If the is_occupied bit is set to 1, then we can use the $RANK$ operation to determine the number of runs starting before this canonical slot and then perform the $SELECT$ operation to determine the end of the run, as there is a one-to-one correspondence between the is_occupied and is_runend bit for each run.

§ IMPLEMENTATION

The AQF uses the same fundamental structure as the QF. Here we describe how we modify the QF schema to support adaptivity.

§.§ False positives

First, let us understand how false positive queries occur in the QF. The QF stores the fingerprints compactly and exactly in the table. Therefore, a false positive occurs due to a hash collision while computing the fingerprint. That is, there exist two distinct items ($x$ and $y$) that share the same fingerprint. If $x \in S$ but $y \not\in S$, then a query for $y$ will result in a false positive.

A QF guarantees a false-positive rate [The false-positive rate is defined as the ratio of the number of false positives reported over the total number of queries in the set.] of $\epsilon = 2^{-r}$, where $r$ is the number of remainder bits, for a set of items drawn uniformly at random from the universe $\mathcal{U}$.

However, if the items are drawn from some arbitrary distribution then there is no guarantee on the false positive rate. For example, if a query set consists of a single item that happens to be a false positive, then the false positive rate of the filter for that set will be 1.

§.§ Adapting to false positives

The updates its representation on every false positive query. These updates ensure that the false-positive probability for any query $x$ remains $\leq \epsilon$, even if $x$ was a false positive the last time that it was queried.

updates its representation by using an additional slot for the false positive item, extending its fingerprint by the next $r$ bits in its hash, known as an extension. Multiple extensions can be added if the resulting fingerprint still produces a false positive on the given query, with the probability that the fingerprint incurs a false positive decreasing by a factor of $2^{-r}$ with each extension. The fingerprint of an item in the now refers to its quotient, remainder, and any extensions that have been added to it in the filter.

We introduce an additional overhead bit, the is_extension bit, to differentiate between slots storing remainders and extensions, bringing the total overhead to 3.125 bits per slot. Recall that the QF has an overhead of 2.125 bits per item. Slots with an unmarked is_extension bit are treated as usual. A marked is_extension bit indicates that the slot contains an extension of the previous remainder.

Lists in the reverse map
To extend a fingerprint, we need to obtain the original key mapped to the current fingerprint in the filter. To do this, we maintain an on-disk hash table that functions as a reverse map from fingerprints to the keys. We extend the fingerprint for the mapped key by adding additional bits derived from the original hash of the key. Recall that the reverse map is not specific to the and is needed by any adaptive filter to retrieve additional information necessary for adaptation.

However, because the adapts by appending to fingerprints rather than reshuffling them as done in the telescoping filter <cit.> and the adaptive cuckoo filter <cit.>, the existing bits of the fingerprint prior to adaptation stay the same. Most notably, the quotient and remainder, which every fingerprint is guaranteed to have, are fixed from the moment of insertion. We use this fact to construct a reverse map that does not need to be accessed in response to natural shifting in the filter during insertions.

Suppose two items $x$ and $y$ share a quotient and remainder. Because runs are sorted by quotient, and fingerprints within a run are sorted by remainder, it follows that the fingerprints of $x$, $y$, and any other items with the same quotient-remainder pair are stored contiguously in the . Let us call this group of fingerprints a minirun. We will call these fingerprints' shared quotient-remainder pair their minirun ID. Note that even when an item does not share a quotient-remainder pair with any other item, its fingerprint is still contained in its own minirun of length 1. The minirun rank of an item is the rank of its fingerprint within its minirun.

The reverse map will map from a minirun ID to a list of all the inserted keys with that minirun ID. We order the keys in the list according to the order of their fingerprints in the minirun.

To insert an item into the database, we start by inserting its fingerprint into the filter. We locate the slot in which the fingerprint belongs, inserting it into the filter and obtaining its minirun rank in the process. We then turn to the reverse map and attempt to map that item's minirun ID to the item itself. If this is the first instance of its minirun ID, we create a new linked list consisting of only that item. If a previously-inserted item shares the same minirun ID, we insert the new item into the existing linked list in the position indicated by its minirun rank. As a result, all subsequent items are shifted back one position in the linked list, matching how their associated fingerprints in the minirun also shifted back one position when we made the filter insertion.

When querying for an item in the database, we always start by querying the filter for its fingerprint, obtaining its minirun rank if the fingerprint is present. We then query the reverse map for the minirun ID, retrieving the associated linked list and obtaining the item at the position indicated by the minirun rank. We can detect a false positive because the original key located at that position in the linked list will differ from the queried key. In that case, we use the original key we found to adapt the offending fingerprint in the filter, which we can do without modifying the reverse map.

<Ref> shows the representation of the and the reverse hash map during insertions and adaptations during queries.

The reverse map as a database
So far, we have acted as though the reverse map and the database are two separate data structures, both on disk. As a result, the reverse map would seem to incur additional disk accesses for every insertion and positive query. We call this the split reverse map setup. However, we can merge the database and reverse map into a single key-value store, eliminating this cost. Because the reverse map allows us to uniquely identify the original key of any fingerprint in the filter, we can simply store any relevant values next to these original keys in the reverse map. That is, instead of the database and reverse map being two separate mappings (one from keys to values and the other from fingerprints to keys), we use the reverse map as a single mapping from fingerprints to keys and values. In effect, the reverse map is being used as a replacement for the database. This does not require any additional queries over the conventional key to values mapping – the filter is always queried before the database, so we already obtain the fingerprint for any queried item. We call this the merged reverse map setup. For all of our disk experiments, we use the merged setup. However, note that this optimization leads to the items in the database being stored in hash order. Thus, this would no longer support range queries. For applications that wish to use range queries, the split reverse map would suffice. We evaluate the overhead of using the split setup later.

Like the counting quotient filter upon which it is based, the adaptive quotient filter supports storing multiple copies of the same item by storing a variable-length counter with each fingerprint.  In the CQF, each item had one slot holding its remainder, followed by 0 or more slots that encoded the number of times that fingerprint was present in the filter.  The CQF encoded the counter such that singleton fingerprints used zero additional slots for their count, which meant the CQF was just as space efficient as a non-counting quotient filter when the set contained no duplicates.  However, because the CQF has only two metadata bits, encoding the counters was quite complex.

Since the AQF has three metadata bits, we can use a much simpler encoding.
The AQF has three types of slots—remainders, extensions, and counters—and we need only to distinguish between the two types of “extra” slots that can follow a remainder: extension slots and counter slots.  In our encoding, both extension and counter slots have the is_extension bit set, and we use the is_runend bit to indicate whether the slot holds an extension or a counter.  This is safe because we indicate the end of a run by setting the is_runend bit on only the remainder slot of the last fingerprint in the run – any other slots of that fingerprint may be free to use their own is_runend bit as needed to indicate if they are extension or counter slots.

§.§ Dynamic List Problem

We can extend to the dynamic list problems as follows.  First, we extend the filter to store an extra bit with each fingerprint, i.e. we extend each slot with one extra bit.  We then store all elements of both $Y$ and $N$ in the filter, performing adaptations to eliminate any fingerprint collisions that occur during insertion and using the extra bit to record which set each fingerprint belongs to.  We can now add new items to $Y$ and $N$ in the same way: add the item to the filter, performing any adaptation necessary to eliminate fingerprint collisions and tagging the items with their origin.  We can delete items by simply deleting them from the filter.  Deleting a fingerprint $f$ may mean that we can shorten other fingerprints in the filter that we extended because they collided with $f$.  Finding any such eligible fingerprints is easy and efficient because the stores fingerprints sorted lexicographically, so all the fingerprints that can be shortened will be stored in a contiguous run of slots containing $f$.

Like the quotient filter, the also supports growing and shrinking.  The data structure described in this section operates by initially provisioning the table with enough slots to hold a certain number of elements and adaptivity bits. In the case of the static filter described in <Ref>, when sizes $n$ and $m$ of the list and list, respectively, are known ahead of time, we can predict the total space cost with high confidence, as per <Ref>. This tight allocation of the table is what allows us to match the lower bound from <Ref>.

Alternatively, if the and list sizes are not known in advance, we can instead fix two upper bounds $\hat{n}$ and $\hat{m}$ on their maximum allowed size, and construct the following dynamic filter: we allocate our table as a function of $\hat{n}$ and $\hat{m}$ (instead of $n$ and $m$), and perform all the insertions into the list and queries of list elements dynamically, as they are needed. The closer $n$ and $m$ get to $\hat{n}$ and $\hat{m}$, respectively, the closer the space cost will be to the space lower bound for a static filter on these list and list sets.

§.§ Skewed and Adversarial Workloads

The basic structure is monotonically adaptive, i.e. it never repeats a false positive.
The cost of never forgetting false positives is that, over time, the needs more and more slots to hold adaptivity information.
Like the regular quotient filter, the cost of an insert into the is $\Theta(\log n / (1-\alpha)^2)$ w.h.p., where $n$ is the number of slots and $\alpha$ is the fraction of slots that are currently in use <cit.>.
Thus, as the adapts, $\alpha$ approaches 1 and insertions performance can fall off a cliff.
In static and dynamic -list problems, this can be mitigated by making the filter large enough to accommodate the anticipated number of items.

However, for skewed and adversarial workloads, we can recover space used by adaptation, ensuring that the total space used by the filter remains constant over time.  This will compromise monotonicity, but will still ensure that the number of false positives from any sequence of $k$ queries is very close to $\epsilon k$ w.h.p.

The basic idea is to periodically rebuild the filter with a new hash function.  Rebuilding the filter puts the attacker back into the position of attacking a filter about which he has no information.  Thus we can drop any adaptivity information after the rebuild.  In other words, when we do the rebuild, each item will consume a single slot.

So, for example, we can build the filter, say, 10% larger than necessary, run the filter until the extra space is consumed by adaptations, and then rebuild.  Furthermore, we can de-amortize the rebuild process.  See Bender et al.  for details <cit.>.

§ STATIC LIST BOUNDS

In this section, we prove a space lower bound for solving the static list problem and
we show that we can use to build an optimal solution to the static list problem, up to low order terms.

Importantly, existing practical solutions to this problem (namely the Seesaw Counting Filter <cit.>,

and the Bloomier Filter <cit.>) are either not always correct solutions to the problem, or their space cost is at least constant factor away from the lower bound.

Let $U$ be a finite universe of elements, and let $Y$ and $N$ be subsets of $U$, with $Y \cap N = \emptyset$. Let $\epsilon \in (0, 1)$. A filter supports queries with the following guarantees: (i) every query for $y \in Y$ must answer , (ii) every query for $z \in N$ must answer , and (iii) every query for $x \notin Y \cup N$ answers with probability at most $\epsilon$. Notice that filters are static data structures.
Although it's possible to consider a dynamic version where the elements of either the or set (or both) are inserted and deleted dynamically, in this section we do not study this scenario.

Throughout this section we will let $n = |Y|$ be the size of the list, $m = |N|$ be the size of the list set, and $u = |U|$ be the size of the universe.

§.§ Upper Bound for Filters

Next we give an upper bound for the static list problem, based on the . We maintain the notation of the previous section, and let $\mu := \epsilon m/n$ be the number of false positives per element. Consider the following implementation, which we refer to as the .

* Create an $F$ with capacity for $n$ elements, and $\calA(n, m, \epsilon)$ bits reserved for adaptivity, where

\[
\calA(n, m, \epsilon) := (1 + o(1)) n \log(1 + \mu) + O(n).
\]

* Insert into $F$ every element from $Y$.

* Query $F$ on each element from $N$.

* If $F$ becomes full at any point before all queries are done, fail.

* Return $F$.

Importantly, the queries in the final step fix all false positives from $N$. The resulting filter satisfies the requirements of a filter.

The uses
$(1 + o(1)) n \log(\max\{1/\epsilon, m/n\}) + O(n)$ bits of space.

The space cost is the sum of the space reserved for the remainders, plus the per-slot metadata bits, plus the space reserved for adaptivity bits. This is a total of $n \log(1/ \epsilon) + O(n) + \calA(n, m, \epsilon)$ bits. Observe that

\begin{align*}
\calA(n, m, \epsilon) &=
\left\lbrace
\begin{array}{ll}
O(n) & \text{if $\mu \leq 1$}\\
(1 + o(1))n(-\log(1/\epsilon) + \log(m/n)) + O(n) & \text{otherwise}
\end{array}
\right.
\end{align*}

Notice that $\mu \leq 1$ if and only if $1 / \epsilon \geq m/n$. Hence,

\begin{align*}
n \log(1/ \epsilon) + O(n) +& \calA(n, m, \epsilon)\\
&= \left\lbrace
\begin{array}{ll}
n \log(1/\epsilon) + O(n) & \text{if $1 / \epsilon \geq m/n$}\\
(1 + o(1))n \log(m/n) + O(n) & \text{otherwise}
\end{array}
\right.\\
&= (1 + o(1))n\log(\max\{1/\epsilon, m/n\}) + O(n).
\end{align*}

Notice that the construction of the may fail if the space initially reserved is insufficient. The following theorem, the central result of this section, establishes that failure is unlikely.

Suppose $\omega((\log^{3/2} n)/\sqrt{n}) \leq \mu \leq 2^{o(n)}$. Then, the number of adaptivity bits added to the is at most $\calA(n, m, \epsilon)$ with probability $1 - 1/\poly(n)$. In particular, the probability that the construction succeeds is $1 - 1 / \poly(n)$.

In the rest of this section, we prove this theorem. Let $A$ be the number of adaptivity bits needed after all the elements of $N$ are queried in step (5). We want to show that $A \leq \calA(n, m, \epsilon)$ with probability $1 - 1/\poly(n)$.

Let $h$ be fingerprint hash function. For any $x, y \in U$, let $\lcp(x, y)$ be the longest common prefix of $h(x)$ and $h(y)$. We decompose $A$ into two parts: Let $A_1$ and $A_2$ be the number of adaptivity bits added in steps 3 and 4, respectively. For any $y \in Y$, let $A_1(y)$ and $A_2(y)$ be the number of adaptivity bits added in step 3 and 4, respectively, to the fingerprint of $y$. Then, $A = A_1 + A_2$, and $A_i = \sum_{y \in Y} A_i(y)$.

We have $A_1 = O(n)$ with probability $1 - 1/\poly(n)$.

This follows directly from Lemma 9 in Bender et. al. <cit.>.

We will use the following basic result about the distribution of the maximum of a collection of independent geometric random variables.

Let $X_1, \dots, X_k$ be independent geometric random variables with parameter $1/2$. Let $M_k := \max_i X_i$. Then,

\[
0 \leq \expect{M_k} - \log(e) H_k \leq 1,
\]

where $H_k$ is the $k$-th harmonic number.

$\expect{A_2} \leq n \left(1 + \log(e) + \log\left(1 + \mu\right)\right)$

We say that $z \in N$ has a soft collision with $y \in Y$ if the baseline fingerprints of $y$ and $z$ match, that is, $\lcp(y, z) \geq \log(n/\epsilon)$.

Fix an arbitrary $y \in Y$. We claim that $\expect{A_2(y)} \leq 1 + \log(e) + \log\left(1 + \mu\right)$. Let $C$ be the (random) numbers of $z \in N$ that have a soft collision with $y$. For each $z$ that has a soft collision with $y$, let $F(z) := \lcp(y, z) - \log(n/\epsilon)$; this is the smallest number of adaptivity bits that $y$ must have to fix a false positive $z$. Then,
$A_2(y) = \max\limits_{\text{$z$ has a soft collision with $y$}} F(z)$.

Observe that $F(z)$ is a geometric random variable with parameter $1/2$. Because all fingerprints are independent, the $F(z)$'s are independent. This is true even if $C$ is known. Thus, $A_2(y)$ conditioned on $C = k$ is identically distributed as the maximum of $k$ independent geometric random variables with parameter $1/2$. Call this maximum $M_k$. Then,

\[
\expect{A_2(y) \mid C = k} = \expect{M_k}.
\]

For $k = 0$, we have $\expect{A_2(y) \mid C = k} = 0$. For $k \geq 1$,

\begin{align*}
\expect{A_2(y) \mid C = k} &\leq 1 + \log(e) H_k \tag{by \Cref{lem:maximum-geometric}}\\
&\leq 1 + \log(e)(1 + \ln k) \tag{as $H_k \leq 1 + \ln k$ for $k \geq 1$}\\
&= 1 + \log(e) + \log k.
\end{align*}

Hence, $\expect{A_2(y) \mid C} \leq 1 + \log(e) + \log(1 + C)$. Then,

\begin{align*}
\expect{A_2(y)} &= \expect{\expect{A_2(y) \mid C}} \tag{by the tower rule}\\
&\leq \expect{1 + \log(e) + \log(1 + C)}\\
&\leq 1 + \log(e) + \log(1 + \expect{C}). \tag{by linearity of expectation and Jensen's inequality}
\end{align*}

Notice that $C = \sum_{z \in N} C(z)$, where $C(z)$ is an indicator random variable that is $1$ exactly when $z$ has a soft collision with $y$. Recall that $\expect{C(z)} = \epsilon / n$. By linearity of expectation, $\expect{C} = \epsilon m/n = \mu$, and, finally,

\[
\expect{A_2(y)} \leq 1 + \log(e) + \log\left(1 + \mu\right).
\]

This concludes the proof of the claim. The lemma follows by summing over all $y \in Y$, and using linearity of expectation.

To simplify notation, let $\mu = \epsilon m/n$ be the mean number of queries that have a soft collision with any fixed $x \in S$.

Suppose $\omega((\log^{3/2} n) / \sqrt{n}) \leq \mu \leq 2^{o(n)}$. Then, $A_2 \leq (1 + o(1)) \expect{A_2}$ with probability $1 - 1 / \poly(n)$.

Recall that $A_2 = \sum_{y \in Y} A_2(y)$. The proof is divided into two parts. First, we show that the random variables $A_2(y)$ are negatively associated (NA). Roughly speaking, this is because when some query from $N$ is a false positive due to fingerprint match with $y \in Y$, then the new adaptivity bits make following queries less likely to cause a false positive on $y$. Though intuitive, proving that the $A_2(y)$'s are NA is challenging because we can't directly apply standard theorems on negative association <cit.>.

For each $y \in Y$, let $G(y)$ be the number of $z \in N$ such that $\lcp(y, z) \geq \log(n/\epsilon) + A_1(y)$, that is, elements that can cause a false positive due to a fingerprint match with $y$ (and only with $y$). The argument rests on the following four properties of the random variables involved:

* The $G(y)$'s are NA random variables.

* Conditioned on the $G(y)$'s, the $A_2(y)$'s are independent.

* The probability that $A_2(y)$ is large is a non-decreasing function of the $G(y)$. Formally, for every $\ell$, $\prob{A_2(y) \geq \ell \mid G(y) = k}$ is a non-decreasing function of $k$.

* Conditioned on $G(y)$, the random variable $A_2(y)$ is independent of the $G(y')$'s with $y' \neq y$.

Once negative association of the $A_2(y)$'s is established, we are almost in the conditions of the Chernoff-Hoeffding inequality for the sum $\sum_{y \in Y} A_2(y)$. Unfortunately, there is one hypothesis that is not met, namely they $A_2(y)$'s are not deterministically bounded—in the worst case, an unbounded number of adaptivity bits may need to be added to some element $y$. This, however, is unlikely, as $A_2(y) = O(\log(\mu + n))$ with probability $1 - 1/\poly(n)$; this is by a Chernoff bound, and a tail bound on the geometric distribution. We can put this observation to work and circumvent the boundedness requirement of Chernoff-Hoeffding, using the following truncation trick: We define $A_2'(y) := \min\{A_2(y), O(\log(\mu + n))\}$, and apply the Chernoff-Hoeffding bound on the truncated sum $A_2' := \sum_{y \in Y} A_2'(y)$. Once concentration around the mean is established on $A_2'$, we conclude the proof by showing that, with high probability, no truncation is actually done, so the analysis on $A_2'$ applies to $A_2$ most of the time. Specifically:

* $A_2 = A_2'$ with probability $1 - 1/\poly(n)$;

* $\expect{A_2'} \leq \expect{A_2}$.

The construction of the filter succeeds if and only if $A \leq \calA(n, m, \epsilon)$. Since $A = A_1 + A_2$, and by <Ref>, <Ref> and <Ref> we have $A \leq O(n) + (1 + o(1))(n (1 + \log(e) + \log(1 + \mu))) = O(n) + (1 + o(1)) n \log(1 + \mu) = \calA(n, m, \epsilon)$, with probability $1 - 1/\poly(n)$.

§.§ Lower Bound for Filters

A lower bound for this problem was sketched out in Reviriego et al. <cit.>, but without a rigorous proof. Moreover, the lower bound as stated in that work is hard to compare against our upper bound using ; here, we give an equivalent but more condensed lower bound.

Suppose $u \geq c(n^2/\epsilon + m^2)$, for some large enough constant $c > 0$, and $\epsilon \leq 1/2$. Then, the number of bits used by a static filter is at least

\[
n \log\left(\max\left\lbrace\frac{1}{\epsilon}, \frac{m}{n}\right\rbrace\right) + \log(e) \min\{\epsilon m, n\} + O(1).
\]

Before diving into the proof let us briefly discuss the lower bound. Dividing by $n$, we have that a filter uses at least

\[
\log\left(\max\left\lbrace 1/\epsilon, m/n\right\rbrace\right) + O(1) = \log(1/\epsilon) + \log(\max\{\epsilon m/n, 1\}) + O(1)
\]

bits per element. For comparison, traditional filters have an information-theoretical lower bound of $\log(1/\epsilon) + O(1)$ bits per element. This can be interpreted as follows: When building a filter, we need to (i) record the $n$ list elements while ensuring that at most an $\epsilon$ fraction of all other elements are incorrectly reported as present, and to (ii) record the $m$ elements. To accomplish (i) we need at least $\log(1/\epsilon)$ bits per element, just like a regular filter. The number of additional bits needed to accomplish (ii) depends on $\mu := \epsilon m/n$, which is the number of false positives per element. When $\mu \leq 1$, only a small constant number of extra bits per element are needed; when $\mu > 1$, $\log(\mu)$ extra bits per element are needed.

Let $\calI = \{(Y, N) \mid Y, N \subseteq U, Y \cap N = \emptyset, |Y| = n, |N| = m\}$ be the set of all inputs of the problem. Consider a static filter with false positive probability $\epsilon$, that uses at most $b$ bits on all inputs $(Y, N) \in \calI$. For any random bit string $r$, denote $\textsf{Inst}(Y, N, r)$ the instance of the data structure with randomness $r$ on input $(Y, N)$. We say that an instance $F$ represents input $(Y, N)$ if there exists a string of random bits $r$ such that $F = \textsf{Inst}(Y, N, r)$.

The proof uses the following standard information-theoretic argument: Let $\calF$ be a subset of instances of the data structure, such that

* every input is represented by some instance of $\calF$, and

* for every $F \in \calF$, $F$ represents at most $c$ inputs.

When $\calF$ satisfies property (1), we say it covers $\calI$; when it satisfies (2), we say it has covering parameter $c$. Then, $|\calF| \geq |\calI| / c$. Because all instances from $\calF$ must be encoded by some state of the data structure, we have $2^b \geq |\calF|$, which in turn implies the space lower bound $b \geq \log |\calF| \geq \log(|\calI| / c)$. The challenge is finding a cover with small covering parameter $c$.

Fix any input $(Y_1, N_1)$. Let $\calF$ be the set of instances that err on at most a fraction $\epsilon$ of $\overline{U} := U \setminus (Y_1 \cup N_1)$. Let $F_r = \textsf{Inst}(Y_1, N_1, r)$. Because the filter errs with probability $\epsilon$, we have, for every $z \in \overline{U}$,

\[
\Pr_r\left[\text{$F_r$ errs on $z$}\right] \leq \epsilon.
\]

Summing over $z$, we find that

\[
\E_r\left[\text{number of $z \in \overline{U}$ on which $F_r$ errs}\right] \leq \epsilon |\overline{U}|.
\]

Hence, there exists some $r$ such that $F_r$ errs on less than a fraction $\epsilon$ of $\overline{U}$. Because this instance $F_r$ represents $(Y_1, N_1)$, this implies that there exists some instance from $\calF$ that represents $(Y_1, N_1)$, that is, $\calF$ covers $\calI$.

The number of inputs $(Y, N) \in \calI$ is

\[
|\calI| = {u \choose n}{u-n \choose m}.
\]

We claim that $\calF$ has covering parameter

\begin{equation}
\label{eq:covering}
c \leq \min_{\epsilon' \in (0, \epsilon]} {n + \epsilon'(u - n - m) \choose n}{u - (n + \epsilon'(u - n - m)) \choose m}.
\end{equation}

To see this, consider an $F \in \calF$ and let $(Y, N) \in \calI$ represented by $F$. Then, $c$ is upper bounded by the number of inputs $(Y', N')$ such that $Y' \subseteq \{x \in U \mid \text{$F$ answers \yes on $x$}\}$ and $N' \subseteq \{x \in U \mid \text{$F$ answers \no on $x$}\}$; these are all the inputs compatible with the answers of $F$. The first and second terms on the right-hand side of <Ref> are the number of ways to choose $Y'$ and $N'$, respectively, when $F$ errs on a fraction $\epsilon' \in (0, \epsilon]$ of elements from $\overline{U}$. Notice that the right-hand side of <Ref> is not non-decreasing in $\epsilon'$, so the minimum is not necessarily attained at $\epsilon' = \epsilon$.

A lengthy calculation, which we omit here due to space constraints, shows that

\[
\log(|\calI|/c) \geq \min_{\epsilon' \in (0, \epsilon]} n\log(1/\epsilon') + \epsilon' m \log(e) + O(1).
\]

Finally, an analysis of the function $f(\epsilon') = n \log(1/\epsilon') + \epsilon' m \log(e) + O(1)$ with $\epsilon' \in (0, \epsilon]$ reveals that

* if $\epsilon \leq n/m$, then $f$ attains its minimum at $\epsilon' = \epsilon$;

* if $\epsilon > n/m$, then $f$ attains its minimum at $\epsilon' = n/m$.

\begin{align*}
\log(|\calI|/c) \geq &\left\{
\begin{array}{cc}
n \log(1/\epsilon) + \epsilon m \log(e) + O(1) & \text{if $\epsilon \leq n/m$}\\
n \log(m/n) + n \log(e) + O(1) & \text{otherwise}
\end{array}
\right.\\
&= n \log(\max\{1/\epsilon, m/n\}) + \log(e) \min\{\epsilon m, n\} + O(1).
\end{align*}

§ EVALUATION

The goal of the evaluation is to answer the following questions regarding the performance of the :

* How does the insertion and query performance of the compare to other adaptive and non-adaptive filters?

* How well does the improve overall database performance, compared to other adaptive and non-adaptive filters?

* How much space does the use to adapt?

* How does the compare to prior solutions to the list problem?

* How does the false positive rate in the change during a dynamic workload?

* How fast can two instances be merged?

§.§ Results summary

We compare the  [https://anonymous.4open.science/r/adaptiveqf-C438] against two state-of-the-art adaptive filters, the telescoping adaptive filter (TQF) <cit.> and the adaptive cuckoo filter (ACF) <cit.>.

We also include two non-adaptive filters, the quotient filter (QF) <cit.> and the cuckoo filter (CF) <cit.>, as baselines to understand the overheads and benefits of adaptivity. The quotient and cuckoo filter are chosen as baselines as these are the filters upon which the adaptive filters used in our evaluation are developed.

We found that adaptivity is an extremely efficient way to reduce the false-positive rate of a filter. For example, on a Zipfian query workload, the is able to reduce the false-positive rate by about 100$\times$ for an additional cost of less than 1/1000th of a bit per item.  In contrast, a non-adaptive filter would need 7 bits per item to achieve the same false-positive rate reduction.

Absent any system, the has comparable space usage to the other filters.  For example, the uses more space than the cuckoo filter, but only by 1%.

Most notably, the performs at par with the quotient filter on which it is based, indicating little to no overhead for its adaptivity. On the other hand, the adaptive cuckoo filter and telescoping adaptive filter are significantly slower than their respective non-adaptive counterparts.

However, when the cost of a false positive is increased by including an on-disk database, the benefits of adaptivity become apparent. For example, when used to filter queries from a fixed dataset, the is able to learn the query set, seeing 10$\times$ fewer false positives over 200 million queries than the quotient filter and the cuckoo filter. This resulted in 4-7$\times$ faster queries. Furthermore, using the to filter queries in a B-tree databases had query throughput that was impervious to an adversarial query workload, whereas the throughput of non-adaptive filters dropped about 2$\times$ with the inclusion of an adversary representing a mere 1% of queries.

Although the benefits of maintaining a low false positive rate during queries are shared by all three adaptive filters, the inclusion of a database reveals that the is much faster than other adaptive filters during insertions. The systems using the TQF and the ACF slow down significantly as the filters fill up due to frequent modifications of their on-disk backing stores. Between 85-90% fullness, the averages 5$\times$ the insertion throughput of the ACF and 30$\times$ that of the TQF.

Other results
The matches the rate of change of false-positive rate during queries from a real-world dataset compared to other adaptive filters. The solves dynamic problems with changing sets. The supports fast merges and bulk insertions. Finally, despite being dynamic, the achieves similar or better space usage compared to purpose-build solutions for the static problem.

§.§ Experimental setup

One challenge we face is that the filters do not all support the same false-positive rates.

Thus, we pick a target false-positive rate and configure each filter
to get as close as possible to the target false-positive rate without
sacrificing performance. This is in accordance with the prior research on evaluating filters <cit.>. Our target false-positive rate is $2^{-9}$ ($\approx 0.2\%$) which is the commonly used in most practical system configurations <cit.>.

We configure the -based filters (AQF, TQF, and QF) with 9-bit remainders. We use 12-bit fingerprints and blocks of size 4 in the cuckoo filter-based filters (ACF, CF). This results in all filters having a false-positive rate of $2^{-9}$. We use MurmurHash2 <cit.> as the hash function for all filters. The does not require any special properties in the hash function compared to other filters.

Machine specification

All experiments were run on an Intel(R) Xeon(R) Gold 6338 CPU @ 2.00GHz with 96 MiB L3 cache. The machine has 1 TB of memory, 64 CPUs, and 4 TB of SSD-based local instance storage, 64-bit platform. We restrict our runs to a single core.

§.§ Microbenchmarks

We evaluate the performance of the filters in RAM. We create the filters with $2^{27}$ (134M) slots, which makes them substantially larger than the L3 cache on the machine where experiments are performed.

We fill each filter to 90% load factor[Load factor is the ratio of the number of occupied slots over the total number of slots in the filter] and report the performance of the filter as a function of load factor.
Although all of the filters evaluated in our benchmarks support up to 95% load factor, we restrict them to 90% in order to give them room to store any additional data needed to adapt.

We evaluate adaptive filter performance on two fundamental operations: insertions and lookups. We evaluate insertions on uniformly random 64-bit keys, and lookups on both uniform-random and Zipfian distributions <cit.>. In the Zipfian distribution, we use a Zipfian coefficient of 1.5 and a universe size of 10 million items.
We do not count the time required to generate the input to the filters, only the time to insert and query items in the filters. This way we only measure the differences in filter performance.

We perform 200 million queries for both query distributions. The numbers reported for both insertions and queries are the average of 5 trials.

We perform the benchmarks in isolation of any overheads from the reverse maps. For the adaptive filters, which use reverse maps to obtain keys for adaptation, we pick valid arbitrary keys that will suffice in order to simulate having the reverse map present. We still measure hashing as part of the filters' performance because it is done independently of the reverse map and database.

<Ref> shows the throughput of adaptive and non-adaptive filters for insertions and queries.

The is based on the counting quotient filter. is not slower than the quotient filter, but it is slightly faster during both insertions and queries, indicating that the overhead of adaptivity in the is minimal. Increased query speed may also be attributed in part to the slightly lower false positive rate resulting from adaptation. The CF has the highest insertion throughput among all the filters, which is consistent with previous research <cit.>. In exchange, the quotient filters offer fast resizing, mergeability, and efficient variable-length counters/values.

In contrast, there is a noticeable overhead in the ACF compared to the CF when it comes to queries due to the need to hash a given query multiple times. The CF can use a single hash function to obtain both the index and the tag of an item simultaneously. On the other hand, the tag of an item in the ACF depends on the location of the tag. This means that the ACF must first apply a hash to calculate the indexes of an item, and only then apply additional hashes to search for the tag.

Similarly, the TQF also sees a lower throughput due to the additional overhead of applying arithmetic coding to encode and decode hash selectors when making queries. Aside from queries, both the ACF and TQF have additional overhead during insertions for the same reason. As items naturally shift and move during insertions, the tags stored need to be rehashed in order to reflect their new locations.

When switching to Zipfian queries, all five filters benefit. Since the filters are easily large enough to overwhelm the machine's L3 cache, skewing the queries allows the cache to be more effective. The adaptive filters can also maintain a significantly lower false positive rate than the non-adaptive filters. However, the extra overhead in the ACF and TQF from the use of hash selectors puts a cap on how fast their queries can be, so the decreased false positive rate and increased cache friendliness have limited benefit. The QF ends up having high variance in its zipfian query speed. This is a result of the high impact of locality in the QF, which uses linear probing in contrast to the CF. When popular items fall in small clusters, queries are fast, but if they are in larger clusters, query performance slows down. The does not see the same variance since it quickly adapts to any zipfian distribution regardless of its locality.

We evaluate the space efficiency of the filters by measuring the actual space needed to store items. We report the space efficiency at 90% load factor. This is space usage prior to any adaptation, so each filter contains the same number of items and uses the same number of slots.

<Ref> shows the empirical space usage and false-positive rate of different filters in these experiments. The space reported in the table is only the filter space. It does not include the space required by the reverse hash map. The has $\sim8-9\%$ space overhead compared to the non-adaptive quotient filter.

The preserves thread safety from the counting quotient filter. It divides the slots in blocks of 4096 slots each and uses a lightweight spin lock for each block to avoid corruption.
During an insertion or an adaptation, each thread first acquires two locks on consecutive blocks, the block in which the item hashes and the next one. Two consecutive locks helps to avoid any corruption in case the shifting of items overflows into the next block.

It is also possible to execute mixed operations concurrently, but two modifications would be required. First, locks would also have to be acquired during queries, which would not be necessary if insertions and queries are performed in separate phases.  Second, if the database being used also supports concurrent inserts, the lock acquired during filter inserts would need to be held until the database insert is finished. This is to ensure the items in the same minirun are also inserted into the database in the same order as they are inserted into the filter. This is only necessary if there are mixed inserts and adaptations being done concurrently; in an insert-only workload, items in a minirun are identical in the filter until an adaptation happens, so the order of insertion into the database does not matter.

<Ref> shows insertion throughput of the in isolation, as a function of the number of threads used, to demonstrate that the itself maintains good parallelism. We also show the performance of the QF for comparison. For this experiment, we use a filter of size $2^{26}$, and we configure the locks to span $2^{16}$ slots each. Therefore, there are $2^{10}$ locks and contention is low. We vary from 1 thread to 12 threads in the increments of 2. Both the and QF show almost linearly scaling with the increasing number of threads while the being slightly faster.

Filter     $-\log$(FPR)     Space (MB)

Adaptive Quotient filter      9     203.610

Telescoping Quotient filter      9     218.104

Adaptive Cuckoo filter      9     201.402

Quotient filter        9     186.818

Cuckoo filter      9     201.401

Empirical space usage and false-positive rate of filters used
in the benchmarks. All filters were created with $2^{26}$ slots.
Space is given in MB. Negative $\log{FPR}$ means higher is better.

§.§ System benchmarks

Filter     Size (log)     Map Inserts     Map Updates     Map Queries

AQF     20     943718     0     0

TQF     20     943718     3608887     3356560

ACF     20     947815     584829     584829

AQF     24     15099494     0     0

TQF     24     15099494     56697889     52650676

ACF     24     15103591     9336669     9336669

Number of reverse map accesses during insertions. The TQF and ACF make additional updates and queries in maintaining the reverse map. All filters of a given size were filled to 90% load.

Reverse Map Setup     Inserts per Sec     Queries per Sec

Merged     $2.32 \times 10^5$     $1.843 \times 10^7$

Split     $1.12 \times 10^5$     $1.819 \times 10^7$

Comparison of merged vs split reverse map and database. Tests were run with 200M queries on a filter of size $2^{25}$. When the reverse map and database are split, inserts have to be done into each one independently, so insertion takes twice as long. However, due to the infrequency of false positives, querying only takes 1-2% longer.

Filter     CAIDA Queries/Sec     Shalla Queries/Sec

AQF     31.6M     15.8M

TQF     8.4M     6.7M

ACF     34.1M     18.3M

QF     24.1M     16.8M

CF     119.2M     62.2M

Query speed on real-world datasets after $2^{26}$ inserts.

In this section, we evaluate the performance of as a front-end filter to a disk-based B-tree database.
We create an instance of the disk-based B-tree by using the B-tree implementation from SplinterDB <cit.>. For these tests, we disable the $B^\varepsilon$-tree structure and its accompanying filters in SplinterDB, and use it as a filter-less on-disk dynamic $B$-tree. Because filters are frequently used alongside databases too large to fit in memory, storing data on disk using the B-tree is representative of real-world database systems.

We create an in-memory filter together with an on-disk map holding uniformly distributed keys with randomly generated values that represents a database. For the non-adaptive filters, the database holds the full set of keys-value pairs. For the adaptive filters, the database instead maps the fingerprints stored in the filter to their associated key-value pairs based on the optimization of using the reverse map as the database described in <Ref>.

To perform an insertion, a key is first inserted into the in-memory filter, and then the key-value pair is inserted into the database.
For non-adaptive filters, the key-value pair is inserted into the database directly. For adaptive filters, a fingerprint is obtained when inserting into the filter, and then the fingerprint-key-value triple is inserted into the database, mapping the fingerprint to the key-value pair.

To perform a query, the key is queried in the filter. If the filter returns “negative,” then that key is not in the database and no disk query is performed. If the filter returns a “positive,” the key and any corresponding data are retrieved from the database.
The non-adaptive filters do this by directly querying the database for the key, and a false positive occurs if the database was not able to find that key.
The adaptive filters instead query the database for the fingerprint found in the filter, and a false positive occurs if the key stored in the database does not match the key that was queried for. The adaptive filters can then use the returned key to adapt the filter so that the queried key no longer returns “positive.”

Insertion performance
<Ref> shows insertion throughput of the database as a function of the filter load factor. For this experiment, we create filters with $2^{25}$ slots and insert keys from a uniform random distribution until the filters are 90% full.

At 1% progress intervals, we record the amount of time taken and calculate the insertion throughput over that interval.

The system has similar performance when using the compared to the non-adaptive QF and CF filters. This shows that there is little to no overhead of using the adaptive filter on the insertion performance of the system.

Since insertions into the B-tree are the main bottleneck, all 5 filters start with roughly equal insertion throughput. However, the ACF and TQF fall off over time. This is due to the cost of maintaining the reverse map. <Ref> shows the number of additional accesses to the reverse map done by the adaptive filters. As fingerprints are inserted into the , no entries for previous insertions need to be modified in the reverse map.

As the ACF fills up, it needs to do a large number of kick outs. Since the tag being stored to represent an item changes depending on its location in the filter, it is not sufficient to simply move a tag when performing a kick out. Instead, every kick out requires an expensive query to the backing map so that a new fingerprint can be hashed. The frequency of kick outs increases with load factor.

When a fingerprint is inserted into the TQF, it may cause other fingerprints to shift. The reverse map implemented with the TQF is based on location – keys are stored alongside their fingerprints and thus need to shift with them. The constant shifting of fingerprints induces many additional reverse map accesses.

Adversarial query performance
In  <Ref>, we measure the effect of a query-only adversary on system throughput. Even if the overall query distribution is uniform, an attacker can artificially skew the distribution by skewing their own queries. An adversary can detect the latency difference between negative and positive queries (including false positives), and even without knowledge of the actual insertion set, record a list of positive queries. They can then repeat these queries to intentionally induce I/Os.

Even in a system with a cache, the adversary needs only collect enough false positives to overload the cache, then proceed to cycle between these queries to render the cache ineffective.

In this experiment, we perform 200M queries. The first 100M give the adversary time to collect false positives. We then measure the average query throughput over the next 100M queries. We vary both the cache size and the frequency of adversarial queries over different trials. <Ref> has five plots, each plot showing the results of the experiment on a different cache size ranging from 1.5%, 3%, 6%, 12%, to 25% the size of the input dataset. There are marginal improvements to the performance of the non-adaptive filters when provided a larger cache. However, a small fraction of adversarial queries has a disproportionately large impact on system performance even in the experiment with the largest cache. With the cache holding 25% of the dataset, an adversary representing less than 1.5% of the total queries can cause query throughput for the entire system to drop by 2$\times$ that of normal operation, which is already lower than that of the . This increases to 3$\times$ with 3% adversarial influence and up to 10$\times$ with 10% adversarial influence.

The offers high and consistent query performance irrespective of the frequency of adversarial queries. Even without adversarial queries the AQF has comparable query performance to the non-adaptive filters. But in the presence of adversarial queries it can offer up to an order of magnitude higher query performance.

Merged vs. split reverse map
As discussed in  <Ref>, the reverse map and database can be merged into a single data structure so that reverse map inserts and queries do not incur additional overhead. This makes the database unable to perform range queries. The split reverse map and database setup, however, does support range queries.  <Ref> compares the two setups to show the overhead of using the split setup in the case that one would like to use range queries. The insertion throughput is halved due to needing to insert into both the database and reverse map individually. However, query throughput is affected by only about 1% due to the infrequency of false positives on general workloads.

§.§ Adaptivity rate for real-world datasets

In application benchmarks, we use real-world datasets to evaluate the rate of change of false positive rate and space usage in adaptive filters in the presence of queries.

To evaluate the false positive rate over time, we first construct all three adaptive filters and fill them to 90% load factor. We then construct a query set that will be performed over time, and the filters will adapt to the false positive queries. We also construct multiple independent query sets from the Zipfian distribution, which we use to compute the instantaneous false positive rate. The filters do not adapt while measuring the instantaneous false positive rate.

We perform a total of 3 million queries when the filters adapt to measure the rate of change of false positive rate and the space usage. We compute the instantaneous false positive rate and space usage after every 1% of queries.

To compute the instantaneous false positive rate, we construct 100 independent query sets from a Zipfian distribution. During the false positive computation, we turn off the adaption in the filters. Therefore, filters only adapt during normal queries and  do not adapt while computing the false positive rate.

We use three different datasets for application workloads. The first dataset is synthetic and generated from the Zipfian distribution (with Zipfian constant 1.5) on a universe of size 1 billion.

The second dataset is CAIDA passive traces <cit.>, a set of anonymized network traces collected by the Center for Applied Internet Data Analysis between April 2008 and January 2019.

The third database, the Shalla <cit.> block list, is a list of about 3 million malicious URLs compiled by Shalla Secure Services. For our experiments, we perform insertions and queries from the Shalla list.

<Ref>  shows the rate of change of false positive rate and space during queries in adaptive filters.

The false positive rate immediately drop for all three filters. This is because the filters adapt to hot items early in the query sequence.
Later on, the filters adapt to infrequent items, each of which brings a smaller drop in the false positive rate.

The drop in false positive rate over time is similar for all three adaptive filters for the Caida and Shalla datasets. These two datasets are not very skewed, and therefore the strong adaptivity advantage of over the TQF and ACF is not very apparent.

On Zipfian queries, the false positive rate for all three filters drops equally. However, over time the false positive rate in the drops to lower than the TQF and ACF. This shows that the strong adaptivity guarantees in the lead to a lower false-positive rate over time.
The TQF and ACF do not adapt completely the first time they encounter the false positive, which can result in subsequent false positive results when colliding with the already adapted key.

The space increase (in bits/item) increases similarly with all three adaptive filters. However, the has a lower initial space usage compared to the TQF and ACF (refer  <Ref>), and therefore the overall space usage of the is lower.

For actual query throughput, we list the numbers in <Ref>. This includes costs incurred by occasional queries to the database. The has comparable query throughput to both the AQF and QF. All filters benefit from cache-friendliness induced by the skewed distribution of CAIDA's queries. However, the and ACF see more improvement than the QF due to their ability to adapt to the most popular false positive queries in the distribution.

§.§ Dynamic workloads

Apart from static workloads, we also evaluate the change of false positive rate in the in the presence of deletions, insertions, and queries over time. This simulates the real-world use cases where the items in the list change over time. We do not include other adaptive filter implementations, TQF and ACF, in this experiment as they do not support deletes.

Like the application workload, we perform 3 million queries and compute instantaneous false-positive rates after every 1% of queries. At 10% intervals, we delete and replace 20% of the items. To compute the instantaneous false-positive rate, We use 1 million queries from the same Zipfian distribution without adapting.

<Ref> shows the false positive rate over time in the presence of deletions, insertions, and queries. Every 10% of the operations, we introduce a massive churn in which 20% of the items in the filter are replaced.

There are a couple of spikes in the false positive rate that coincide with the churns. They are caused when one of the inserted items causes a popular query to become a false positive. But the filter quickly adapts to the new item, and the false positive rate once again drops very low.

TQF and ACF are excluded from these experiments as those implementations do not support deletions.

In these experiments, we lose strong adaptivity. This is a deliberate choice and not a limitation of the . We can support strong adaptivity in the presence of updates to the list and list by associating a small value to the fingerprints as described in <Ref>. Strong adaptivity can be preserved in the presence of deletions by setting an item's counter to zero instead of deleting the item completely. We chose in these experiments not to preserve strong adaptivity in order to demonstrate the filter's ability to maintain a low false positive rate in dynamic environments and because the highly dynamic nature of these experiments would make the extra space usage impractical.

skip = 4pt

§.§ Merge and bulk load performance

Filters are often used to build inverted text indexes on genomics data <cit.>, where they are merged with other filters during compactions. Therefore, mergeability is a critical feature in filters for easy adoption in database systems.

The QF supports efficient merging, and the supports efficient merging by extension, since we do not store any auxiliary hash encoding information. In contrast, merging in the TQF and ACF is not straightforward due to the hash selectors obscuring the original keys. To evaluate the merge performance of the , we use an in-memory hash table as the reverse map because we just want to evaluate the filter's merging speed. Note that merging two reverse maps is easy, because minirun lists sharing an ID can be concatenated, so long as miniruns in the filter are also concatenated during merging.

Operation     Time per item ($\mu s$)

Insert into filter                    0.520092

Insert into half-size filter          0.353332

Merge two half-size filters           0.039147

Sort in hash order (qsort)            0.348060

Bulk insert                           0.019569

Average latency for inserting items into an with $2^{26}$ slots until 90% full, inserting into two instances with $2^{25}$ slots each and then merging, and sorting items beforehand and then bulk inserting.

We also evaluate bulk loading in the , where the entire list of items is known. We find that the raw execution time of merging and bulk inserting is extremely low. For bulk loading, we would prepare by first sorting the items in hash order.

<Ref> shows the merge and bulk-build performance of the .  Inserting into smaller filters and merging is about $25\%$ faster than directly inserting into a full size filter.  Sorting followed by bulk building is about $10\%$ faster than merging.  In this particular test we used the C library function qsort.  More specialized sorting functions for a given situation may be even faster.  Merging is slower than bulk loading due to needing to compare quotient-remainder pairs between the two merged filters. There is also an overhead in identifying runs when stepping through the filter.

§.§ Space comparison to static solution

<Ref> shows the space usage of CRLlite <cit.>, a custom-built and static list solution based on the cascading Bloom filter, and the .

The space usage of the while being dynamic is always smaller or similar to CRLite.

For the evaluation, we fix the aggregate size of the list and list to 1 million items and evaluate the space with changing ratio of the list and list.

§.§ Non-adaptive filter additional space

The adaptive filters have higher space usage (due to the overhead of adaptivity) compared to the non-adaptive filters. Therefore, we performed an experiment where we configured the QF and CF with a higher number of bits to give them extra space and lower false-positive rate.

With extra space, the uniform query performance of the CF increases by $1$%, and the Zipfian query performance increases by $0.3$%. Similar performance gains are seen for the QF. Therefore, even with extra space and a lower false-positive rate, the CF-based system is $20$% slower compared to the -based system.

§ CONCLUSION

We introduce in this paper. The is the first strongly adaptive filter which support high throughput operations using single-hashing and quotienting.  Using the adaptive filters in the system we can increase the overall system throughput by avoiding repeated unnecessary accesses to the backing stores (or other slower storage). The strongly adaptive filters guarantees consistently low false positives rate over time on dynamic workloads.

Traditional filters have been the go to data structure for over five decades. However, traditional filters lose their benefits in the presence of modern skewed and adverserial real-world workloads. Today's applications need practical adaptive filters that can offer strong theoretical guarantees and high performance independent of the data distribution to quickly and efficiently perform complex analyses on large-scale data.

§ ACKNOWLEDGMENTS

This research is funded in part by

NSF grant OAC 2339521.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Almeida et al(2007)]
authorpersonPaulo Sérgio Almeida,
personCarlos Baquero, personNuno Preguiça,
and personDavid Hutchison. year2007.
Scalable Bloom filters.
journalJournal of Information Processing Letters
volume101, number6 (year2007),

[Alsubaiee et al(2014)]
authorpersonSattam Alsubaiee,
personAlexander Behm, personVinayak Borkar,
personZachary Heilbron, personYoung-Seok Kim,
personMichael J Carey, personMarkus Dreseler, and
personChen Li. year2014.
Storage management in AsterixDB.
journalProceedings of the VLDB Endowment
volume7, number10 (year2014),

[Apache([n. d.])]
year[n. d.].

authorpersonAustin Appleby.
titleSMHasher source code in C++.

[Beame et al(2014)]
authorpersonPaul Beame, personParaschos
Koutris, and personDan Suciu.
Skew in Parallel Query Processing. In
booktitleProceedings of the 33rd ACM SIGMOD-SIGACT-SIGART
Symposium on Principles of Database Systems (Snowbird, Utah, USA)
(seriesPODS '14). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Bender et al(2021)]
authorpersonMichael A. Bender, personRathish
Das, personMartín Farach-Colton, personTianchi
Mo, personDavid Tench, and personYung Ping Wang.
Mitigating False Positives in Filters: to Adapt or
to Cache?. In booktitleProc. 2nd Symposium on Algorithmic
Principles of Computer System (APoCS).

[Bender et al(2018)]
authorpersonMichael A. Bender, personMartin
Farach-Colton, personMayank Goswami, personRob
Johnson, personSamuel McCauley, and personShikha
Singh. year2018.
Bloom Filters, Adaptivity, and the Dictionary
Problem. In booktitleProc. 59th Annual IEEE Symposium on
Foundations of Computer Science (FOCS). addressParis, France,

[Bender et al(2012a)]
authorpersonMichael A. Bender, personMartin
Farach-Colton, personRob Johnson, personRussell
Kaner, personBradley C. Kuszmaul, personDzejla
Medjedovic, personPablo Montes, personPradeep
Shetty, personRichard P. Spillane, and personErez
Zadok. year2012a.
Don't Thrash: How to Cache Your Hash on Flash.
journalProceedings of the VLDB Endowment
volume5, number11 (year2012).

[Bender et al(2012b)]
authorpersonMichael A Bender, personMartin
Farach-Colton, personRob Johnson, personRussell
Kraner, personBradley C Kuszmaul, personDzejla
Medjedovic, personPablo Montes, personPradeep
Shetty, personRichard P Spillane, and personErez
Zadok. year2012b.
Don't thrash: how to cache your hash on flash.
journalProceedings of the VLDB Endowment
volume5, number11 (year2012),

[Bender et al(2012c)]
authorpersonMichael A. Bender, personMartin
Farach-Colton, personRob Johnson, personRussell
Kraner, personBradley C. Kuszmaul, personDzejla
Medjedovic, personPablo Montes, personPradeep
Shetty, personRichard P. Spillane, and personErez
Zadok. year2012c.
Don't Thrash: How to Cache Your Hash on Flash.
journalPVLDB volume5,
number11 (year2012), pages1627–1637.

authorpersonBurton H. Bloom.
Space/time Trade-offs in Hash Coding With Allowable
journalCommun. ACM volume13,
number7 (year1970), pages422–426.

[Bonomi et al(2006)]
authorpersonFlavio Bonomi, personMichael
Mitzenmacher, personRina Panigrahy, personSushil
Singh, and personGeorge Varghese.
An improved construction for counting Bloom
filters. In booktitleEuropean Symposium on Algorithms
(ESA). Springer, pages684–695.

[Bradley et al(2019)]
authorpersonPhelim Bradley, personHenk C
Den Bakker, personEduardo PC Rocha, personGil
McVean, and personZamin Iqbal.
Ultrafast search of all deposited bacterial and
viral genomic data.
journalNature biotechnology volume37,
number2 (year2019), pages152–159.

[Breslow and Jayasena(2018)]
authorpersonAlex D Breslow and
personNuwan S Jayasena. year2018.
Morton filters: faster, space-efficient cuckoo
filters via biasing, compression, and decoupled logical sparsity.
journalProceedings of the VLDB Endowment
volume11, number9 (year2018),

[Brodal and Fagerberg(2003)]
authorpersonGerth Stølting Brodal and
personRolf Fagerberg. year2003.
Lower Bounds for External Memory Dictionaries. In
booktitleProceedings of the 14th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA). pages546–554.

[Broder and Mitzenmacher(2004)]
authorpersonAndrei Broder and
personMichael Mitzenmacher. year2004.
Network applications of Bloom filters: A survey.
journalInternet Mathematics volume1,
number4 (year2004), pages485–509.

authorpersonCAIDA. year2016.
titleAnonymized Internet Traces 2016.

[Canim et al(2010)]
authorpersonMustafa Canim, personGeorge A
Mihaila, personBishwaranjan Bhattacharjee,
personChristian A Lang, and personKenneth A Ross.
Buffered Bloom Filters on Solid State Storage..
In booktitleProceedings of the International Workshop on
Accelerating Analytics and Data Management Systems Using Modern Processor and
Storage Architectures (ADMS). pages1–8.

[Carter et al(1978)]
authorpersonLarry Carter, personRobert
Floyd, personJohn Gill, personGeorge Markowsky,
and personMark Wegman. year1978.
Exact and approximate membership testers. In
booktitleProceedings of the tenth annual ACM symposium on
Theory of computing. pages59–65.

[Celis et al(1985)]
authorpersonPedro Celis, personPer-Ake
Larson, and personJ Ian Munro.
Robin hood hashing. In
booktitle26th Annual Symposium on Foundations of Computer
Science (FOCS). pages281–288.

[Chang et al(2006)]
authorpersonFay Chang, personJeffrey Dean,
personSanjay Ghemawat, personWilson C. Hsieh,
personDeborah A. Wallach, personMike Burrows,
personTushar Chandra, personAndrew Fikes, and
personRobert E. Gruber. year2006.
Bigtable: A Distributed Storage System for
Structured Data. In booktitle7th USENIX Symposium on
Operating Systems Design and Implementation (OSDI).

[Chazelle et al(2004)]
authorpersonBernard Chazelle, personJoe
Kilian, personRonitt Rubinfeld, and personAyellet
Tal. year2004.
The Bloomier filter: an efficient data structure
for static support lookup tables. In booktitleProceedings
of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. Society
for Industrial and Applied Mathematics, pages30–39.

[Chen et al(2011)]
authorpersonShimin Chen, personAnastasia
Ailamaki, personManos Athanassoulis, personPhillip B
Gibbons, personRyan Johnson, personIppokratis
Pandis, and personRadu Stoica.
TPC-E vs. TPC-C: Characterizing the new TPC-E
benchmark via an I/O comparison study.
journalACM Sigmod Record volume39,
number3 (year2011), pages5–10.

[Cheng et al(2014)]
authorpersonLong Cheng, personSpyros
Kotoulas, personTomas E. Ward, and personGeorgios
Theodoropoulos. year2014.
Robust and Skew-Resistant Parallel Joins in
Shared-Nothing Systems. In booktitleProceedings of the 23rd
ACM International Conference on Conference on Information and Knowledge
Management (Shanghai, China) (seriesCIKM '14).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages1399–1408.

[Chikhi and Rizk(2013a)]
authorpersonRayan Chikhi and
personGuillaume Rizk. year2013a.
Space-efficient and exact de Bruijn graph
representation based on a Bloom filter.
journalAlgorithms for Molecular Biology
volume8, number1 (year2013),

[Chikhi and Rizk(2013b)]
authorpersonRayan Chikhi and
personGuillaume Rizk. year2013b.
Space-efficient and exact de Bruijn graph
representation based on a Bloom filter.
journalAlgorithms for Molecular Biology
volume8, number1 (year2013),

[Chu et al(2014)]
authorpersonJustin Chu, personSara Sadeghi,
personAnthony Raymond, personShaun D Jackman,
personKa Ming Nip, personRichard Mar,
personHamid Mohamadi, personYaron S Butterfield,
personA Gordon Robertson, and personInanc Birol.
BioBloom tools: fast, accurate and memory-efficient
host species sequence screening using bloom filters.
journalBioinformatics volume30,
number23 (year2014), pages3402–3404.

[Clauset et al(2009)]
authorpersonAaron Clauset,
personCosma Rohilla Shalizi, and personMark EJ
Newman. year2009.
Power-law distributions in empirical data.
journalSIAM review volume51,
number4 (year2009), pages661–703.

[Conway et al(2020)]
authorpersonAlexander Conway, personAbhishek
Gupta, personVijay Chidambaram, personMartin
Farach-Colton, personRichard Spillane, personAmy
Tai, and personRob Johnson. year2020.
$\{$SplinterDB$\}$: Closing the Bandwidth Gap for
$\{$NVMe$\}$$\{$Key-Value$\}$ Stores. In booktitle2020
USENIX Annual Technical Conference (USENIX ATC 20).

[Cooper et al(2010)]
authorpersonBrian F Cooper, personAdam
Silberstein, personErwin Tam, personRaghu
Ramakrishnan, and personRussell Sears.
Benchmarking cloud serving systems with YCSB. In
booktitleProceedings of the 1st ACM symposium on Cloud
computing. pages143–154.

[Corominas-Murtra and Solé(2010)]
authorpersonBernat Corominas-Murtra and
personRicard V Solé. year2010.
Universality of Zipf's law.
journalPhysical Review E volume82,
number1 (year2010), pages011102.

[Dayan et al(2017)]
authorpersonNiv Dayan, personManos
Athanassoulis, and personStratos Idreos.
Monkey: Optimal navigable key-value store. In
booktitleProceedings of the 2017 ACM International
Conference on Management of Data. pages79–94.

[Debnath et al(2011)]
authorpersonBiplob Debnath, personSudipta
Sengupta, personJin Li, personDavid J Lilja, and
personDavid HC Du. year2011.
BloomFlash: Bloom filter on flash-based
storage. In booktitleProceedings of the 31st International
Conference on Distributed Computing Systems (ICDCS).

[Debnath et al(2010)]
authorpersonBiplob K Debnath, personSudipta
Sengupta, and personJin Li. year2010.
ChunkStash: Speeding Up Inline Storage
Deduplication Using Flash Memory.. In booktitleProceedings
of the USENIX Annual Technical Conference (ATC).

[Deeds et al(2020)]
authorpersonKyle Deeds, personBrian
Hentschel, and personStratos Idreos.
Stacked filters: learning to filter by structure.
journalProceedings of the VLDB Endowment
volume14, number4 (year2020),

[Dillinger and Manolios(2009)]
authorpersonPeter C. Dillinger and
personPanagiotis (Pete) Manolios.
Fast, All-Purpose State Storage. In
booktitleProceedings of the 16th International SPIN Workshop
on Model Checking Software (Grenoble, France).
publisherSpringer-Verlag, addressBerlin, Heidelberg,

[Duggan et al(2015)]
authorpersonJennie Duggan, personOlga
Papaemmanouil, personLeilani Battle, and
personMichael Stonebraker. year2015.
Skew-Aware Join Optimization for Array Databases.
In booktitleProceedings of the 2015 ACM SIGMOD International
Conference on Management of Data (Melbourne, Victoria, Australia)
(seriesSIGMOD '15). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

[Einziger and Friedman(2016)]
authorpersonGil Einziger and personRoy
Friedman. year2016.
Counting with TinyTable: Every Bit Counts!. In
booktitleProceedings of the 17th International Conference on
Distributed Computing and Networking (Singapore, Singapore)
(seriesICDCN '16). publisherAssociation for
Computing Machinery, addressNew York, NY, USA, Article
articleno27, numpages10 pages.

authorpersonBennett Eisenberg.
On the expectation of the maximum of IID geometric
random variables.
journalStatistics & Probability Letters
volume78, number2 (year2008),

[Esmet et al(2012)]
authorpersonJohn Esmet, personMichael A.
Bender, personMartin Farach-Colton, and
personBradley C. Kuszmaul. year2012.
The TokuFS Streaming File System. In
booktitleProc. 4th USENIX Workshop on Hot Topics in Storage
(HotStorage). addressBoston, MA, USA.

[Fan et al(2014a)]
authorpersonBin Fan, personDave G Andersen,
personMichael Kaminsky, and personMichael D
Mitzenmacher. year2014a.
Cuckoo Filter: Practically Better Than Bloom. In
booktitleProceedings of the 10th ACM International on
Conference on Emerging Networking Experiments and Technologies.

[Fan et al(2014b)]
authorpersonBin Fan, personDave G Andersen,
personMichael Kaminsky, and personMichael D
Mitzenmacher. year2014b.
Cuckoo Filter: Practically Better Than Bloom. In
booktitleProceedings of the 10th ACM International on
Conference on emerging Networking Experiments and Technologies. ACM,

[Fan et al(2000)]
authorpersonLi Fan, personPei Cao,
personJussara Almeida, and personAndrei Z Broder.
Summary cache: A scalable wide-area web cache
sharing protocol.
journalIEEE/ACM Transactions on Networking (TON)
volume8, number3 (year2000),

[Farach-Colton et al(2009)]
authorpersonMartin Farach-Colton,
personRohan J. Fernandes, and personMiguel A.
Mosteiro. year2009.
Bootstrapping a hop-optimal network in the weak
sensor model.
journalACM Transactions on Algorithms
volume5, number4 (year2009).

[Google, Inc.(2015)]
authorpersonGoogle, Inc.
titleLevelDB: A fast and lightweight key/value database
library by Google.
howpublished<http://github.com/leveldb/>, Last
Accessed May 16, 2015.

[Graf and Lemire(2020)]
authorpersonThomas Mueller Graf and
personDaniel Lemire. year2020.
Xor Filters: Faster and Smaller Than Bloom and
Cuckoo Filters.
journalACM J. Exp. Algorithmics
volume25, Article articleno1.5 (dateMarch
year2020), numpages16 pages.

authorpersonTrish Hogan.
Overview of tpc benchmark e: The next generation of
oltp benchmarks. In booktitleTechnology Conference on
Performance Evaluation and Benchmarking. Springer, pages84–98.

[Housley et al(1999)]
authorpersonRussell Housley, personWarwick
Ford, personWilliam Polk, and personDavid Solo.
booktitleInternet X. 509 public key infrastructure
certificate and CRL profile.
typeTechnical Report.

booktitleGoogle search statistics.

[Jackman et al(2017)]
authorpersonShaun D Jackman,
personBenjamin P Vandervalk, personHamid Mohamadi,
personJustin Chu, personSarah Yeo,
personS Austin Hammond, personGolnaz Jahesh,
personHamza Khan, personLauren Coombe,
personRene L Warren, et al
ABySS 2.0: resource-efficient assembly of large
genomes using a Bloom filter.
journalGenome research volume27,
number5 (year2017), pages768–777.

[Jannen et al(2015a)]
authorpersonWilliam Jannen, personJun Yuan,
personYang Zhan, personAmogh Akshintala,
personJohn Esmet, personYizheng Jiao,
personAnkur Mittal, personPrashant Pandey,
personPhaneendra Reddy, personLeif Walsh,
personMichael A. Bender, personMartin
Farach-Colton, personRob Johnson, personBradley C.
Kuszmaul, and personDonald E. Porter.
BetrFS: A Right-Optimized Write-Optimized File
System. In booktitleProc. 13th USENIX Conference on File
and Storage Technologies (FAST) (Santa Clara, CA, USA),
editorpersonJiri Schindler and
personErez Zadok (Eds.). pages301–315.

[Jannen et al(2015b)]
authorpersonWilliam Jannen, personJun Yuan,
personYang Zhan, personAmogh Akshintala,
personJohn Esmet, personYizheng Jiao,
personAnkur Mittal, personPrashant Pandey,
personPhaneendra Reddy, personLeif Walsh,
personMichael A. Bender, personMartin
Farach-Colton, personRob Johnson, personBradley C.
Kuszmaul, and personDonald E. Porter.
BetrFS: Write-Optimization in a Kernel File
journalTransactions on Storage—Special Issue on
USENIX FAST 2015 volume11, number4
(year2015), pages18:1–18:29.

[KG([n. d.])]
authorpersonShalla Secure Services KG.
year[n. d.].
titleShalla’s Blacklists.

[Kopelowitz et al(2021)]
authorpersonTsvi Kopelowitz, personSamuel
McCauley, and personEly Porat.
Support optimality and adaptive cuckoo filters. In
booktitleWorkshop on Algorithms and Data Structures.
Springer, pages556–570.

[Larisch et al(2017)]
authorpersonJames Larisch, personDavid
Choffnes, personDave Levin, personBruce M. Maggs,
personAlan Mislove, and personChristo Wilson.
CRLite: A Scalable System for Pushing All TLS
Revocations to All Browsers. In booktitle2017 IEEE
Symposium on Security and Privacy (SP). pages539–556.

[Lee et al(2021)]
authorpersonDavid J. Lee, personSamuel
McCauley, personShikha Singh, and personMax
Stein. year2021.
Telescoping Filter: A Practical Adaptive Filter.
volume204 (year2021),

authorpersonAllen Leng.
title1 in 2 visitors abandon a website that takes more
than 6 seconds to load.

[Leutenegger and Dias(1993)]
authorpersonScott T Leutenegger and
personDaniel Dias. year1993.
A modeling study of the TPC-C benchmark.
journalACM Sigmod Record volume22,
number2 (year1993), pages22–31.

[Li et al(2022)]
authorpersonMeng Li, personDeyi Chen,
personHaipeng Dai, personRongbiao Xie,
personSiqiang Luo, personRong Gu,
personTong Yang, and personGuihai Chen.
Seesaw Counting Filter: An Efficient Guardian for
Vulnerable Negative Keys During Dynamic Filtering. In
booktitleProceedings of the ACM Web Conference 2022
(Virtual Event, Lyon, France) (seriesWWW '22).
publisherAssociation for Computing Machinery,
addressNew York, NY, USA, pages2759–2767.

[Lohr([n. d.])]
authorpersonSteve Lohr.
year[n. d.].
For Impatient Web Users, an Eye Blink Is Just Too
Long to Wait.
journalThe New York Times
(year[n. d.]).

[Lu et al(2011)]
authorpersonGuanlin Lu, personBiplob
Debnath, and personDavid HC Du.
A Forest-structured Bloom Filter with flash
memory. In booktitleProceedings of the 27th Symposium on
Mass Storage Systems and Technologies (MSST). pages1–6.

[Mitzenmacher et al(2020)]
authorpersonMichael Mitzenmacher,
personSalvatore Pontarelli, and personPedro
Reviriego. year2020.
Adaptive Cuckoo Filters.
journalACM J. Exp. Algorithmics
volume25 (year2020), pages1–20.

[MongoDB([n. d.])]
year[n. d.].

[Mousavi and Tripunitara(2019)]
authorpersonNima Mousavi and personMahesh
Tripunitara. year2019.
Constructing cascade bloom filters for efficient
access enforcement.
journalComputers & Security  volume81
(year2019), pages1–14.

authorpersonMark EJ Newman.
Power laws, Pareto distributions and Zipf's law.
journalContemporary physics volume46,
number5 (year2005), pages323–351.

[Ngo et al(2014)]
authorpersonHung Q Ngo, personChristopher
Ré, and personAtri Rudra.
Skew Strikes Back: New Developments in the Theory
of Join Algorithms.
journalSIGMOD Rec. volume42,
number4 (datefeb year2014),

[O'Neil et al(1996)]
authorpersonPatrick O'Neil, personEdward
Cheng, personDieter Gawlic, and personElizabeth
O'Neil. year1996.
The Log-Structured Merge-Tree (LSM-tree).
journalActa Informatica volume33,
number4 (year1996), pages351–385.

[Pagh et al(2005)]
authorpersonAnna Pagh, personRasmus Pagh,
and personS Srinivasa Rao. year2005.
An optimal Bloom filter replacement. In
booktitleProceedings of the sixteenth annual ACM-SIAM
symposium on Discrete algorithms. Society for Industrial and Applied
Mathematics, pages823–829.

[Pandey et al(2018)]
authorpersonPrashant Pandey, personFatemeh
Almodaresi, personMichael A Bender, personMichael
Ferdman, personRob Johnson, and personRob Patro.
Mantis: A fast, small, and exact large-scale
sequence-search index.
journalCell systems volume7,
number2 (year2018), pages201–207.

[Pandey et al(2017a)]
authorpersonPrashant Pandey, personMichael A
Bender, personRob Johnson, and personRob Patro.
deBGR: an efficient and near-exact representation
of the weighted de Bruijn graph.
journalBioinformatics volume33,
number14 (year2017), pagesi133–i141.

[Pandey et al(2017b)]
authorpersonPrashant Pandey, personMichael A
Bender, personRob Johnson, and personRob Patro.
A general-purpose counting filter: Making every bit
count. In booktitleProceedings of the 2017 ACM
International Conference on Management of Data. pages775–787.

[Pandey et al(2017c)]
authorpersonPrashant Pandey, personMichael A
Bender, personRob Johnson, and personRob Patro.
Squeakr: an exact and approximate k-mer counting
journalBioinformatics volume34,
number4 (year2017), pages568–575.

[Pandey et al(2021)]
authorpersonPrashant Pandey, personAlex
Conway, personJoe Durie, personMichael A Bender,
personMartin Farach-Colton, and personRob Johnson.
Vector quotient filters: Overcoming the time/space
trade-off in filter design. In booktitleProceedings of the
2021 International Conference on Management of Data.

[Pell et al(2012)]
authorpersonJason Pell, personArend Hintze,
personRosangela Canino-Koning, personAdina Howe,
personJames M Tiedje, and personC Titus Brown.
Scaling metagenome sequence assembly with
probabilistic de Bruijn graphs.
journalProceedings of the National Academy of
Sciences volume109, number33
(year2012), pages13272–13277.

[Putze et al(2007)]
authorpersonFelix Putze, personPeter
Sanders, and personJohannes Singler.
Cache-, hash-and space-efficient bloom filters. In
booktitleInternational Workshop on Experimental and
Efficient Algorithms. pages108–121.

[Qiao et al(2014)]
authorpersonYan Qiao, personTao Li, and
personShigang Chen. year2014.
Fast Bloom Filters and Their Generalization.
journalIEEE Transactions on Parallel and Distributed
Systems (TPDS) volume25, number1
(year2014), pages93–103.

[Reagen et al(2017)]
authorpersonBrandon Reagen, personUdit
Gupta, personRobert Adolf, personMichael M
Mitzenmacher, personAlexander M Rush, personGu-Yeon
Wei, and personDavid Brooks. year2017.
Weightless: Lossy weight encoding for deep neural
network compression.
journalarXiv preprint arXiv:1711.04686

[Reviriego et al(2021a)]
authorpersonPedro Reviriego, personAlfonso
Sánchez-Macián, personStefan Walzer, and
personPeter C. Dillinger. year2021a.
titleApproximate Membership Query Filters with a False
Positive Free Set.

[Reviriego et al(2021b)]
authorpersonPedro Reviriego, personAlfonso
Sánchez-Macián, personStefan Walzer, and
personPeter C. Dillinger. year2021b.
titleApproximate Membership Query Filters with a False
Positive Free Set.

[RocksDB([n. d.])]
RocksDB year[n. d.].
howpublished<https://rocksdb.org/>, Last Accessed Oct.
15, 2022.

[Rozov et al(2014)]
authorpersonRoye Rozov, personRon Shamir,
and personEran Halperin. year2014.
Fast lossless compression via cascading Bloom
journalBMC Bioinformatics  volume15

[Salikhov et al(2014)]
authorpersonKamil Salikhov, personGustavo
Sacomoto, and personGregory Kucherov.
Using cascading Bloom filters to improve the memory
usage for de Brujin graphs.
journalAlgorithms for Molecular Biology
volume9, number1 (year2014),

[ScyllaDB([n. d.])]
year[n. d.].

[Solomon and Kingsford(2016)]
authorpersonBrad Solomon and personCarl
Kingsford. year2016.
Fast search of thousands of short-read sequencing
journalNature biotechnology volume34,
number3 (year2016), pages300.

[Stranneheim et al(2010)]
authorpersonHenrik Stranneheim, personMax
Käller, personTobias Allander, personBjörn
Andersson, personLars Arvestad, and personJoakim
Lundeberg. year2010.
Classification of DNA sequences using Bloom
journalBioinformatics volume26,
number13 (year2010), pages1595–1600.

[Sun et al(2016)]
authorpersonBo Sun, personMitsuaki Akiyama,
personTakeshi Yagi, personMitsuhiro Hatada, and
personTatsuya Mori. year2016.
Automating URL blacklist generation with similarity
search approach.
journalIEICE TRANSACTIONS on Information and
Systems volume99, number4 (year2016),

[Tripunitara and Carbunar(2009)]
authorpersonMahesh V. Tripunitara and
personBogdan Carbunar. year2009.
Efficient Access Enforcement in Distributed
Role-Based Access Control (RBAC) Deployments. In
booktitleProceedings of the 14th ACM Symposium on Access
Control Models and Technologies (Stresa, Italy)
(seriesSACMAT '09). publisherAssociation for
Computing Machinery, addressNew York, NY, USA,

authorpersonDavid Wajc.
titleNegative Association - Definition, Properties, and

[Wang et al(2014)]
authorpersonPeng Wang, personGuangyu Sun,
personSong Jiang, personJian Ouyang,
personShiding Lin, personChen Zhang, and
personJason Cong. year2014.
An efficient design and implementation of
LSM-tree based key-value store on open-channel SSD. In
booktitleProceedings of the 9th European Conference on
Computer Systems (EuroSys). pages16:1–16:14.

[Yuan et al(2017)]
authorpersonJun Yuan, personYang Zhan,
personWilliam Jannen, personPrashant Pandey,
personAmogh Akshintala, personKanchan Chandnani,
personPooja Deo, personZardosht Kasheff,
personLeif Walsh, personMichael A Bender,
et al year2017.
Writes wrought right, and other adventures in file
system optimization.
journalACM Transactions on Storage (TOS)
volume13, number1 (year2017),

[Yuan et al(2016)]
authorpersonJun Yuan, personYang Zhan,
personWilliam Jannen, personPrashant Pandey,
personAmogh Akshintala, personKanchan Chandnani,
personPooja Deo, personZardosht Kasheff,
personLeif Walsh, personMichael A. Bender,
personMartin Farach-Colton, personRob Johnson,
personBradley C. Kuszmaul, and personDonald E.
Porter. year2016.
Optimizing Every Operation in a Write-Optimized
File System. In booktitleProc. 14th USENIX Conference on
File and Storage Technologies (FAST).

[Zhang and Ross(2022)]
authorpersonWangda Zhang and
personKenneth A. Ross. year2022.
Exploiting Data Skew for Improved Query
journalIEEE Transactions on Knowledge and Data
Engineering volume34, number5
(year2022), pages2176–2189.

[Zhu et al(2008)]
authorpersonBenjamin Zhu, personKai Li,
and personR Hugo Patterson. year2008.
Avoiding the Disk Bottleneck in the Data Domain
Deduplication File System. In booktitleProceedings of the
6th USENIX Conference on File and Storage Technologies (FAST).