††thanks: Pedro Reviriego is with Universidad Carlos III de Madrid, Leganés
28911, Madrid, Spain. email<EMAIL_ADDRESS>Alfonso Sánchez-
Macián is with Universidad Antonio de Nebrija, 28040, Madrid, Spain. email:
<EMAIL_ADDRESS>Stefan Walzer is with University of Cologne,
Cologne, Germany. email<EMAIL_ADDRESS>Peter C. Dillinger is
with Facebook, Inc., Seattle, Washington, USA. email<EMAIL_ADDRESS>
# Approximate Membership Query Filters with a False Positive Free Set

Pedro Reviriego, Alfonso Sánchez-Macián, Stefan Walzer and Peter C. Dillinger

###### Abstract

In the last decade, significant efforts have been made to reduce the false
positive rate of approximate membership checking structures. This has led to
the development of new structures such as cuckoo filters and xor filters.
Adaptive filters that can react to false positives as they occur to avoid them
for future queries to the same elements have also been recently developed. In
this paper, we propose a new type of static filters that completely avoid
false positives for a given set of negative elements and show how they can be
efficiently implemented using xor probing filters. Several constructions of
these filters with a false positive free set are proposed that minimize the
memory and speed overheads introduced by avoiding false positives. The
proposed filters have been extensively evaluated to validate their
functionality and show that in many cases both the memory and speed overheads
are negligible. We also discuss several use cases to illustrate the potential
benefits of the proposed filters in practical applications.

##  1 Introduction

Approximate membership checking is widely used in many computing applications
[1]. For example, to accelerate access to key-value stores [2] or to data
stored in external memory [3]. Approximate membership checking is also used in
networking, for example for packet classification [4]. The most frequently
used data structure for approximate membership queries is probably the Bloom
filter [5] for which many enhancements and optimizations have been proposed
[6]. A Bloom filter maps an element to a set of bits in a bit vector using a
group of hash functions and sets those bits to one on insertion and checks if
they are one when checking membership. This construction ensures that there
are no false negatives. Instead, false positives can occur when other elements
have set to one the positions checked by a given element. Therefore, the
approximate checking manifests as a false positive probability for elements
not originally added to the filter [5]. This is the price paid for having a
much smaller and faster representation of the set. Alternative approximate
membership querying structures have also been proposed like the cuckoo filter
[7] or more recently the xor filter [8] that can achieve smaller false
positive probability with the same memory budget in some settings.

Since false positives are the main drawback of all these approximate
membership querying structures, significant efforts have been made to reduce
them for example by adapting the filter to react to false positives as they
occur [9],[10]. Another approach is to design filters that are false positive
free when the set stored is small and from elements taken also from a small
universe [11]. Unfortunately, this limits the use of the false positive free
filters to very small sets having only a few elements. In this paper we
introduce a new type of filters that are false positive free on a subset of
the negative elements. That is, the proposed filters do suffer false positives
over the entire universe but we can select a set of negatives, that we assume
can be larger than the set of elements stored in the filter, that will not
suffer false positives. This is useful to reduce the observed false positive
rate by including the most commonly accessed negative elements on that set.

To better understand the problem we address in this paper, let us consider one
of the initial applications of a Bloom filter, storing the set of correct
words to check their spelling [12]. In more detail, all the words of the
dictionary are stored in the Bloom filter and used to check written words so
that an error is flagged when the Bloom filter returns a negative. This design
ensures that valid words are always classified as correct but there may be
some invalid words that are not detected. An interesting observation is that
there are some common misspellings that occur frequently for which it would be
beneficial not having false positives on the filter. However, the Bloom filter
treats all the words that are not in the dictionary equally having all the
same false positive probability.

In this paper we consider this problem: given two disjoint sets $S$ and $T$ of
elements that belong to universe $U$, design a false negative free filter that
stores $S$ and has no false positives for elements in $T$ and a low false
positive probability for the rest of the elements that are neither in $S$ nor
in $T$. That is, our goal is to design a filter for which elements in $S$ are
guaranteed to query positive, elements in $T$ are guaranteed to query
negative, and most other elements query negative. We denote these filters are
false positive free on a set ($T$) that is possibly larger than $S$. Obviously
such a filter could be used with a set $S$ of the words in the dictionary and
a set $T$ with the common misspellings to make the filter based spell checker
more effective. These filters with a false positive free set would also be
beneficial in applications such as filtering for database queries [2], in
memory key-value stores [3], for filtering of URLs[13] or in lightweight
Bitcoin nodes [14] among many others as will be discussed in several case
studies in section 5.

The rest of the paper is organized as follows, section 2 covers the
preliminaries by briefly reviewing existing approximate membership query
filters, the efforts to reduce their false positive rate and providing an
overview of xor probing filters that are used to build our proposed filters.
The proposed filters are presented and analyzed in section 3. The evaluation
of the filters is presented in section 4 that also compares them with existing
filters. Section 5 discusses several use cases where the use of the proposed
filters would be beneficial. Finally, the paper ends in section 6 with the
conclusion and some ideas for future work.

##  2 Preliminaries

###  2.1 Approximate membership query filters

As discussed in the introduction, approximate membership checking is widely
used in computing and networking and different structures have been proposed
to implement it. The most well-known and commonly used option is Bloom filters
[6] but other alternatives like the Bloomier filter [15], cuckoo filters [7]
or xor filters have been proposed in the last two decades [8]. In all cases,
elements are mapped to several positions on an array or table using a set of
hash functions $h_{1}(x),h_{2}(x),\ldots,h_{k}(x)$. The contents of those
positions are used to check the membership. The filters can be classified
according to how the checking is done [16]:

  * •

And probing: the logical And of the positions is used to check membership.
This is the case of the Bloom filter in which an array of bits is used and
true is returned when the and of positions $h_{1}(x),h_{2}(x),\ldots,h_{k}(x)$
is a one and a false is returned otherwise.

  * •

Or probing: the logical Or of the matching of the contents of the positions
with a value $v(x)$ derived from the element is used to detect positives. This
is the scheme used in the cuckoo filter that computes a fingerprint per
element and compares it with the fingerprints stored in the positions and if
any of them matches the element’s fingerprint true is returned [4].

  * •

Xor probing: the logical Xor of the positions is used to compute a value
$F_{xor}(x)$ that is used to detect positives. A value derived from the
element $v(x)$ is compared with $F_{xor}(x)$ and true is return on a match and
false otherwise. This is the scheme used in the xor and ribbon filters
[8],[16].

Each filter type and construction has advantages and disadvantages. For
example, Bloom filters are the simplest to construct and their false positive
probability (FPP) degrades gracefully if the number of elements added does not
match what was predicted and optimized for. However, they do not support
deletions unless counters instead of bits are used and their FPP is large in
some settings [6]. Another advantage of Bloom filters is that they can be
implemented on a single memory access [17], so can be made faster than cuckoo
filters in software [18]. While cuckoo filters support removals and have lower
FPP in many settings, space efficiency with low FPP depends on high occupancy
but not so high to fail insertion [4]. Finally, xor filters [8] and ribbon
filters [16] achieve better FPP for the same memory budget in many cases, with
good speed, but do not support dynamic insertions and removals, limiting their
use to _static_ filtering applications, in which real time updates to the set
are not needed. In summary, the best filter configuration depends on the
application requirements and implementation platform.

###  2.2 Reducing the false positive probability of filters

First, when the universe of elements is sufficiently small, it is possible to
represent an exact set with no false positives, using less space than a
generic filter with low but non-zero FPP, e.g. [19]. It is even possible for
exact sets to degrade into filters with non-zero FPP as more elements are
added [11, 20, 21]. We expect only a small minority of applications to have
universes sufficiently small to justify these approaches. The rest of the
paper assumes a large or infinite universe.

One of the main performance parameters of approximate query filters is the FPP
that they achieve for a given memory budget and many efforts have been made to
reduce it. For example, for Bloom filters optimizations like the Variable
Increments Bloom filter have been proposed to reduce the FPP [5]. Indeed, one
of the main motivations to develop cuckoo, xor and ribbon filters was to
improve space efficiency in the FPP.

Another strategy is to reduce selectively the FPP only for elements that are
frequently accessed. This can be done in the Bloom filter by setting some
positions to zero in the array that correspond to false positive elements that
are frequently accessed. This however introduces false negatives for other
elements [22]. The knowledge of elements that are frequently accessed may not
be known in advanced, and in that scenario filters have to remove false
positives adaptively as they occur [9]. For example, Adaptive Cuckoo Filters
(ACFs) change the stored fingerprints to remove false positives as they occur
[10].

As discussed in the introduction, in this paper we focus on the design of
filters that are false positive free on a set of elements $T$ while allowing
false positives for the rest of the negative elements in the universe. To the
best of our knowledge efficient designs for such filters when $T$ is large
have not been proposed before. False positives can be avoided by using a
Bloomier filter [15] but each such false positive requires an entry on the
filter thus incurring a large cost when $T$ is large. There have also been
efforts to reduce the false positives for a given subset of frequently
accessed elements like for example [23],[10] but not to completely avoid them
by construction.

###  2.3 Xor probing filters

An xor probing filter can be seen at a high level as a function that for a
given element $x$ returns a value $F_{xor}(x)$ that is obtained by performing
the xor of several positions on the filter given by hash functions
$h_{1}(x),h_{2}(x),\ldots,h_{k}(x)$. The filter is constructed so that
$F_{xor}(x)=v(x)$ holds when an element $x$ has been inserted into the filter,
where $v(x)$ is a fingerprint computed on the element. Instead when the
element has not been inserted on the filter, in most cases $F_{xor}(x)\neq
v(x)$ and the probability of having $F_{xor}(x)=v(x)$ would be approximately
$2^{-r}$, where $r$ is the number of bits in $v(x)$.

A lookup on an xor probing filter is a simple operation that just requires
accessing positions $h_{1}(x),h_{2}(x),\ldots,h_{k}(x)$, computing the xor of
their values to obtain $F_{xor}(x)$ and comparing it with $v(x)$. On a match,
true is returned and false is returned otherwise. The construction of xor
probing filters is more complex and needs to be precomputed, so these filters
are not suitable for applications that need to perform frequent updates on the
stored elements. Two constructions have been proposed so far, the xor filter
[24, 8] and the ribbon filter [16]. The first one usually probes $k=3$ random
positions while the second probes many more positions in a small window. A
standard xor filter uses $1.23\cdot r$ bits of memory per element, already a
significant improvement on Bloom filter’s best case of $1.44\cdot r$. With
some elaboration [25, 26], both constructions approach information-theoretic
limits, requiring as little as $1.01\cdot r$ bits with negligible additive
overheads. This makes them the most memory efficient approximate membership
query structures to date for many settings. In the following, we assume that
in general an $r$ bit xor probing filter requires $(1+\epsilon)\cdot r$ memory
bits per element.

In the rest of the paper we will use xor probing filters to construct our
filters with false positive free sets in a general form. The specifics of xor
filter constructions will be covered in the evaluation section when analyzing
the practical performance of our filters. Before presenting the proposed
filters in the next section, the main notations used in the rest of the paper
are summarized in Table 1.

Table 1: Summary of main notations Symbol | Meaning
---|---
$U$ | universe of elements
$S$ | set stored in the filter
$T$ | set for which false positives must be avoided
$F$ | residual set for which false positives must be avoided
$r$ | number of bits of the base xor filter
$c$ | number of subfilters of the second filter in the Integrated Filter (IF) design
$a$ | number of bits added to the first filter
$\mathrm{FPP}$ | false positive probability
$\epsilon$ | memory overhead required by the xor probing filter

##  3 Avoiding False Positives for a given set

As discussed in the introduction, our goal is to design filters that provide
approximate membership checking for a set $S$ ensuring that all elements of
set $T$ return a negative on the filter. In the following subsections we first
formally define the target filters, analyze their lower bound memory
requirements theoretically and discuss briefly several potential options to
construct the filters. Then, the proposed constructions are presented starting
from a naive implementation that is used to illustrate the main ideas and the
different constructions are analyzed theoretically. Finally, some potential
optimizations for the proposed constructions are briefly discussed.

###  3.1 Filters with a False Positive Free Set

For a universe $U$ and a number $\mathrm{FPP}\in[0,1]$, a filter with a false
positive free set is a randomised data structure constructed from two disjoint
sets $S,T\subseteq U$. When queried for $x\in U$, it returns a bit
$q(x)\in\\{0,1\\}$ such that

  * (i)

$q(x)=1$ for all $x\in S$,

  * (ii)

$q(x)=0$ for all $x\in T$,

  * (iii)

$\Pr[q(x)=1]\leq\mathrm{FPP}$ for all $x\in U\setminus(S\cup T)$, where
“$\Pr$” refers to randomness used in the construction algorithm.

Note how this is a generalisation of several important problems. For
$T=\emptyset$ we obtain an ordinary filter. For $U=S\cup T$ (or
$\mathrm{FPP}=0$) we obtain a set data structure. If we omit condition (iii)
or $\mathrm{FPP}\geq 0.5$ then the problem has been referred to as the
_relative membership problem_ [27] and calls for a static function with
$1$-bit values.111Unless $|S|\approx|T|$, a _compressed_ static function
should be used for space efficiency [27, 25, 28]. We do not claim any
improvements for these widely studied special cases. From now on let $u=|U|$,
$s=|S|$ and $t=|T|$. Our main interest concerns cases where $s$ and $t$ are
both large, $u\gg s,t$ and $\mathrm{FPP}$ is bounded away from $0$ and $<0.5$.

###  3.2 Space Lower Bound

Using arguments resembling those in [29, Chapter 2.3] for perfect hashing and
in [30] for Bloom filters, we now derive a space lower bound for filters with
a false positive free set. Such a data structure implies a related data
structure with essentially the same space consumption that satisfies (i), (ii)
and the more combinatorial (and slightly weaker) property

$\tfrac{1}{u-s-t}|\\{x\in U\setminus(S\cup T)\mid
q(x)=1\\}|=\mathrm{FPP}^{\prime}$ (iii’)

for some $\mathrm{FPP}^{\prime}\leq\mathrm{FPP}$. The number $I$ of possible
inputs $(S,T)$ for such a data structure is

$I=\binom{u}{s}\binom{u-s}{t}=\frac{u!}{s!\,t!\,(u-s-t)!}$

Different inputs are not necessarily handled differently. Indeed, after
construction, the data structure returns $1$ for a set $P$ of
$s+\mathrm{FPP}^{\prime}\cdot(u-s-t)$ elements of $U$ and $0$ for $U\setminus
P$. As such, a single memory state is suitable for all inputs where
$S\subseteq P$ and $T\subseteq U\setminus P$, i.e. for

$W=\binom{s+\mathrm{FPP}^{\prime}\cdot(u-s-t)}{s}\binom{(1-\mathrm{FPP}^{\prime})\cdot(u-s-t)+t}{t}$

inputs. By the pigeon hole principle, at least $I/W$ memory states are
possible after construction and hence $\log_{2}(I/W)$ bits of memory are
required. To obtain a simple bound, we assume that $u$ is large, more
precisely $\min(\mathrm{FPP}^{\prime},1-\mathrm{FPP}^{\prime})\cdot
u=\omega(\max(s^{2},t^{2}))$. In that case

$\displaystyle\log_{2}(I/W)$
$\displaystyle=\log_{2}\big{(}\tfrac{u^{s+t}}{s!t!}/(\tfrac{(\mathrm{FPP}^{\prime}u)^{s}}{s!}\cdot\tfrac{((1-\mathrm{FPP}^{\prime})u)^{t}}{t!})\big{)}+o(1)$
$\displaystyle=\log_{2}((\tfrac{1}{\mathrm{FPP}^{\prime}})^{s}\cdot(\tfrac{1}{1-\mathrm{FPP}^{\prime}})^{t})+o(1)$
$\displaystyle=s\cdot\log_{2}(\tfrac{1}{\mathrm{FPP}^{\prime}})+t\cdot\log_{2}(\tfrac{1}{1-\mathrm{FPP}^{\prime}})+o(1).$

When $\mathrm{FPP}^{\prime}$ is small a good approximation is obtained using
$\ln(\frac{1}{1-\varepsilon})\geq\varepsilon$, namely

$\log_{2}(I/W)\geq
s\cdot\log_{2}(\tfrac{1}{\mathrm{FPP}^{\prime}})+t\cdot\mathrm{FPP}^{\prime}\cdot\log_{2}(\mathrm{e})+o(1).$

A lower bound for a filter with a false positive free set is now obtained by
choosing $\mathrm{FPP}^{\prime}\leq\mathrm{FPP}$ that minimises space
consumption, i.e.

$\textsc{space}\geq\min\limits_{\mathrm{FPP}^{\prime}\leq\mathrm{FPP}}s\cdot\log_{2}(\tfrac{1}{\mathrm{FPP}^{\prime}})+t\cdot\mathrm{FPP}^{\prime}\cdot\log_{2}(\mathrm{e})+o(1).$
(1)

Note that this suggests two regimes: When
$t/s\ll\tfrac{\log_{2}(1/\mathrm{FPP})}{\mathrm{FPP}}$ then using
$\mathrm{FPP}^{\prime}=\mathrm{FPP}$ is optimal and the term depending on $t$
is negligible. We recover essentially the lower bound
$s\cdot\log_{2}(1/\mathrm{FPP}^{\prime})$ for ordinary filters. When $t/s$ is
larger, however, the minimum is attained for a value
$\mathrm{FPP}^{\prime}<\mathrm{FPP}$. In particular the most compact filter
with false positive free set should be expected to have a false positive rate
$\mathrm{FPP}^{\prime}$ _smaller_ than required. We will reencounter this
phenomenon in our implementation which will, up to a constant factor, achieve
the lower bound (1).

###  3.3 High-level Design Strategies

Before developing our preferred solutions, let us discuss a few high-level
strategies that come to mind.

  * •

One might construct a filter for $S$ and—as an afterthought—retouch it [22]
such that no element from $T$ is a false positive, but without introducing
false negatives. Applied to Bloom filters and xor filters, this plan seems
hopeless. It is plausible, however, that it can work for adaptive filters. For
example, in adaptive cuckoo or quotient filters [10],[9] by adapting the
filter to the $T$ set before using the filter. The same applies to more recent
variants of adaptive cuckoo filters [31] where stored fingerprints that cause
a false positive can be moved to alternative positions where they do not.
However, removing one false positive has a chance of creating false positives
for different elements in $T$, making it unclear how to guarantee the
simultaneous removal of all false positives for $T$ efficiently. Even if this
alternative works, our favoured approach is simpler and more space efficient.

  * •

One could construct a cascade of filters as suggested for a similar setting in
[15]. First, construct a filter for $S$. Then, construct a filter for those
elements from $T$ that are false positives of the first filter. Then,
construct a filter for those elements from $S$ that are false positives of the
second filter (making them “false false positives”) and so on resulting in a
sequence of ever smaller filters, each correcting the mistakes of the previous
one. This would likely work, but our favoured approach is simpler and has
better worst-case query time.

  * •

One could use a $1$-bit static function with support $S\cup T$ and value $1$
for $x\in S$ and $0$ for $x\in T$. Unfortunately, most constructions return a
uniformly random bit for $x\in U\setminus(S\cup T)$, giving us no easy way to
control the false positive rate. An exception might be the construction from
[27] where the output distribution for inputs $x\in U\setminus(S\cup T)$
coincides with the output distribution for random elements from the support.
This yields $\mathrm{FPP}=\tfrac{s}{s+t}$ at first, but could plausibly be
tuned for any false positive rate. We have not pursued this approach because
it is rather complicated with no practical implementation that we know of.

  * •

Bloomier filters [15] _can_ solve the problem at hand. Even though we improve
upon the idea later in the paper, it is instructive to consider it in some
detail in Subsection 3.4.

Our favoured approach involves aspects of some of these ideas, combining a
filter with a static function. Since xor-probing is suitable to implement both
of these sub-tasks, it is the natural probing strategy for us to use.

###  3.4 Naive construction

As discussed in the previous section, an xor probing filter ensures that for
each element $x$ inserted, the filter computes a value $F_{xor}(x)$ that is
equal to $v(x)$. Indeed a positive is returned when $F_{xor}(x)=v(x)$ and a
negative otherwise. Therefore, to ensure that an element $x$ returns a
negative, we can insert it on the filter with a value $v_{n}(x)\neq v(x)$.
Then when searching for $x$ the filter will return $F_{xor}(x)=v_{n}(x)$ that
is different from $v(x)$ so a negative is obtained. This is illustrated in
Figure 1. This naive construction can also be implemented with a Bloomier
filter [15] using two categories—one for positives and one for negatives—and
storing $S$ and $T$ on each of them respectively.

Figure 1: Diagram of the naive construction of a filter with a false positive
free set $T$.

This simple scheme can be used to insert all the elements in $T$ with values
different from their $v(x)$ values and thus avoid false positives for $T$.
However, this comes at a large cost in terms of memory as now the filter
stores $|S\cup T|$ elements and thus requires approximately:

$M_{naive}=(s+t)\cdot(1+\epsilon)\cdot r$ (2)

memory bits for a filter with a false positive rate of $2^{-r}$. This means
that ensuring that each element on $T$ is not a false positive requires
$(1+\epsilon)\cdot r$ bits, the same memory as for the elements in $S$. On the
other hand, the check operation on the filter remains the same and thus
removing the false positives has no implications on speed.

Finally, let us consider the False Positive Probability (FPP) for elements of
the universe $U$ that are not in $S\cup T$. For those, the value returned by
the filter $F_{xor}(x)$ would look like a uniformly distributed random value
and thus the probability that it matches the value of the element $v(x)$ and
thus a false positive is obtained will be approximately $2^{-r}$.

###  3.5 Two filters (TF) construction

The memory footprint can be significantly reduced by observing that to ensure
that an element is not a false positive, using a one bit filter suffices.
Therefore, an $r-1$ bit filter can be used to store the elements in $S$ and a
second one bit filter to store the elements in $S\cup T$ (the elements in $T$
with their negated bit value). In fact, this second one-bit filter can be seen
as a static function that maps elements in $S$ to 1 and elements in $T$ to 0.
Based on a subtle observation, not all elements in $T$ have to be inserted on
the second filter. Indeed only the elements in $T$ that return a false
positive on the first filter need to be inserted on the second filter. Let us
denote as $F$ the set formed by the elements in $T$ that return a false
positive in the first filter, and let $f=|F|$. Then only the elements in $F$
have to be inserted on the second filter and $f\approx\frac{t}{2^{r-1}}$, so
$F$ is typically much smaller than $T$. Therefore, this scheme would require:

$M_{TF_{initial}}=s\cdot(1+\epsilon)\cdot(r)+f\cdot(1+\epsilon)$ (3)

memory bits and can be expressed as a function of $T$ as:

$M_{TF_{initial}}=s\cdot(1+\epsilon)\cdot(r)+\frac{t}{2^{r-1}}\cdot(1+\epsilon)$
(4)

which is much lower than that of the naive construction (using assumption
$r>1$ from assumption $\mathrm{FPP}<0.5$).

Looking carefully at the second term of equation 3, it can be observed that
each element that needs to be removed requires $(1+\epsilon)$ bits. This is
not efficient when $\frac{t}{2^{r-1}}>2\cdot s$. To explain why, for example,
let us consider that $t=3\cdot 2^{r-1}\cdot s$ so that $f=3\cdot s$, then we
would need $(1+\epsilon)\cdot(r+3)\cdot s$ memory bits. Instead, let us
consider an alternative configuration in which the first filter has $r$ bits
instead of $r-1$ bits. Then, we would have $f=\frac{3}{2}\cdot s$ and only
$(1+\epsilon)\cdot(r+2.5)\cdot s$ memory bits are needed. This shows that when
$\frac{t}{2^{r-1}}>2\cdot s$, it is more efficient to add bits to the first
filter using $r^{\prime}=r+a$ such that $\frac{t}{2^{r+a-1}}<2\cdot s$. This
is so because by adding an additional bit to the first filter we reduce in
half the size of $F$ and thus when $F$ is large this is more efficient than
storing all the elements in $F$ in the second filter. Therefore, in the TF
construction when that occurs, $a=\lceil\log_{2}(\frac{t}{2^{r-1}\cdot
s})\rceil-1$ bits are added to the first filter to reduce the size of $F$.
This generalized TF construction is illustrated in Figure 2.

Figure 2: Diagram of the Two Filter (TF) construction with a false positive
free set $T$.

The memory requirements are now:

$M_{TF}=s\cdot(1+\epsilon)\cdot(r+a)+f\cdot(1+\epsilon)$ (5)

that can be expressed as a function of $T$ as:

$M_{TF}=s\cdot(1+\epsilon)\cdot(r+a)+\frac{t}{2^{r+a-1}}\cdot(1+\epsilon)$ (6)

so much smaller than in the naive construction. The FPP would be approximately
$2^{-(r+a)}$ so the use of additional bits on the first filter has the side
benefit of reducing the FPP.

A drawback of the TF construction is the speed overhead of checking two
filters for some queries, specifically positive and a fraction of negative
queries. This would be acceptable in many cases as negative queries motivate
the choice to use a filter.

###  3.6 Integrated filters (IF) construction

The two filters construction is effective to reduce the memory footprint
(space) but introduces other overheads (time) that may be an issue in some
applications. Therefore, it would be beneficial to have a construction that is
as fast as a single filter and is more memory efficient than the naive
construction requiring $(s+t)\cdot(1+\epsilon)$ positions. By increasing the
number of positions in filter 1 to match filter 2, from $s\cdot(1+\epsilon)$
to $(s+f)\cdot(1+\epsilon)$ positions, both filters can be fully integrated in
the same data structure. And by using the same position hash functions for
both222This leads to potential correlation in construction success
probability, not in false positive probability., the bits for both filters can
be concatenated on a single larger entry per position, so that querying both
involves no more memory lookups than a single filter query. This scheme is
illustrated in Figure 3 and would require a memory footprint of:

$M_{IF}|_{c=1}=(s+\frac{t}{2^{r+a-1}})\cdot(1+\epsilon)\cdot(r+a)$ (7)

In this case, adding bits to the first filter is more beneficial as the cost
of the elements in $F$ is larger. The analytical derivation of the optimal
value for $a$ becomes more complex as it now appears twice on the equation but
it can be easily found by computing equation 7 starting with $a=0$ and
increasing $a$ until the memory required increases. Alternatively, when $r$ is
much larger that $a$, we can approximate $r+a$ with $r$ and then the condition
to minimize the memory becomes becomes $\frac{t\cdot(r-1)}{2^{r+a-1}}>2\cdot
s$ and thus:

$a=\lceil\log_{2}(\frac{t\cdot(r-1)}{2^{r-1}\cdot s})\rceil-1$ (8)

This results in a memory overhead that is larger than that of the TF approach,
especially when the initial $F$ is large.

Figure 3: Diagram of the Integrated Filter (IF) construction of a filter with
a false positive free set $T$ when $c=1$. Filters 1 and 2 use the same hash
functions to compute the addresses to access and have the same size.

To reduce the overhead, the previous construction can be generalized as shown
in Figure 4. It can be seen that now $c$ bits are used for the second filter
that is decomposed in $c$ subfilters each storing a subset of the elements in
$S\cup F$. As in the initial construction, the bits are concatenated per
position, each having $r+a-1$ bits for the first filter and $c$ for the
second. In more detail, another hash function is used to compute $c(x)$ that
selects the subfilter in the second filter. Therefore each subfilter stores
approximately $\frac{|S\cup F|}{c}$ elements. When this is smaller than $s$,
the memory footprint is:

$M_{IF}|_{c>1}=s\cdot(1+\epsilon)\cdot(r+c-1).$ (9)

The minimum value of $c$ that can be used to ensure that $\frac{|S\cup
F|}{c}<s$ given a set $T$ can be computed as:

$c_{min}=1+\big{\lceil}\frac{t}{s\cdot 2^{r-1}}\big{\rceil}$ (10)

So the minimum memory needed is given by:

$M_{IF}|_{c_{min}}=|S|\cdot(1+\epsilon)\cdot(r+\big{\lceil}\frac{t}{|S|\cdot
2^{r-1}}\big{\rceil})$ (11)

Figure 4: Diagram of the Integrated Filter (IF) construction of a filter with
a false positive free set $T$ when $c=2$. Filter 2 is composed of two
subfilters each element $x$ maps to one of them given by $c(x)$.

As in the previous constructions, a subtle observation is that when the value
obtained for $c_{min}$ is larger than two, it is better to increase the value
of $r$ and use $c=2$. This is better seen with an example, let us assume that
$\frac{t}{s\cdot 2^{r-1}}$ is equal to 3.6. Then $c_{min}$ would take a value
of five, so five bits have to be added the filter. Instead if we use
$r^{\prime}=r+2$, then $\frac{t}{s\cdot 2^{r^{\prime}-1}}$ would be 0.9 and
$c_{min}$ would take a value of two, needing in total four bits, so fewer than
the original five. In general, by adding $a$ bits to $r$ to obtain
$r^{\prime}$, the following number of bits would be needed:

$a+1+\big{\lceil}\frac{t}{s\cdot 2^{r+a-1}}\big{\rceil}$ (12)

when this value is lower than that of Equation 10, adding bits to $r$ is more
efficient.

Therefore, the procedure to select the parameters for the IF design is as
follows:

  1. 1.

Determine $c_{min}$ according to equation 10.

  2. 2.

If $c_{min}=2$ no additional bits are needed for $r$, the filter is
implemented with the original value of $c_{min}=2$.

  3. 3.

If $c_{min}>2$ add $a=\lceil\log_{2}(c_{min}-1)\rceil$ bits to $r$ and
recompute equation 10 to obtain the final value of $c_{min}=2$.

  4. 4.

Implement the IF with $r^{\prime}=r+a$ bits on the first filter and $c=2$
subfilters in the second filter.

So, it can be seen that in all cases $c=2$ is used. When $a=1$, for example
when $\frac{t}{s\cdot 2^{r-1}}$ is equal to 1.8, both alternatives require the
same number of bits (four), but adding the bit to $r$ has the side benefit of
reducing the false positive rate for elements that are not in $T$ so it should
be used.

In summary, in the integrated filter construction to reduce the memory
footprint in a given design, the value of $c$ is always fixed to two and $a$
is computed. In terms of lookups, this construction does not introduce
additional memory accesses, only some operations to select and check the
subfilter when needed.

The FPP would also be approximately $2^{-(r+a)}$ so similar to previous
constructions when $a=0$ and lower otherwise.

###  3.7 Analysis

Let us now compare the different filters with a false positive free set (FPFS)
constructions presented in the previous subsections. We consider a set $S$ of
size one million elements, $\epsilon=0.23$, $r=8$ and different sizes of the
FPFS set $T$ and compute the memory required by the three constructions using
the equations derived in the previous subsections. The results are shown in
Figure 5. It can be seen that the naive construction requires much more memory
than the others as the size of $T$ increases confirming that it is not an
efficient construction unless $T$ is very small. The same reasoning applies to
a Bloomier based construction and therefore none of the two is considered
further in the rest of the paper.

Figure 5: Memory bits per element in $S$ to implement the different FPFS
filters for different sizes of $T$ when $r=8$ and for $S$ of size one million
elements.

To better compare the other two constructions, their results are shown in
Figure 6 for $r=8$ and in Figure 7 for $r=16$ that also show lower bound (1).
When $r=8$, TF is the most efficient construction in terms of memory while IF
with $c=1$ is more effective when $T$ is small while the IF with $c>1$ is
better when $T$ is large. As the size of $T$ increases, the memory required
also increases and more bits are added to the first filter. When $r=16$, the
use of memory is similar in most cases (except when $T$ is very large for the
IF with $c=1$) as the size of $F$ is very small (recall that
$c=\frac{t}{2^{r+a-1}}$). Finally it can be seen that the proposed filters are
reasonably close to the lower bound being the difference mostly due to the
$\epsilon$ =23% memory overhead introduced by xor filters [8].

An interesting observation is that the IF construction offers an efficient
alternative for all values of $T$ by selecting the appropriate value of $c$.
Therefore, the integrated construction can be used to implement FPFS filter
with a small memory footprint and lookups that require the same number of
memory accesses as the original xor probing filter from which they are
derived.

Figure 6: Memory bits per element in $S$ required to implement the TF and IF
FPFS filters for different sizes of $T$ when $r=8$ and for $S$ of size one
million elements.  Figure 7: Memory bits per element in $S$ required to
implement the TF and IF FPFS filters for different sizes of $T$ when $r=16$
and for $S$ of size one million elements.

###  3.8 Potential Optimizations

In this section we discuss two potential optimizations for the proposed filter
constructions. The evaluation and further analysis of these optimizations are
left as future work and not considered further in this paper.

####  3.8.1 Hybrid of TF and IF

We observe that a hybrid of the TF and IF approaches could achieve the memory
footprint of TF with the speed of IF for a portion of queries. This could be
useful in speeding up positive queries when TF space efficiency is desired.
Essentially, the hybrid would not round up in computing $c_{min}$ (Equation
10), would separate off and size the $c(x)=2$ subfilter for only $f$ elements,
and would make $c(x)$ a weighted hash, such that $c(x)=1$ for approximately
$s$ random elements of $S\cup F$ and $c(x)=2$ for the approximately $f$
remaining elements.

####  3.8.2 Generalized IF

We observe that when minimal rounding is involved in choosing $c_{min}$
(Equation 10), IF is as memory efficient as TF, as in Figure 6 near
$T/S=10^{2}$. With rounding, only $s+f$ elements are stored where there is
space for $2s$ elements. If an independently hashed $\frac{s-f}{s}$ subset of
elements map to both subfilters, this space can be filled for the purpose of
lowering the false positive rate of elements not in $S\cup T$. Note that to
guarantee false positive freedom, elements in $F$ only need to be added to one
subfilter even if mapping to both. The approach of mixing the matching of $r$
and $r+1$ bits is known to incur only small space efficiency overheads
compared to an optimal approach with truly fractional $r$ [16]. However, TF
and generalized IF do not compare so directly because they offer different
choices for false positive rates, except when the structure is standard IF
with the same memory efficiency as TF because $t$ is a power of two.

##  4 Evaluation

The proposed filters with a FPFS from Sections 3.5 and 3.6 have been
implemented using as base filters the Java implementation of the xor filter
[8]333The code is available in https://github.com/amacian/fastfilterfpfs. Then
several experiments have been conducted to validate the filters and measure
their performance. All simulations have been run on a Windows 10 machine with
an Intel(R) Core(TM) i7-10700 CPU running at 2.90GHz.

The first experiment focuses on validating the filter functionality by testing
that all elements in $S$ return a positive, all elements in $T$ a negative and
the rest have a false positive probability that is approximately $2^{-(r+a)}$.
This has been done for a set $S$ of one hundred thousand elements and
different sizes of $T=10K,100K,1M$ and $10M$ elements when $r=4,8,16$. First,
sets $S$ and $T$ were generated using random elements. Then, the filters were
constructed and then all elements in $T$ were queried, in all cases there were
no false positives. Therefore, the proposed filters provide the false positive
free set feature. The memory usage and false positive rate for elements not in
$T$ were measured.

The results for memory usage are shown in Figure 8 that includes the
theoretical estimates presented in the previous section. The values for an Xor
filter are similar to those of the TF scheme when $T$ is small that correspond
to the leftmost points on the plots. It can be seen that the simulation
results match the theoretical analysis. The TF construction is the most
efficient in terms of memory usage as expected but the IF construction can
also be implemented with a reasonable amount of memory by appropriately
selecting the value of $c$. The results for the naive construction are not
shown as much more memory is required making the filters not practical when
the number of elements if $T$ is large.

Figure 8: Memory required to implement the TF and IF FPFS filters for
different sizes of $T$ when $r=4$ (left), $r=8$ (middle), $r=16$ (right) and
for $S$ of size one hundred thousand elements.

The parameter $a$ selected for each configuration was also logged and the
results are shown in Figure 9. It can be seen that when $r=16$, the value of
$a$ is always zero as the size of $F$ is much smaller than that of $S$.
Instead, when $r=4,8$ values larger than zero are selected as the size of $T$
grows.

Figure 9: Value of $a$ for the TF and IF FPFS filters for different sizes of
$T$ when $r=4$ (left), $r=8$ (middle), $r=16$ (right) and for $S$ of size one
hundred thousand elements.

Finally, the false positive probability for negative elements that are not in
$T$ was measured with ten million random elements. The results are summarized
in Figure 10 that also shows the theoretical estimate given by
$\frac{1}{2^{r+a}}$. It can be seen that simulation results match the
theoretical analysis.

Figure 10: Fraction of false positives for negative elements not in $T$ for
the TF and IF FPFS filters for different sizes of $T$ when $r=4$ (left), $r=8$
(middle), $r=16$ (right) and for $S$ of size one hundred thousand elements.

The second experiment evaluates the speed of the proposed FPFS filter. As the
absolute performance values are dependent on the platform used to run the
experiments and also on the programming language and tools, we also include
the results for the base Xor filter Java implementation [8]. This enables a
relative comparison in terms of the overhead introduced by our FPFS filters.

The speed is measured for both for the construction of the filter and also for
lookups. In the first case, the time needed to complete the construction was
measured and compared to that of the original filter. The average over 1000
runs was computed and the results are shown in Figure 11. It can be seen that
the proposed filters introduce a significant overhead that is around 2-3x when
$T$ is small and increases with the size of $T$. This overhead is due to
several factors. The first one is the need to construct several filters, two
for the TF and IF, $c=1$ constructions and in some cases even three for the
IF, $c=2$ construction. The construction of the filters is also linked in the
case of IF construction so that when trying a set of hash functions,
construction is successful only when the construction of all the filters
succeeds. The second factor is that some of those filters are larger as they
store elements from $F$ in addition to those in $S$. The third factor that
contributes to the overhead is the fact that all elements in $T$ have to be
checked in the first filter to construct the set $F$. This means that as the
size of $T$ increases, so does the overhead as it is clearly seen in the
results on Figure 11. In any case, the construction time remains in the order
of seconds even for large $T$. Additionally, the check for the elements in $T$
can be easily run in parallel if in some application the overhead becomes an
issue. Indeed, in most applications construction is amortized over many query
operations so its cost is not a major concern.

Figure 11: Average time needed to construct the filter when $r=4$ (left),
$r=8$ (middle), $r=16$ (right) and for $S$ of size one hundred thousand
elements.

To evaluate the speed of lookups we measure the speed for positives and
negatives. Positives would require to check all the filters while for
negatives most of them will be identified by the first filter avoiding access
to the second so the overhead should be smaller. For positives, all the
elements in $S$ were queried and the average time was logged while for
negatives, one million random elements were tested. The results averaged over
1000 runs are shown in Figures 12 and 13 where the results for the original
Xor filter are also included for comparison. It can be seen that the proposed
filters introduce an overhead for positives. This lookup time is approximately
2x for the TF construction which needs to access different memory positions
for each filter. Instead, for the IF constructions it is much lower, below
1.2x that of the original filter in all cases thus confirming the benefits of
integrating the filters when positive lookup speed is a priority. Finally,
speed does not have any clear dependency with the size of $T$ or the value of
$r$ for positive lookups.

Figure 12: Average time needed for a positive lookup when $r=4$ (left), $r=8$
(middle), $r=16$ (right) and for $S$ of size one hundred thousand elements.

For negative lookups, the proposed filters also introduce a small overhead. In
the case of the TF construction, the overhead is small as the first filter is
the same and most lookups (approximately $1-2^{-r}$) only need to check the
first filter. The IF constructions have also a small overhead because checking
the first filter needs some additional operations to extract the relevant bits
that share the word with those of the second filter. In any case, the lookup
time is only approximately 1.2x that of the original filter in the worst case.
In summary, the proposed filters introduce a significant overhead in the
construction time while for lookups, the overhead is smaller and can be
minimized for positive or negative lookups by selecting the filter
construction.

Figure 13: Average time needed for a negative lookup when $r=4$ (left), $r=8$
(middle), $r=16$ (right) and for $S$ of size one hundred thousand elements.

The implementation and evaluation confirm that false positive free on a set
can be implemented with a moderate overhead in memory and speed when using the
xor filter as the base structure. Therefore, for applications on which the
cost of a false positive is large, the proposed filters can provide
significant benefits by ensuring that the most frequent negative elements do
not suffer false positives.

##  5 Case studies

This section discusses the applicability of the proposed filters by presenting
a few use cases and showing the benefits of the proposed filters. The first
case study is a simple spell checker, one of the original applications of
Bloom filters, that is used to illustrate how the proposed filters work. Then,
two more practical case studies a URL deny list and a cryptocurrency
application are discussed.

###  5.1 Spell checker

One of the original applications of Bloom filters was to store the words of a
dictionary to detect spelling errors [12]. Although this is no longer
implemented with Bloom filters, it can serve to illustrate how our FPFS
filters work. In this design, the checker fails to detect spelling errors that
have a false positive on the filter. Unfortunately, those may occur for
frequent spelling mistakes and it would be beneficial to avoid them. In this
scenario, our filter with a false positive free sets can be used by selecting
common spelling errors and adding them to set $T$. To illustrate this use
case, we have taken the Birkbeck dataset444Available at
https://www.dcs.bbk.ac.uk/%7EROGER/corpora.html that contains 36 133 common
misspellings of 6 136 words and inserted the words555We have removed common
misspellings that are duplicated or correspond to valid words so that the
total number of misspelling is reduced to 32 894. in our filter with $r=8$ as
set $S$ and the misspellings as set $T$. We verified that there are no false
positives for those misspellings and measured the false positive rate for
other words. The results show that the proposed filters require 60 951, 63 168
and 68 229 memory bits for the TF, IF with $c=1$ and IF with $c=2$
constructions compared to 60 624 memory bits of a traditional filter. The
memory overhead is negligible (0.5%) for the TF construction and very small
(4.2%) for the IF with $c=1$. The proposed filters achieve a similar false
positive probability for negative elements not in $T$ as that of the original
filter while eliminating all false positives in $T$. Instead, the original
filter suffers on average 130.5 false positives on $T$, based on one thousand
sample runs. This illustrates the benefits of the proposed filters in this
simple case study.

###  5.2 URL deny list

Another scenario where our filters can be useful is to implement a deny list
of malicious URLs. A filter that stores the list of malicious URLs can be
useful to perform an initial checking so that on a negative, the URL can be
safely classified as non-malicious. Instead on a positive a full check would
be needed to ensure that the URL is not a false positive. Here again, there
are many valid URLs that are frequently used and thus ensuring that they do
not suffer false positives would be beneficial. As an example, we have
considered the URL dataset used in [32] that has 485 730 unique URLs of which
16.47% are malicious, and the rest are benign. We store the malicious URLs in
a filter using the benign URLs as set $T$. In this case, we set $r=8$ and the
proposed filters require 656 328, 679 584 and 734 697 memory bits for the TF,
IF with $c=1$ and IF with $c=2$ constructions compared to 653 040 memory bits
of a traditional filter. Again, the memory overhead is negligible (0.5%) for
the TF construction and very small (4.1%) for the IF with $c=1$. We verified
that there are no false positives for the set $T$ in our filters while the
traditional one suffers 1 358 false positives on average, based on one
thousand constructions. This means that again, we are able to avoid false
positives on frequently used URLs. There are other similar use cases of
access/deny lists where our filters could be useful, such as for IP addresses
or person names (e.g. no-fly list).

###  5.3 Bitcoin Simplified Payment Verification (SPVs) Nodes

Bitcoin defines two modes of operation for the nodes: Full nodes and
Simplified Payment Verification nodes
(SPVs)666https://developer.bitcoin.org/devguide/operating%5Fmodes.html. The
full nodes store all the blocks in the Bitcoin blockchain (which currently
requires more than 300 GBs) while the SPV nodes only store the block headers.
This reduces the storage and bandwidth needed by SPV nodes. Since SPV nodes do
not have the full data of the transactions, they need to get it from the full
nodes when needed. Originally, when an SPV needed to retrieve a transaction,
it downloaded the blocks until the transaction was found which was very
inefficient. To reduce the overhead, a first solution was implemented by the
SPV nodes constructing a Bloom filter with the identifiers of the transactions
that they want to get and sending it to the full nodes. Then, the full nodes
applied the filter to each block and whenever a positive was returned by the
filter for any of the transaction identifiers on the block, the block was sent
to the SPV node that issued the
request777https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki.
However, this scheme had privacy issues as full nodes can infer information
from the SPV nodes [14] and the filters can also be used to launch denial of
service attacks. This led to a new design in which full nodes add a filter to
each of the header blocks so that now SPV nodes can use those filters to
locate the blocks that contain the transactions they are interested in. Once
the blocks are identified, the SPV node can download only those blocks from
the full
nodes888https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki. In
this second version, Golomb Code Sets [33] are used instead of Bloom filters
for the approximate membership
checking999https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki.

The number of transactions per month in Bitcoin is approximately 20 million
and as of today the number of existing transactions is around 700
million101010https://www.blockchain.com/charts/n-transactions-total.
Therefore, one possibility could be to replace Golomb Code Sets with our
filter with a false positive free set using the universe of existing
transactions as the set free of false positives or if that is not possible
avoiding for example false positives for the transactions in the last few days
that are more likely to be checked by the SPV nodes. As the number of
transactions per block is around 2500, we have constructed filters with $S$ of
size 2500 and $T$ of sizes 700 million and 20 million to implement a FPFS on
all existing transactions and on the last 30 day transactions respectively.
The FPFS filters when we set $r=8$, require in the first case (700 million)
62293 bits for the TF construction and 76245 and 65268 for the IF1 and IF2
constructions and in the second 46363 bits for the TF construction and 59262
and 46620 bits for the IF1 and IF2 constructions. This shows that the proposed
filters can be used to completely avoid false positives on Bitcoin SPV nodes
for all existing transactions or for the transactions done in the last 30
days.

##  6 Conclusions and Future Work

In this paper, a new type of approximate membership query filters that
completely eliminate false positives for a given set has been proposed.
Several constructions based on xor filters have been presented and evaluated
for these filters with a false positive free set showing that it is indeed
possible to avoid false positives for large sets. The benefits of the filters
with a false positive free set have also been illustrated with three practical
case studies covering different applications in computing and networking.

The constructions presented in this paper are also directly applicable to the
ribbon filter [16], which offers more design flexibility than standard xor
filters. Therefore, implementing the proposed filter with a false positive
free set using ribbon filters is an interesting topic to continue this work.
Similarly, incorporating the proposed filters in Bitcoin SPV nodes and
evaluating their benefits over existing filters would also be of interest.
More broadly, we expect the proposed filters to be beneficial in many other
scenarios and thus identifying those and evaluating the use of the proposed
filters on them could lead to significant performance improvements.

##  7 Acknowledgements

We would like to thank Mario Palomares for the discussions on the Bitcoin SPV
case study. Pedro Reviriego would like to acknowledge the support of the
ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T
funded by the Spanish Agencia Estatal de Investigación (AEI)
10.13039/501100011033 and of the Madrid Community research project TAPIR-CM
grant no. P2018/TCS-4496. Stefan Walzer work was supported by the DFG grant WA
5025/1-1.

## References

  * [1] S. Tarkoma, C. E. Rothenberg, and E. Lagerspetz, “Theory and practice of bloom filters for distributed systems,” _IEEE Communications Surveys Tutorials_ , vol. 14, no. 1, pp. 131–155, 2012.
  * [2] N. Dayan, M. Athanassoulis, and S. Idreos, “Optimal bloom filters and adaptive merging for lsm-trees,” _ACM Trans. Database Syst._ , vol. 43, no. 4, Dec. 2018. [Online]. Available: https://doi.org/10.1145/3276980
  * [3] S. Pontarelli, P. Reviriego, and M. Mitzenmacher, “Emoma: Exact match in one memory access,” _IEEE Transactions on Knowledge and Data Engineering (TKDE)_ , vol. 30, no. 11, pp. 2120–2133, 2018.
  * [4] P. Reviriego, J. Martínez, D. Larrabeiti, and S. Pontarelli, “Cuckoo filters and bloom filters: Comparison and application to packet classification,” _IEEE Transactions on Network and Service Management_ , 2021\.
  * [5] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” _Commun. ACM_ , vol. 13, no. 7, p. 422–426, 1970.
  * [6] L. Luo, D. Guo, R. T. B. Ma, O. Rottenstreich, and X. Luo, “Optimizing bloom filter: Challenges, solutions, and comparisons,” _IEEE Communications Surveys Tutorials_ , vol. 21, no. 2, pp. 1912–1949, 2019\.
  * [7] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher, “Cuckoo filter: Practically better than bloom,” in _ACM CoNEXT_ , 2014.
  * [8] T. M. Graf and D. Lemire, “Xor filters: Faster and smaller than bloom and cuckoo filters,” _ACM J. Exp. Algorithmics_ , vol. 25, Mar. 2020. [Online]. Available: https://doi.org/10.1145/3376122
  * [9] M. A. Bender, M. Farach-Colton, M. Goswami, R. Johnson, S. McCauley, and S. Singh, “Bloom filters, adaptivity, and the dictionary problem,” in _IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2018.
  * [10] M. Mitzenmacher, S. Pontarelli, and P. Reviriego, “Adaptive cuckoo filters,” _ACM J. Exp. Algorithmics_ , vol. 25, 2020.
  * [11] S. Z. Kiss, É. Hosszu, J. Tapolcai, L. Rónyai, and O. Rottenstreich, “Bloom filter with a false positive free zone,” _IEEE Transactions on Network and Service Management_ , pp. 1–1, 2021.
  * [12] M. McIlroy, “Development of a spelling list,” _IEEE Transactions on Communications_ , vol. 30, no. 1, pp. 91–99, 1982.
  * [13] M. Akiyama, T. Yagi, and T. Hariu, “Improved blacklisting: Inspecting the structural neighborhood of malicious urls,” _IT Professional_ , vol. 15, no. 4, pp. 50–56, 2013.
  * [14] A. Gervais, S. Capkun, G. O. Karame, and D. Gruber, “On the privacy provisions of bloom filters in lightweight bitcoin clients,” in _Proceedings of the 30th Annual Computer Security Applications Conference_ , 2014, pp. 326–335.
  * [15] B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal, “The bloomier filter: an efficient data structure for static support lookup tables,” in _Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms_. Citeseer, 2004, pp. 30–39.
  * [16] P. C. Dillinger and S. Walzer, “Ribbon filter: practically smaller than bloom and xor,” _CoRR_ , vol. abs/2103.02515, 2021. [Online]. Available: https://arxiv.org/abs/2103.02515
  * [17] U. Manber and S. Wu, “An algorithm for approximate membership checking with application to password security,” _Inf. Process. Lett._ , vol. 50, no. 4, p. 191–197, 1994.
  * [18] H. Lang, T. Neumann, A. Kemper, and P. Boncz, “Performance-optimal filtering: Bloom overtakes cuckoo at high throughput,” _VLDB Endow._ , vol. 12, no. 5, p. 502–515, 2019.
  * [19] J. G. Cleary, “Compact hash tables using bidirectional linear probing,” _IEEE Trans. Comput._ , vol. 33, no. 9, p. 828–834, Sep. 1984. [Online]. Available: https://doi.org/10.1109/TC.1984.1676499
  * [20] O. Rottenstreich, P. Reviriego, E. Porat, and S. Muthukrishnan, “Avoiding flow size overestimation in the count-min sketch with bloom filter constructions,” _IEEE Transactions on Network and Service Management_ , pp. 1–1, 2021.
  * [21] P. C. Dillinger and P. P. Manolios, “Fast, all-purpose state storage,” in _Proceedings of the 16th International SPIN Workshop on Model Checking Software_. Berlin, Heidelberg: Springer-Verlag, 2009, p. 12–31. [Online]. Available: https://doi.org/10.1007/978-3-642-02652-2_6
  * [22] B. Donnet, B. Baynat, and T. Friedman, “Retouched bloom filters: Allowing networked applications to trade off selected false positives against false negatives,” in _Proceedings of the 2006 ACM CoNEXT Conference_ , ser. CoNEXT ’06. New York, NY, USA: Association for Computing Machinery, 2006. [Online]. Available: https://doi.org/10.1145/1368436.1368454
  * [23] K. Deeds, B. Hentschel, and S. Idreos, “Stacked filters: Learning to filter by structure,” _Proc. VLDB Endow._ , vol. 14, no. 4, p. 600–612, Dec. 2020\. [Online]. Available: https://doi.org/10.14778/3436905.3436919
  * [24] B. Majewski, N. Wormald, G. Havas, and Z. Czech, “A family of perfect hashing methods.” _Comput. J._ , vol. 39, pp. 547–554, 01 1996.
  * [25] M. Genuzio, G. Ottaviano, and S. Vigna, “Fast scalable construction of ([compressed] static — minimal perfect hash) functions,” _Information and Computation_ , vol. 273, p. 104517, 2020, dCC (Data Compression Conference) 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0890540120300043
  * [26] S. Walzer, “Peeling close to the orientability threshold: Spatial coupling in hashing-based data structures,” in _Proc. 32nd SODA_ , 2021.
  * [27] D. Belazzougui and R. Venturini, “Compressed static functions with applications,” in _Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms_ , ser. SODA ’13. USA: Society for Industrial and Applied Mathematics, 2013, p. 229–240.
  * [28] J. B. Hreinsson, M. Krøyer, and R. Pagh, “Storing a compressed function with constant time access,” in _Proc. 17th ESA_ , 2009, pp. 730–741.
  * [29] K. Mehlhorn, _Data Structures and Algorithms 1: Sorting and Searching_. Springer, 1984. [Online]. Available: http://www.mpi-inf.mpg.de/~mehlhorn/DatAlgbooks.html
  * [30] L. Carter, R. Floyd, J. Gill, G. Markowsky, and M. Wegman, “Exact and approximate membership testers,” in _Proceedings of the Tenth Annual ACM Symposium on Theory of Computing_ , ser. STOC ’78. New York, NY, USA: Association for Computing Machinery, 1978, p. 59–65. [Online]. Available: https://doi.org/10.1145/800133.804332
  * [31] T. Kopelowitz, S. McCauley, and E. Porat, “Support optimality and adaptive cuckoo filters,” in _Proc. 17th WADS_ , ser. Lecture Notes in Computer Science, vol. 12808. Springer, 2021, pp. 556–570.
  * [32] Z. Dai and A. Shrivastava, “Adaptive learned bloom filter (ada-bf): Efficient utilization of the classifier,” _arXiv_ , 2019.
  * [33] S. Golomb, “Run-length encodings (corresp.),” _IEEE Transactions on Information Theory_ , vol. 12, no. 3, pp. 399–401, 1966.