# Aleph Filter: To Infinity in Constant Time

Niv Dayan  University of TorontoCanada ,  Ioana Bercea  KTH Royal Institute of
TechnologySweden and  Rasmus Pagh  BARC, University of CopenhagenDenmark

###### Abstract.

Filter data structures are widely used in various areas of computer science to
answer approximate set-membership queries. In many applications, the data
grows dynamically, requiring their filters to expand along with the data that
they represent. However, existing methods for expanding filters cannot
maintain stable performance, memory footprint, and false positive rate at the
same time. We address this problem with Aleph Filter, which makes the
following contributions. (1) It supports all operations (insertions, queries,
deletes, etc.) in constant time, no matter how much the data grows. (2) Given
any rough estimate of how much the data will ultimately grow, Aleph Filter
provides far superior memory vs. false positive rate trade-offs, even if the
estimate is off by orders of magnitude.

##  1\. Introduction

Filters. A filter is a compact data structure that represents keys in a set
and answers approximate set-membership queries. It cannot return false
negatives, but it returns a false positive with a probability that depends on
the number of bits used on average to represent each key. A filter is
typically stored at a higher layer of the memory hierarchy (e.g., DRAM) than
the base data, which typically resides in storage (i.e., disk or SSD) and/or
over a network. If a filter returns a negative, the sought-after key is
guaranteed not to exist, meaning that the full data set does not need to be
searched. In this way, filters eliminate redundant storage accesses and
network hops to improve a system’s performance.

From Bloom to Tabular Filters. The Bloom filter (Bloom, 1970) is the oldest
and best-known filter. It works by hashing each key to random bits in a bit
vector, setting them from zeros to ones. During a query, it returns a positive
if all bits corresponding to a given key are set to ones and a negative
otherwise. Bloom filters do not support deletes and cannot be efficiently
expanded. Hence, they are typically used to represent static key sets.

Over the past 10-15 years, a new family of tabular filters emerged as an
alternative to Bloom filters. A tabular filter stores a fingerprint (i.e., a
hash digest) for each key in a compact hash table. It processes a query by
checking if the fingerprints in a given hash slot match the fingerprint of the
target key. To date, numerous tabular filters have been proposed with various
nuanced performance properties on account of their different hash collision
resolution strategies (i.e., cuckoo (Fan et al., 2014; Breslow and Jayasena,
2018; Wang et al., 2019), robin hood (Bender et al., 2012; Pandey et al.,
2017), or two-choice (Pandey et al., 2021; McCoy et al., 2023b) hashing,
etc.). Unlike Bloom filters, many Tabular filters support deletes and can
associate a payload with each fingerprint. These capabilities allow tabular
filters to support richer, dynamic applications (e.g., key-value stores (Dayan
and Twitto, 2021; Ren et al., 2017; Conway et al., 2023; Shetty et al., 2013),
large-scale k-mer analysis (McCoy et al., 2023a), duplicate detection in
streams (Dutta et al., 2013), etc.).

The Need for Expandable Filters. In many applications that use filters, the
data size grows over time. This establishes a need for filters that can expand
along with the data. For example, many modern log-structured key-value stores
employ an in-memory tabular filter to map the location of each data entry in
storage (Chandramouli et al., 2018; Andersen et al., 2009; Debnath et al.,
2010, 2011; Dayan and Twitto, 2021; Dayan et al., 2021; Ren et al., 2017;
Conway et al., 2023). As the data size grows, the filter must expand to map a
greater number of keys and their storage locations. In the networks community,
expandable filters have recently been pointed out as pivotal for supporting
black lists and multicast routing. In the architecture community, the 2020
ASPLOS best paper proposes to implement virtual page tables using an
expandable tabular filter (Skarlatos et al., 2020). While expandable filters
empower a widening range of modern applications, existing approaches exhibit
performance problems.

Common Expansion Approaches. The simplest approach for expanding a filter is
to reread the original data and construct a larger filter from scratch. If the
data resides in storage, however, scanning it can be performance prohibitive.

Hence, the standard approach for expanding a tabular filter is to allocate a
hash table with twice the capacity and to migrate every fingerprint into this
larger hash table. The issue is that this requires transferring one bit from
each entry’s fingerprint to become a part of its slot address to evenly
distribute the fingerprints across the expanded hash table (Bender et al.,
2012; Zhang et al., 2021). As a result, the fingerprints shrink as the data
grows, causing the false positive rate (FPR) to increase. Eventually, the
fingerprints run out of bits, at which point the filter becomes useless by
returning a positive for any query.

The State of the Art: InfiniFilter. The recent InfiniFilter (Dayan et al.,
2023) is a tabular filter that can grow indefinitely while better scaling the
FPR. It also expands by migrating all fingerprints into a larger hash table
with twice the capacity while sacrificing one bit from each fingerprint in the
process. The core innovation is a new hash slot format that allows setting
longer fingerprints to newer entries. On average, this stabilizes the FPR.
Nevertheless, InfiniFilter suffers from two scalability concerns.

Problem 1: Performance Scalability. After the first few expansions, older
fingerprints within InfiniFilter run out of bits. Such entries are referred to
as void entries. A void entry cannot be uniquely mapped to a slot in an
expanded filter as there is no additional fingerprint bit to transfer to its
slot address. InfiniFilter addresses this problem by transferring and storing
void entries across a series of smaller hash tables. The problem is that query
and delete operations must probe potentially each of these hash tables,
resulting in worst-case asymptotically increasing CPU overheads. Can we better
scale the costs of queries and deletes?

Problem 2: FPR vs. Memory Scalability. As InfiniFilter expands, the shorter
fingerprints of older entries cause the FPR to increase (i.e., at a
logarithmic rate). To counteract this phenomenon, it is possible to assign
increasingly long fingerprints to newer entries across expansions to cause the
FPR to converge to a constant. However, this inflates the memory footprint. Is
it possible to resolve or at least alleviate this contention such that the FPR
vs. memory trade-off for expandable filters stays closer to that of static
filters?

Aleph Filter. We propose Aleph Filter111The name Aleph is borrowed from set
theory, where the Aleph numbers denote different orders of infinity. , an
infinitely expandable filter with constant time performance for insertions,
queries, and deletes, and superior memory vs. FPR trade-offs. It achieves this
by building on top of InfiniFilter in three ways.

Contribution 1: Faster Queries by Duplicating Void Entries. Aleph Filter
duplicates every void entry in the expanded hash table across both slots that
it could have mapped to if there were an additional fingerprint bit to
sacrifice. This keeps all information about all entries, including void
entries, within one main hash table. As a result, Aleph filter accesses only
one hash table for any query at a cost of $O(1)$ time. We show how to tune the
filter such that duplicated void entries occupy negligible space within the
filter so as not to adversely impact its performance.

Contribution 2: Faster Deletes using Tombstones. Duplicating void entries
within the main hash table makes it challenging to efficiently execute
deletes. The reason is that potentially many duplicates must be identified and
removed whenever an older entry is deleted. Aleph filter addresses this
challenge by first transforming the target void entry into a tombstone in
$O(1)$ time. Before the next expansion, it retrieves the original hash of the
deleted void entry and uses it to identify the full collection of duplicates
that need to be removed. The overhead of removing these duplicates is
negligible and gets amortized as a part of the next expansion operation.

Contribution 3: Inverting the FPR vs Memory Trade-Off. In many applications,
the maximum data size can be predicted in advance. We show that given a
reasonable estimation of how much the data will grow, it is possible to pre-
allocate slightly longer fingerprints from the onset and assign decreasing
fingerprint lengths to newly inserted entries. By the time we reach the
estimated data size, the filter guarantees an FPR vs. memory footprint trade-
off that is on par with that of static filters. Even as the data size
surpasses the estimate, Aleph Filter continues to dominate the State of the
Art with respect to memory vs. FPR trade-offs that it provides.

term |  definition
---|---
$N$ |  current filter capacity divided by initial capacity
$X$ |  number of expansions so far (i.e., $X=\lceil\log_{2}(N)\rceil$)
$M$ |  total memory used for the filter (bits / entry)
$F$ |  initial fingerprint length when the filter is first allocated
$h(...)$ |  mother hash generating function
$\alpha$ |  fraction of occupied slots ($0\leq\alpha<1$)
Table 1.  Terms used throughout the paper to describe Aleph Filter and other
baselines.

##  2\. Background

This section describes Quotient Filter and InfiniFilter, on top of which we
build Aleph Filter.

###  2.1. Quotient Filter

A quotient filter (Clerry, 1984; Dillinger and Manolios, 2009; Bender et al.,
2012) is a hash table that stores a fingerprint for each inserted key. It does
this by first generating a mother hash for a key consisting of $F+A$ bits
using some hash function $h(...)$. The least significant $A$ bits of this
mother hash represent the key’s canonical slot. The subsequent $F$ bits are
the key’s fingerprint. Table 1 lists terms used throughout the paper.

A quotient filter resolves hash collisions using Robin Hood hashing (Celis et
al., 1985), which is a variant of linear probing (Peterson, 1957). This means
that all fingerprints mapped to a given canonical slot are stored
contiguously, and they push to the right any other existing fingerprints that
they collide with. A run is defined as a group of contiguous fingerprints
belonging to the same canonical slot. A cluster is defined as several adjacent
runs where all but the first have all been pushed to the right due to
collisions.

Figure 1 Part A illustrates a quotient filter with eight slots after four
insertions of Keys $V$, $Y$, $Z$ and $W$. The mother hash for each key is
shown at the top. The rightmost (least significant) bits for each mother hash
represent the key’s canonical address. The subsequent bits, shown in red, are
the fingerprint. Keys $V$ and $Y$ share Canonical Slot 100 while Keys $Z$ and
$W$ share the adjacent Canonical Slot 101. The result is a cluster consisting
of two runs, each with two slots.

Metadata Bits. To keep track of the start and end of runs and clusters, a
quotient filter employs three metadata bits per slot. The is$\\_$occupied bit
indicates whether the slot is a canonical slot for at least one existing key.
The is$\\_$shifted bit indicates whether the slot contains a fingerprint that
has been shifted to the right relative to its canonical slot. The
is$\\_$continuation bit indicates whether the slot contains the start of a new
run within a cluster.

Figure 1. A Quotient filter stores a fingerprint for each key in a hash table,
and it resolves has collisions by organizing fingerprints into runs and
clusters. Fingerprints are illustrated in red.

In Figure 1 Part A, the is$\\_$occupied flag is set for Slots 100 and 101 as
each of them is a canonical slot for at least one key. The is$\\_$shifted flag
is set for Slots 101, 110, and 111 as they each contain a fingerprint that has
been shifted to the right from its canonical slot. The is$\\_$continuation
flag is set for Slots 101 and 111 as they each contain a fingerprint belonging
to a run that starts to its left.

Query. A query begins at the canonical slot for the target key. If the
is$\\_$occupied flag for this slot is set to 0, the key could not have been
inserted so the query returns a negative. Otherwise, the query must find the
start of the target run that might contains the sought-after key, yet this run
could have been pushed to the right from its canonical slot due to collisions.
To find the target run, the query first moves leftwards until reaching the
start of the cluster. Along the way, it counts the number of is$\\_$occupied
flags $c$ set to ones, each of which indicates the existence of a run in the
cluster that precedes Run $r$. After reaching the start of the cluster, the
query moves rightwards while skipping $c$ runs, at which point it reaches the
target run. It then scans this run, returning a positive if it finds a
matching fingerprint.

Figure 2.  The Fingerprint Sacrifice method transfers one bit from the
fingerprint to the slot address while expanding to evenly distribute the
entries across the larger hash table.

Insertion. An insertion commences as a query by first finding the start of the
target run for the key we wish to insert. It then adds a fingerprint to this
run, pushing subsequent fingerprints in the cluster one slot to the right to
clear space. This may cause more runs to join the cluster by pushing them from
their canonical slots.

Delete. A delete operation also commences like a query by first finding the
target run of the key we wish to remove. It then scans the run and removes the
first matching fingerprint. Then, it pulls all remaining fingerprints in the
cluster one slot to the left to keep the cluster contiguous. For example,
Figure 1 Part B illustrates how deleting Key $Y$ pulls the second run in the
cluster back to its canonical slot, causing the cluster to fragment. As with
any tabular filter, it is only permissible to delete keys that we know for
sure had been inserted to prevent false negatives.

False Positive Rate. A quotient filter’s FPR is $\approx\alpha\cdot 2^{-F}$,
where $F$ is the fingerprint size and $\alpha$ is the fraction of the slots
that are occupied. The intuition is that the target run contains on average
$\alpha$ fingerprints, while the probability that each of them matches that of
the sought-after key is $2^{-F}$.

Reaching Capacity. As a quotient filter exceeds $90\%$ utilization (i.e.,
$\alpha=0.9$), the clusters’ lengths begin to grow rapidly. This causes
performance to plummet as all operations on the filter must traverse a greater
number of slots. To keep performance stable and to accommodate more
insertions, it is desirable to expand the filter.

Fingerprint Sacrifice. The standard approach for expanding a quotient filter
is to derive the mother for every key by concatenating its canonical slot
address to its fingerprint. We then reinsert the mother hash into a hash table
with twice the capacity of the original one (Bender et al., 2012). Figure 2
illustrates an example. As shown, this approach transforms the least
significant bit of each fingerprint to the most significant bit of its
canonical slot address in order to to evenly distribute the fingerprints
across the larger hash table. Hence, all fingerprints shrink by one bit in
each expansion, causing the FPR to double, i.e., the FPR becomes $O(N\cdot
2^{-F})$ (Dayan et al., 2023). This method supports at most $F$ expansions, at
which point all fingerprints run out of bits. We summarize the properties of
this method in Row 1 of Table 2.

Figure 3.  By supporting variable-length fingerprints, InfiniFilter can set
long fingerprints to newer entries inserted after expanding.

###  2.2. InfiniFilter

InfiniFilter is a quotient filter that sets longer fingerprints to newer
entries to allow expanding indefinitely while stabilizing the FPR.

Unary Padding. The central design innovation of InfiniFilter is the ability to
store variable-length fingerprints. This is achieved by padding each
fingerprint with a self-delimiting unary code to occupy the rest of the space
in the slot. The top part of Figure 3 illustrates an instance of InfiniFilter
with four occupied slots and fingerprints of lengths 3, 1, 2 and 3 bits from
left to right. Fingerprints and unary codes are illustrated in red and blue,
respectively.

Expansion Algorithm. As with the Fingerprint Sacrifice method, InfiniFilter
transfers the least significant bit from each fingerprint to become the most
significant bit of the slot address during expansion to evenly distribute
existing entries across the expanded hash table. After the expansion,
InfiniFilter’s slot format allows inserting longer fingerprints than the older
ones that had shrunk. This is shown by the insertion of entry $Y$ in Figure 3.
This entry is assigned a three bit fingerprint despite the fact that
fingerprints that existed before the expansion have now all shrunk to two or
fewer bits. This keeps the average fingerprint length longer.

Figure 4.  InfiniFilter in the Widening Regime gradually increases the slot
width across expansions to keep the false positive rate constant.

False Positive Rate. Since InfiniFilter doubles in capacity every time it
expands, the fingerprints within the filter follow a geometric distribution
with respect to their lengths: half of them are as long as possible, a quarter
are shorter by one bit, an eighth are shorter by two bits, etc. Generally, the
fingerprints created $i$ generations ago comprise a fraction of
$\approx\alpha\cdot 2^{-i-1}$ of the occupied slots, while their fingerprints
have a length of $F-i$ bits and hence a collision probability of $2^{-F+i}$.
The FPR after $X$ expansions can be derived as a weighted average of these
terms: $\sum_{i=0}^{X}2^{-F+i}\cdot\alpha\cdot
2^{-i-1}\lesssim(\log_{2}(N)+2)\cdot 2^{-F-1}\cdot\alpha$. After $\approx
2^{F}$ expansions, the FPR reaches one, at which point the filter returns a
positive for any query thereby becoming useless.

Fixed-Length vs. Widening Regimes. To further stabilize the FPR, it is
possible to widen slots across expansions. For example, Figure 4 illustrates
increasing the slot width by one bit. Entries inserted after the expansion are
set fingerprints of length four rather than three bits. By assigning
fingerprints of length $F+\lceil 2\cdot\log_{2}(X+1)\rceil$ bits to new
entries after the $X^{\text{th}}$ expansion, the FPR converges to a constant
smaller than $2^{-F}$ (Dayan et al., 2023). The intuition is that the longer
fingerprints of newer entries make their weighted contribution to the FPR
increasingly small. We refer to this as the Widening Regime, in contrast to
the Fixed-Width Regime described just before.

Deletes. InfiniFilter deletes a key by removing the longest matching
fingerprint in the target run to prevent future false negatives. For example,
Figure 5 illustrates a delete operation to Key $Z$. The target run for this
key begins at Slot 1010 and consists of three slots. While the fingerprint at
Slot 1010 does not match, both subsequent fingerprints, which have different
lengths, do match. If we remove the shorter matching fingerprint (at Slot
1011) and it happens to belong to a different key $Y$ with a different mother
hash from that of Key $Z$ (e.g., $h(Y)=011010$), future false negatives would
occur when querying for Key $Y$. In contrast, removing the longest matching
fingerprint (at Slot 1100) guarantees that the remaining shorter fingerprint
in the run will still match the non-deleted key so that future queries to it
do not result in false negatives.

Rejuvenation. In many applications (e.g., key-value stores), a positive query
to a filter is followed by fetching the corresponding data entry from storage
to return it to the user. In case that the key exists (i.e., a true positive),
we can rehash it to derive a longer mother hash and thus rejuvenate (i.e.,
lengthen) the key’s fingerprint, in case it was created before the last
expansion. Such rejuvenation operations help keep the FPR low. However, they
are only effective when queries target older entries. Similarly to deletes, a
rejuvenation operation must lengthen the longest matching fingerprint in a run
to prevent false negatives.

Void Entries. After the first $F$ expansions, the oldest fingerprints in
InfiniFilter run out of bits. Such entries are referred to as void entries.
Both Figures 3 and 4 show the creation of a void entry at Slot 101 after the
expansion. As shown, the unary code fully occupies a slot that contains a void
entry. Any query that encounters a void entry in its target run returns a
positive. Void entries cannot be uniquely remapped to a slot in a larger
filter as there is no extra fingerprint bit to transfer to the entry’s
canonical slot address.

Figure 5.  InfiniFilter deletes the longest matching fingerprints in the target run to prevent future false negatives.  |  query/ delete/rejuv |  insert |  FPR |  fingerprint
bits / key |  max.
expansions
---|---|---|---|---|---
Fingerprint Sacrifice (Zhang et al., 2021; Bender et al., 2012) |  $O(1)$ |  $O(1)$ |  $O(2^{-F}\cdot N)$ |  $F-O(\lg N)$ |  $F$
InfiniFilter (Fixed-Width Regime) |  $O(\frac{\lg N}{F})$ |  $O(1)$ |  $O(2^{-F}\cdot\lg N)$ |  $F$ |  $2^{F}$
InfiniFilter (Widening Regime) |  $O(\frac{\lg N}{F+\lg\lg N})$ |  $O(1)$ |  $O(2^{-F})$ |  $F+O(\lg\lg N)$ |  $\infty$
Table 2. A comparison of different techniques for expanding a filter. No
existing method is scalable in terms of the costs of queries/deletes, the
false positive rate, the memory footprint, and the maximum number of
expansions, all at the same time.

Supporting Infinite Expansions. To support more than $F$ expansions,
InfiniFilter transfers each void entry from the main hash table into a smaller
secondary hash table, which has an identical structure to that of the main
hash table but fewer slots. Figure 6 illustrates this process across four
expansions. During the second expansion, for instance, the void entry from
canonical Slot 110 of the main hash table is transferred to the secondary hash
table. As 110 is also the mother hash of this entry, its least significant bit
(i.e., 0) is used as a canonical slot address in the secondary hash table
while its more significant two bits (i.e., 11) are used as a fingerprint.

The secondary hash table also expands when it reaches capacity. Eventually,
the oldest entries in the Secondary hash table become void entries, as shown
in Figure 6 by the entry at Slot 11 after the third expansion. As this point,
the Secondary InfiniFilter is sealed and appended to a so-called chain of
auxiliary hash tables, and a new empty secondary hash table is allocated.
While this design supports an unlimited number of expansions, it slows down
queries, deletes and rejuvenation operations, as they must now traverse
potentially all hash tables along the chain.

Figure 6.  InfiniFilter transfers void entries into a secondary hash table,
which also expands when it reaches capacity. When void entries appear in the
secondary hash table, it is appended to a chain of hash tables and a new
secondary hash table is allocated.

##  3\. Problem Analysis

Challenge 1: Scaling CPU Costs. The number of hash tables across which
InfiniFilter stores its entries determines the CPU costs of queries, deletes
and rejuvenation operations. In the Fixed-Width Regime, each hash table stores
entries from across $F$ subsequent expansions, and the overall number of
expansions is $\log_{2}(N)$. Hence, there are at most
$O(\nicefrac{{\lg(N)}}{{F}})$ hash tables. In the Widening Regime, each hash
table stores entries from across $F+O(\lg\lg N)$ subsequent expansions on
average, and so the number of hash tables is $O(\nicefrac{{\lg(N)}}{{(F+\lg\lg
N)}})$ (Dayan et al., 2023). We summarize these properties in Rows 2 and 3 of
Table 2. Under both regimes, performance deteriorates as the data grows. Can
we reduce the worst-case number of hash tables that queries, deletes, and
rejuvenation operations must access?

Challenge 2: Alleviating the Memory vs. FPR Contention. As shown in Row 2 of
Table 2, InfiniFilter exhibits a logarithmic FPR if we fix the number of bits
per entry. Alternatively, as shown in Row 3, it exhibits a stable FPR if we
increase the number of bits per entry at a doubly logarithmic rate. Is it
possible to alleviate this scalability contention to achieve an FPR and memory
footprint that are both on par with a static filter?

##  4\. Aleph Filter

We introduce Aleph Filter, an expandable filter that builds on InfiniFilter to
improves its scalability properties. Section 4.1 shows how Aleph Filter
supports queries in $O(1)$ time by keeping and duplicating void entries within
the main hash table. Section 4.2 shows analytically that the fraction of
duplicated void entries stays small and therefore does not significantly
impact the FPR or the maximum number of expansions that the filter supports.
Sections 4.3 and 4.4 address the challenges of supporting deletes and
rejuvenation operations in $O(1)$ time by lazily identifying and removing
duplicated void entries. Section 4.5 shows how given a rough, conservative
estimation of how much the data will grow, Aleph filter achieves superior FPR
vs. memory trade-offs relative to InfiniFilter.

###  4.1. Fast Queries by Duplicating Void Entries

While expanding, Aleph Filter duplicates each void entry in the main hash
table across both canonical slots that it could have mapped to if there were
an additional fingerprint bit to sacrifice. In Figure 7, for example, there is
a void entry at Slot 11 of the main hash table before the expansion. During
the expansion, Aleph Filter duplicates it across Canonical Slots 011 and 111.
In the next expansion, each of these duplicates will be duplicated again,
resulting in four duplicates at Canonical Slots 0011, 0111, 1011, and 1111.

Figure 7.  While expanding, Aleph Filter duplicates each void entry so that
one duplicate would still be found in constant time when querying for the
original key.

As a result of duplicating void entries, a query targeting any old entry
returns a positive after one access to the main hash table. Figure 7
illustrates a query to Key $Y$, which corresponds to the void entry that was
duplicated. The query visits canonical slot 111 (based on the first three bits
of the key’s mother hash), finds a void entry and returns a positive. Had Key
Y’s mother hash started with 011, the query would have found the other void
duplicate at Slot 011 and also terminated after one hash table access. This is
in contrast to InfiniFilter, which must search the smaller hash tables if the
target key was inserted many expansions ago.

Another result of duplicating void entries is that any query to a non-existing
key terminates after one access to the main hash table. The reason is that the
main hash table contains either a fingerprint or a void entry in any existing
key’s canonical slot. This means that if we do not find a matching entry in
$O(1)$ time, the target entry is guaranteed not to exist. In contrast, a query
to InfiniFilter must also search all the smaller hash tables to verify that
the key does not exist before it can return a negative.

Hence, all queries to Aleph Filter are processed in worst-case $O(1)$ time.
This is an improvement over InfiniFilter, where queries targeting non-existing
or older keys must search an increasing number of hash tables as the data
grows.

|  query/ delete/rejuv |  insert |  false positive rate |  fingerprint
bits / key |  maximum
expansions
---|---|---|---|---|---
Aleph Filter (Fixed-Width Regime) |  $O(1)$ |  $O(1)$ |  $O(2^{-F}\cdot\lg N)$ |  $F$ |  $2^{F}$
Aleph Filter (Widening Regime) |  $O(1)$ |  $O(1)$ |  $O(2^{-F})$ |  $F+O(\lg\lg N)$ |  $\infty$
Aleph Filter (Predictive Regime) |  $O(1)$ |  $O(1)$ |  $O(2^{-F})$ |  $F+O(\lg|\lg(N/N_{est})|)$ |  $\infty$
Table 3.  Aleph Filter achieves constant time performance for all operations.
In addition, the new Predictive Regime significantly reduces the memory
requirement given a rough estimate $N_{est}$ of how much the data will grow.

###  4.2. Analysis

Duplicating void entries in the main hash brings up two plausible concerns.
First, do duplicated void entries significantly increase the FPR, seeing as a
query that encounters a void entry immediately returns a positive? Second, can
duplicated void entries fill up the main hash table to prevent the insertion
of new entries? This section shows that the proportion of void entries stays
moderate and therefore does not increase the FPR or decrease the maximum
number of expansions that Aleph Filter supports relative to InfiniFilter.

Generational Distribution. Aleph Filter doubles in capacity during each
expansion. This means that keys inserted zero, one or two expansions ago
comprise approximately a half, a quarter, or an eighth of the data set,
respectively, and so on. More generally, consider the Set $s_{j}$ of keys
inserted in-between the $j^{\text{th}}$ and $(j+1)^{\text{th}}$ expansions,
i.e., in Generation $j$. Suppose we are now in Generation $X$ ($X\geq j$),
i.e., before Expansion $X+1$. Equation 1 approximates the size of Set $s_{j}$
as a fraction of the whole key set.

(1) $f(j)\approx 2^{-X+j-1}$

FPR in the Fixed-Width Regime. Consider some Generation $j$ of non-void
entries (i.e., $X-j<F$) . These entries’ fingerprints each consist of $F-X+j$
bits, since they are initialized with $F$ bits and lose one bit in each
expansion. The probability for a query to encounter such an entry in a given
slot and falsely match its fingerprint is $\alpha\cdot f(j)\cdot
2^{-F+X-j}=\alpha\cdot 2^{-F-1}$.

Now consider a Generation $j$ of void entries (i.e., $X-j\geq F$). There are
$2^{-F+X-j}$ duplicates per entry since the number of duplicates increases by
a factor of two in each expansion. The fraction of slots occupied by void
duplicates originating from Generation $j$ is $\alpha\cdot f(j)\cdot
2^{-F+X-j}=\alpha\cdot 2^{-F-1}$. Hence, the probability of encountering a
void duplicate from Generation $j$ during a query and thus returning a false
positive is $\alpha\cdot 2^{-F-1}$.

We observe that the weighted contribution of each generation of entries to the
FPR is equal (i.e., $\alpha\cdot 2^{-F-1}$). Equation 2 expresses the overall
FPR after $X$ expansions. As shown, Aleph Filter has approximately the same
FPR as InfiniFilter in the fixed-width regime.

(2) $\small\begin{split}FPR&\approx\sum_{j=0}^{X+1}\alpha\cdot
2^{-F-1}\lesssim\alpha\cdot(log_{2}(N)+2)\cdot 2^{-F-1}\\\ \end{split}$

FPR in the Widening Regime. In the Widening Regime, entries in Generation $j$
are assigned fingerprints of $\ell(j)=F+2\cdot\log_{2}(j+1)$ bits, and they
lose one bit in each expansion.

Let us consider a generation Generation $j$ of non-void entries (i.e.,
$X-j<\ell(j)$). By Generation $X$, the fingerprints of Generation $j$ will
have shrunk by $X-j$ bits to $\ell(j)-(X-j)$ bits. The probability for a query
to encounter an entry from Generation $j$ in a given slot and falsely match
its fingerprint is therefore $\alpha\cdot f(j)\cdot 2^{-\ell(j)+X-j}$.

Let us now suppose Generation $j$ consists of void entries (i.e.,
$X-j\geq\ell(j)$). The number of void duplicates for each entry is
$2^{-\ell(j)+X-j}$. The probability of encountering a void duplicate
originating from this generation is therefore the same expression:
$\alpha\cdot f(j)\cdot 2^{-\ell(j)+X-j}$.

Equation 3 sums up this expression across all generations to derive the FPR.
The derivation uses a well-known identity that the sum of the reciprocals of
the square numbers (i.e., $\Sigma_{i=0}^{\infty}i^{-2}$) converges to
$\nicefrac{{\pi^{2}}}{{6}}$. The result is that Aleph Filter’s FPR matches
InfiniFilter’s FPR in the Widening regime.

(3) $\small\begin{split}FPR&\approx\sum_{j=0}^{X+1}\alpha\cdot f(j)\cdot
2^{-\ell(j)+X-j}\\\\[-5.69054pt] &\approx\alpha\cdot
2^{-F-1}\cdot\sum_{j=0}^{i}\cdot\frac{1}{(j+1)^{2}}\lesssim\alpha\cdot
2^{-F-1}\cdot\frac{\pi^{2}}{6}\lesssim\alpha\cdot 2^{-F}\end{split}$

Expansion Limit in Fixed-Width Regime. As we just saw, the fraction of slots
in the filter that are occupied by void duplicates of entries created in
generation $j$ is $\alpha\cdot f(j)\cdot 2^{-F+X-j}=\alpha\cdot 2^{-F-1}$. The
number of generations of void entries is $X-F+1$. Hence, the fraction of slots
occupied by void duplicates by the time we reach Generation $X$ ($X\geq F$) is
$\gamma(X)=\alpha\cdot 2^{-F-1}\cdot(X-F+1)$. We may now ask at which point
the number of duplicates takes up half the space in the filter, meaning that
even after we expand, void duplicates fully take up the expanded capacity so
there is no space for new insertions. We obtain it by setting $\alpha$ to one,
equating $\gamma(X)$ to $\nicefrac{{1}}{{2}}$, and solving for $X$ to obtain
$F+2^{F}-1$. Recall from Section 2 that the fixed-width regime only supports
$2^{F}$ expansions anyways (as at this point the FPR reaches one and the
filter becomes useless). Hence, Aleph Filter does not reduce the maximum
number of supported expansions in the Fixed-Width Regime.

Expansion Limit in Widening Regime. As we saw, the fraction of slots in the
filter occupied by void duplicates from Generation $j$ is $\alpha\cdot
f(j)\cdot 2^{-FP(j)}$. Let $v$ denote the total number of generations of void
entries. The overall fraction of slots occupied by void entries is
$\sum_{j=0}^{v}\alpha\cdot 2^{-FP(j)}\cdot f(j)$. We note that this expression
is subsumed by Equation 3 and is therefore lower than $\alpha\cdot 2^{-F}$.
This establishes that the fraction of slots occupied by void entries converges
to a small constant as the filter expands. The intuition is that newer entries
are assigned longer fingerprints, and so it takes them increasingly longer to
become void and start duplicating. As a result, Aleph Filter supports an
infinite number of expansions.

###  4.3. Fast Deletes Using Tombstones

Duplicating void entries makes delete operations more intricate to handle. The
reason is that every duplicate of a void entry that we wish to delete must be
identified and removed. The challenge is do so correctly, in constant time,
and without using a significant amount of additional metadata.

In the simple case that a delete operation is targeting a run with at least
one matching non-void entry, the entry with the longest matching fingerprint
will be removed as shown in Section 2. This section focuses on processing
deletes when the only matching entries in the target run are void entries.

Figure 8.  Aleph filter stores the mother hashes of all void entries along a
secondary hash table and a series of auxiliary hash tables.

Identifying a Void Entry’s Duplicates. An entry becomes void when the length
of the mother hash that it was assigned when it was inserted matches the
logarithm base two of the number of slots in the filter. In every subsequent
expansion, the number of duplicates for the entry and the number of slots in
the filter both multiply by a factor of two. If the entry’s original mother
hash consists of $b$ bits and the filter currently comprises $2^{k}$ slots,
then the entry participated in $k-b$ expansions since it became a void entry.
Therefore, it has $2^{k-b}$ void duplicates. For example, suppose the filter
consists of $2^{6}$ slots and the mother hash we wish to remove is 0011. This
mother hash consists of $b=4$ bits while the power of the size of the filter
is $k=6$, meaning that its number of void duplicates is $2^{6-4}=4$.

We can also infer which canonical slots contain these void duplicates by using
the mother hash of the original entry as the least significant $b$ bits of
their addresses, and applying all possible permutations to the remaining $k-b$
bits. In the example just given, we use the mother hash 0011 as the least
significant bits and permute the remaining two bits to obtain the following
four slots addresses: 000011, 010011, 100011, 110011\. To execute the delete
correctly, we would need to remove a void duplicate from each one of these
canonical slots. The question becomes how to efficiently store and retrieve
the mother hash of any void entry so that we can identify and remove all of
its void duplicates?

Secondary Hash Table. Similarly to the Chained InfiniFilter, Aleph filter adds
the mother hash of any entry that turns void into a secondary hash table,
which has an identical structure to that of the main hash table yet fewer
slots. Figure 7 illustrates an example. Before the expansion, the secondary
hash table stores only the mother hash of the void entry at Slot 11 of the
main hash table. The secondary hash table then expands alongside the main hash
table. After the expansion, another entry turns void at Slot 010 of the main
hash table, and so its mother hash is stored in the Secondary hash table. Note
that while a void entry may have multiple duplicates in the main hash table
(e.g., at Slots 011 and 111), its mother hash is only stored once in the
secondary hash table.

Auxiliary Hash Tables. Expanding the secondary hash table requires
transferring one bit from each entry’s fingerprint to its canonical slot
address in the expanded hash table. In Figure 7, for example, the entry at
Slot 1 of the secondary hash table after the expansion corresponds to the
entry with fingerprint 11 before the expansion, since the least significant
bit of its fingerprint is repurposed as the most significant bit of its slot
address. Eventually, void entries appear in the secondary hash table as well.
At this point, we seal the secondary hash table and add it to a chain of
auxiliary hash tables. A new empty secondary hash table is then allocated.
Figure 8 illustrates the high-level workflow. This architecture is similar to
that of the Chained InfiniFilter from Section 2. The core difference is that
InfiniFilter traverses the secondary and auxiliary hash tables to process
queries and deletes while Aleph Filter does not.

Tombstones. A delete operation commences by modifying a void entry in the
canonical slot of the key to be deleted into a tombstone at the main hash
table. This causes subsequent queries to the deleted key to likely return a
negative (unless there is some other void entry in the slot, which would lead
to a false positive). To encode a tombstone, we employ a special bit string of
all ones. Figure 9 shows an example of a delete operation of Key $X$ landing
at Canonical Slot 101, where the only matching entry is a void entry. The
first step is changing the content of the slot from a void entry encoding
(i.e., 1110) into a tombstone (i.e., 1111). As a result, subsequent queries to
Key $X$ in the example will now return a negative.

Figure 9.  Aleph filter deletes a void entry by first transforming it into a
tombstone and storing the canonical address in a deletion queue. Before the
next expansion, void duplicates are identified and removed.

Deferred Removal of Duplicates. The second step of a delete operation is to
add the canonical slot of a void entry to be removed into a deletion queue,
which is structured as an append-only array. Right before the next expansion
(or contraction) operation, Aleph Filter pops one canonical slot address at a
time from the deletion queue. It uses this address as a search key to traverse
the secondary and auxiliary hash tables from largest to smallest. The search
terminates as soon as it finds a matching entry. Since larger hash tables
store longer mother hashes and we search the hash tables from largest to
smallest, the first matching entry that is found corresponds to the longest
matching mother hash. Based on this mother hash, we identify all duplicates
and remove them from the main hash table222Note that if many such deletes of
void entries take place before the next expansion and cause the filter
utilization to drop significantly below the expansion threshold again, we
delay the expansion until utilization reaches the threshold again. .

In Figure 9, for example, we pop Slot 101 from the deletion queue and use it
as a search key to probe the secondary hash table. We find a matching entry at
Slot 1 with fingerprint of 0. We concatenating these to obtain a longest
matching mother hash of 01. Since the main hash table currently has $2^{3}$
slots while the longest matching mother hash consists of two bits, we infer
that the void entry has $2^{3-2}=2$ duplicates in the main hash table, and
that their canonical slots are 001 and 101\. We proceed to delete one void
entry from each of these canonical slots. Finally, we also delete the longest
matching mother hash from the secondary hash table.

Preventing False Negatives. Figure 10 shows a more complex example of a delete
operation where there are two void entries in the target canonical slot. When
we visit the Secondary hash table, we find a run containing two mother hashes
of different lengths for these void entries: 00 and 000. The different lengths
of these mother hashes indicate that one of the void entries has two
duplicates in the filter while the other has one. There is now a question of
whether to remove the entry with the single void duplicate or the one with the
two void duplicates.

Let us first suppose the entry with the smaller mother hash (and hence more
duplicates) is removed. If this entry happens to correspond to a different key
Y with a different extended mother hash than that of key X (e.g.,
$h(Y)=...100$), we would get false negatives later when querying for Key $Y$.
Particularly, a query for Key $Y$ would reach Slot 100, fail to find a
matching entry, and return a false negative. To prevent false negatives, we
must delete the void entry with the fewest duplicates. As before, this entry
corresponds to the one with the longest matching mother hash. This ensures
that the remaining void entry’s duplicates will still match whichever entry
still exists. Hence, in Figure 10, one void entry is removed from Slot 001 of
the main hash table, and the entry with Slot 0 is removed from the secondary
hash table.

Figure 10.  Aleph filter identifies which void duplicates to remove based on
the longest matching mother hash of the deleted key.

Computational Analysis. The first two steps of a delete operation, turning a
void entry into a tombstone and adding its address to the deletion queue, each
cost $O(1)$ time to execute.

The cost of identifying and removing all duplicates for a given void entry is
deferred and incurred right before the next expansion. To quantify this cost
in the worst-case, suppose the user deletes all void entries at once. The
dominating part of the cost is to remove each individual duplicate from the
main filter, while the cost of retrieving every mother hash from the secondary
and auxiliary hash tables is a lower-order term (i.e.,
$O(\nicefrac{{X}}{{F}})$). In Section 4.2, we saw that there are at most
$O(2^{-F}\cdot X\cdot N)$ void duplicates in the main hash table in the Fixed-
Width Regime. Each of them takes constant time to remove. Hence, the overall
amount of work is $O(2^{-F}\cdot X\cdot N)$. As this work is performed after
$N$ insertions, it remains sub-constant as long as $X<2^{F}$. Since this is
the maximum number of supported expansions anyways, the cost of removing void
duplicates is amortized constant for the filter’s whole lifetime.

In the Widening Regime, we saw in Section 4.2 that there are at most
$O(2^{-F}\cdot N)$ void duplicates in the main hash table. Removing each of
them after $N$ insertions entails $O(2^{-F})$ additional overhead per
insertion. Hence, Aleph Filter supports deletes in constant time while being
able to expand indefinitely in the Widening Regime.

Memory Analysis. The secondary and auxiliary hash tables store at most $N\cdot
2^{-F}$ mother hashes altogether. The size of these hash tables is therefore
smaller by a factor of at least $2^{-F}$ from the main hash table and
therefore does not take up much memory.

###  4.4. Fast Rejuvenation Operations

In Section 2, we saw that a rejuvenation operation rehashes a queried key
after retrieving it from storage to lengthen the longest matching fingerprint
in the target run. This helps reduce the FPR. In Aleph Filter, a rejuvenation
operation can be trickier to handle if the only matching entry in the target
run is a void entry. In this case, we must also eliminate its void duplicates.

Aleph Filter handles the case where the target run only contains matching void
entries by immediately rejuvenating one void entry into the full fingerprint
of the queried key. It also adds the corresponding canonical slot into a
Rejuvenation Queue (similar to the Deletion Queue from Section 4.3). Just
before the next expansion, Aleph filter pops one address at a time from the
Rejuvenation Queue. For each address, it finds the longest matching mother
hash in the Secondary or Auxiliary Hash Tables. It compares the length of this
mother hash to the log of the number of slots in the main hash table to infer
how many void duplicates correspond to this mother hash and what their
locations are. It then removes each of these void duplicates. This process is
identical to how deletes are processed with the only exception that a void
duplicate need not be removed from the queried key’s canonical slot, as the
void entry there has already been transformed into a full fingerprint upfront.

Figure 11 shows an example of rejuvenating a void entry at Canonical Slot 100.
First, Aleph Filter transforms the void entry into a full fingerprint and adds
the canonical slot address to the Rejuvenation Queue. Before the next
expansion, Aleph filter pops address 100 from the Rejuvenation Queue and uses
it as a search key to query the Secondary Hash Table. It finds the longest
matching fingerprint of 0 at Slot 0 (the other mother hash in this run is 000,
which doesn’t match 100 along the third bit). Hence, the longest matching
mother hash is 00. This implies that the void entry had been duplicated twice
at Canonical Slots 000 and 100 of the main hash table. However, since this is
a rejuvenation operation, we know we have already replaced one void entry by a
fingerprint at Canonical Slot 100, so the only remaining duplicate to remove
is at Canonical Slot 000. Finally, we also remove the longest matching mother
hash from the Secondary Hash Table.

Similarly to deletes, rejuvenation operations do a constant amount of work
upfront while deferring and amortizing the removal of duplicates to the next
expansion. Hence, their cost is $O(1)$.

Figure 11.  Aleph filter rejuvenates a void entry by transforming it into a
full fingerprint while adding the canonical slot to a rejuvenation queue.
Before the next expansion, void duplicates are identified and removed.

###  4.5. Predictive Regime

So far, we have seen two complementary methods of preventing the FPR from
increasing as the data grows. Rejuvenation operations lengthen fingerprints to
stabilize the FPR, but they are only effective when the query workload is
targeting older entries (i.e., with shorter fingerprints). On the other hand,
the Widening Regime stabilizes the FPR by increasing the fingerprint length
assigned to newer entries, yet the cost is a higher memory footprint
comprising $F+O(\lg\lg N)$ bits per entry. This begs the question of whether
there are ways to fix the FPR without relying on rejuvenation operations or
using more memory. This section introduces the Predictive Regime to address
this challenge.

The Predictive Regime takes as a parameter an estimation from the user of how
much the data size will grow. We denote this estimate as $N_{est}$, and it is
measured as the ratio between what we think the final data size will be to the
initial filter capacity. Using this estimate, the Predictive Regime uses
Equation 4 to assign fingerprints of length $\ell(j)$ to entries inserted at
Generation $j$. The term $X_{est}=\log_{2}(N_{est})$ refers to the number of
expansions before reaching the data size estimate.

At Generation 0, Equation 4 assigns larger fingerprints of length $F+\lceil
2\cdot\log(X_{est}-1)\rceil$ bits. As the data size grows towards the estimate
($1\leq j\leq X_{est}$), it assigns an equal or shorter fingerprint length to
every subsequent generation. When we reach the data size estimate (i.e.,
$j=X_{est}+1$), the Equation assigns fingerprints of length $F$ bits, while
all fingerprints assigned in previous generations will have shrunk to at most
$F$ bits. Note that the max function keeps the inner part of the logarithm
non-zero so that the equation is defined for all $j\geq 0$.

(4) $\ell(j)=F+2\cdot\lceil\log_{2}(\max(|X_{est}-1-j|,1))\rceil$

After surpassing the data size estimate (i.e., $j>X_{est}+1$), the Predictive
Regime assumes the Widening Regime’s behavior. The absolute value function
within the logarithm in Equation 4 sets increasing fingerprint lengths to
subsequent generations to keep the FPR stable. Note that when we set
$N_{est}=1$ (implying $X_{est}=0$), the Predictive Regime is identical to the
Widening Regime from the get-go. Generally, the memory complexity for the
Predictive Regime is $F+O(\lg|\lg(N/N_{est})|)$.

Visualization. Figure 12 illustrates how the fingerprint length assigned to
newer entries first drops during the first $X_{est}$ expansions and then
increases again afterwards. The Predictive Regime initially requires more
memory than the Widening Regime. As the data grows, however, the Predictive
Regime comes to improve upon the Widening Regime across the board, especially
when the real data size is close to the estimate. This is a good trade-off as
it is more important to require fewer bits per entry when the data is large
rather than when it is small.

FPR Analysis. The analysis of the FPR with the predictive regime is similar to
the analysis of the Widening Regime from Section 4.2. The contribution of any
generation $0\leq j\leq X$ to the FPR is $\alpha\cdot f(j)\cdot
2^{\ell(j)-(X-j)}$. Equation 5 sums this up across all generations to obtain
the overall FPR.

(5) $\small FPR=\sum_{j=0}^{X+1}\alpha\cdot f(j)\cdot 2^{\ell(j)-(X-j)}$

By plugging in $X_{est}$ for $X$ in Equation 5 and simplifying, we obtain the
maximum FPR until the moment we reach the data size estimate. This turns out
to be at most $2^{-F}$ by the same analysis we saw in Section 4.2 for the FPR
in the Widening Regime. At this point, all fingerprints consist of at most $F$
bits. Hence, the memory vs. FPR trade-off is as good as we can hope for by the
time we reach the data size estimate.

By plugging in infinity for $X$ in Equation 5 and simplifying, we obtain a
maximum FPR of $2^{-F+1}$ as we surpass the data size estimate. The intuition
is that the left-hand and right-hand curves of the Predictive Regime in Figure
12 each contribute an additive factor of $2^{-F}$. It is possible to assign
fingerprints that are longer by one bit in advance to maintain a given FPR
target as we surpass the data size estimate.

We summarize the Predictive Regime’s properties in Row 3 of Table 2. Given an
accurate or even conservative estimation of how much the data size will grow,
Aleph Filter provides superior FPR vs. memory trade-offs in the Predictive
Regime relative to any other expandable filter.

Figure 12.  Given a rough estimate of how much the data size will grow, Aleph
filter requires far fewer bits per entry by the time we reach the estimate and
pass it.  Figure 13.  Aleph Filter exhibits faster queries while matching
InfiniFilter in terms of the false positive rate, the memory footprint, and
write latency.

##  5\. Evaluation

We evaluate Aleph Filter against the Fingerprint Sacrifice (FS) method and
InfiniFilter, the state-of-the-art methods for expanding filters, which were
described and analyzed in Sections 2 and 3.

Implementation. We implemented Aleph Filter within InfiniFilter’s software
library to enable a direct comparison. Aleph filter is built as a subclass of
InfiniFilter to reuse its core machinery (e.g., for parsing slots, chaining
hash tables, etc.). All baselines inherit from a common Quotient Filter class
to perform hash collision resolution. The code reuse across the baselines
means that any differences in their performance properties arise due to the
core expansion algorithm as opposed to implementation idiosyncrasies. We
employ version 11.0.16 of the Java compiler. We use xxhash (Collet, 2023) as
the hash function for all baselines. For all experiments, we generate
uniformly random 8-byte keys using java.util.Random. Each baseline is
configured to expand when 80% of the hash table slots are occupied.

Hardware. Our system is equipped with dual Intel Xeon E5-2690v4 processors,
each running at 2.6 GHz with 14 cores and two hyper-threads per core. The
machine contains 512GB of RAM, 35MB of L3 cache, 256KB of L2 cache, and 32KB
of L1 cache. Storage includes two 960GB SSDs and four 1.8TB HDDs, though these
drives are not used in the experiments. The system runs on Ubuntu 18.04.5 LTS.

Aleph Filter Reduces Query Cost. Figure 13 shows how various cost metrics
evolve as we insert data into the different baselines. All baselines are
initialized with 12-bit slots. InfiniFilter and Aleph Filter employ the Fixed-
Width Regime in this experiment. On each curve, one expansion occurs between
any two adjacent points, indicating a doubling of the data size.

Part (A) measures query cost by averaging the latency of 10,000 queries to
random non-existing keys right before the next expansion (i.e. when the filter
is as full as possible). We observe that as the data size grows, the average
latency gradually increases across all baselines as they outgrow the CPU
caches. Nevertheless, InfiniFilter’s query cost deteriorates more rapidly
since each query has to check a growing number of hash tables. The FS method
cannot expand indefinitely as eventually, all fingerprints run out of bits. In
contrast, Aleph Filter supports more expansions than the FS method while
maintaining stabler query costs as each query checks at most one hash table.

Part (B) measures the false positive rate (FPR) for the same queries as in
Part (A). The FS method exhibits a skyrocketing FPR, while InfiniFilter and
Aleph Filter each exhibit a much stabler (logarithmic) FPR. Part (C) measures
the memory footprint right before the next expansion. For the FS method, the
number of bits per entry drops as all fingerprints become shorter by one bit
in each expansion. For Aleph Filter and InfiniFilter, the memory footprint is
stable at $\approx 15$ bits per entry. The reason is that while each slot
consists of 12 bits, at most $80\%$ of the filter is utilized right before the
next expansion. This leads to $12/0.8\approx 15$ bits per entry being used
overall. Part (D) measures the average write latency while accounting for the
amortized cost of expansion. As shown, Aleph Filter is at least as performant
as the other baselines. Overall, Figure 13 demonstrates that Aleph Filter
dominates the other methods by providing faster queries, a stabler FPR, and
practically indefinite expansions, all at the same time.

Figure 14.  The Predictive Aleph Filter dominates other baselines when we have
a conservative estimation of how much the data will grow.

Better Trade-Offs While Growing Indefinitely. Figure 13 illustrates a similar
experiment under different use-case assumptions: we envision a user that
requires an FPR of at most $\approx 1\%$ while expecting the data size to grow
to a maximum of $\approx 10^{6}$ entries. However, the data size in this
scenario ends up growing beyond the user’s initial expectations. We initialize
each baseline with the smallest memory footprint that ensures that when the
data size reaches $\approx 10^{6}$ entries, the FPR is at most $\approx 1\%$.
InfiniFilter and Aleph Filter in the Widening Regime are each assigned 13 bits
per entry. We initialize the FS method with 30 bits per entry and Aleph filter
with 22 bits per entry.

Similarly to the last experiment, Part (A) shows that the Aleph Filter
outperforms InfiniFilter in terms of query cost as the data grows both in the
widening and predictive regimes. At the same time, Part (D) shows that the
different baselines have an approximately equal insertion latency.

Parts (B) and (C) show that the FS method is unable to meet the FPR
requirement once the data size exceeds $\approx 10^{6}$ entries since the
fingerprints continue to shorten in each expansion. In contrast, InfiniFilter
and Aleph Filter in the Widening Regime maintain a constant FPR from the get-
go and even after the data size surpasses $\approx 10^{6}$ entries. The trade-
off is a slowly growing memory footprint. Aleph filter in the Predictive
Regime also meets the FPR target while requiring far fewer bits per entry than
in the Widening Regime when we meet the target data size. Even after we exceed
the target data size, Aleph filter continues to require less memory than in
the Widening regime as precisely predicted in our cost models in Figure 12.
The only trade-off is that it requires a few more bits per entry from the get-
go, though this is a good deal: it’s better to require more bits per entry
when the data is small rather than when it is large. Overall, this experiment
shows that Aleph Filter can accommodate superior FPR vs. memory trade-offs,
even when we only have a rough estimate of how much the data size will grow.

Aleph Filter Supports Cheaper Deletes. Figure 15 Part (A) compares Aleph
Filter to InfiniFilter in terms of delete latency. The figure illustrates two
variants of Aleph Filter with greedy vs. lazy deletes. The former removes void
duplicates immediately during a delete operation. The latter uses tombstones
and removes void duplicates during the next expansion as described in Section
4.3. All baselines are in the Fixed-Width Regime with 12-bit slots for
experimental control.

Each baseline initially consists of $2^{9}$ slots, and we perform insertions
until it expands to $2^{25}$ slots. We then clone each baseline multiple
times. For each clone, we measure the average latency for deleting $512$
random entries, all created in the same generation. As we move from left to
right on the x-axis, we delete older entries (i.e., from earlier generations).

For all baselines, delete latency is $\approx 600$ ns when deleting recent
entries from within the most recent eight generations. We observe that a
delete operation costs more than queries or insertions in a quotient filter as
all subsequent entries in the cluster must be shifted back by one slot to keep
the cluster contiguous. As we delete older entries, the latency for
InfiniFilter increases to $\approx 800$ since more hash table accesses are
needed to find them. For Aleph Filter with greedy deletes, latency skyrockets
as we target older entries since each entry has exponentially more duplicates
in the main hash table, each of which must be removed. In contrast, for Aleph
Filter with lazy deletes, latency decreases as we delete older entries since
we simply replace one void entry with a tombstone (i.e., we do not need to
shift the remaining fingerprints in the cluster backward by one slot). An
experiment with rejuvenation operations yields a nearly identical figure to
the one shown in Figure 15 Part (A), and so we omit it. This demonstrates that
the use of tombstones makes Aleph filter practical for supporting dynamic data
despite the myriad duplicate entries that potentially must be removed when
deleting or rejuvenating an old entry.

Duplicates Removal Does not Impact Expansion Time. When Aleph filter deletes a
void entry by replacing it with a tombstone, the removal of the entry’s
potentially many duplicates is deferred to the next expansion. To ensure that
this does not degrade expansion speed, Figure 15 Part (B) measures this
overhead in both the Fixed-Width and Widening Regimes against the cost of
migrating entries into an expanded hash table. We run the experiment by
inserting entries into an initially small empty filter, causing it to expand
multiple times. From the $10^{\text{th}}$ expansion onward, we delete the
oldest remaining generation of entries before the next expansion (e.g., After
Expansion 15, we delete all entries inserted in Generation 5, etc.). During
the next expansion, all void duplicates for this generation of entries are
removed. This experiment represents the worst-case consistent toll that
deletes can inflict on expansion.

The figure shows that in the fixed-width regime, removing void duplicates
takes approximately two orders of magnitude less time than the overhead of
migrating entries into the expanded hash table. The reason is that the maximum
number of void duplicates from each generation as a proportion of the filter
size is small (i.e., $\approx 2^{-F}$ as shown in Section 4.2). In the
widening regime, entries are slower to become void as they are created with
increasing fingerprint lengths. Therefore, there are only a few generations of
void entries to be removed. Once they are removed, all subsequent deletes
occur to entries in the main hash table, and so the removal of void duplicates
inflicts no toll on expansion. The experiment demonstrates that in both
regimes, the removal of void duplicates is heavily amortized with respect to
the cost of expansion. This ensures that insertions stay fast, no matter how
many deletes targeting old entries exist in the workload.

Figure 15.  Aleph Filter supports fast deletes and rejuvenation operations by
using tombstones and deferring the removal of void duplicates to the next
expansion.

##  6\. Related Work

Compatibility with Existing Filters. The design principles of Aleph Filter are
compatible with any underlying tabular filter that supports deriving the
mother hash for each entry so that it can be reinserted into an expanded
filter. Nevertheless, several reasons make the classical Quotient filter
(Bender et al., 2012) particularly well-suited as a base method. First, a
Quotient filter makes it trivial to derive the mother hash for each key by
concatenating the fingerprint with the canonical slot address for each entry
(unlike, say, Cuckoo filters (Fan et al., 2014) and their variants (Wang et
al., 2019; Breslow and Jayasena, 2018)). Second, quotient filter supports
deletes, which is a crucial feature for applications with dynamic data
(unlike, say, XOR (Graf and Lemire, 2020), Ribbon (Dillinger et al., 2022) or
Prefix filters (Even et al., 2022)).

Furthermore, we observe that while many filters have been designed to
outperform the classic quotient filter when operating above $90\%$ capacity,
such filters are better suited for static data sets. In the context of dynamic
sets, it is more important to operate efficiently at low capacity. The reason
is that by the time we reach high capacity, the filter expands, and so the
filter spends most of its time at low capacity (e.g., Aleph Filter is tuned by
default to expand at $80\%$ utilization, at which point it returns to $40\%$
after the expansion). Compared to other filters, a quotient filter performs
particularly well at low capacity because each query incurs only one cache
miss. Furthermore, clusters are small on average when operating at low
capacity, meaning that the computational overhead for inserts, queries, and
deletes stays modest. In contrast, a Cuckoo (Fan et al., 2014) or vector
quotient filter (Pandey et al., 2021) would entail two cache misses per query,
even when operating at low capacity. For these reasons, we employ quotient
filter as the base method for Aleph filter, though implementing Aleph filter
on top of the Rank-and-Select Quotient Filter (Pandey et al., 2017) or Crate
Filter (Bercea and Even, 2020) could make for intriguing future work. In
addition, applying the Aleph Filter on top of recent range filters (Goswami et
al., 2014; Zhang et al., 2018; Luo et al., 2020; Knorr et al., 2022; Vaidya et
al., 2022) and adaptive filters (Mitzenmacher et al., 2018; Deeds et al.,
2020; Kraska et al., 2018) can also make for impactful future research.

Other Expansion Approaches. A common workaround to the filter expansion
problem is to allocate additional empty filters into which more insertions can
be made (Guo et al., 2006, 2009; Chen et al., 2017; Xie et al., 2007; Almeida
et al., 2007; Williger and Maier, 2019). The issue with such methods is that
in the worst-case, all filters need to be checked during a query. As a result,
such techniques are uncompetitive with Aleph Filter in terms of query cost.

A few filter expansion approaches (Luo et al., 2019; Xie et al., 2022) form a
hash ring of buckets to support elastic expansion. The issue is that queries,
deletes, and insertions all become $O(\log_{2}N)$ as a search tree has to be
searched to find a given entry’s bucket. In contrast, Aleph Filter performs
all operations in constant time.

Yet another paradigm involves fetching a larger fingerprint for a key from
storage, yet this involves issuing storage I/Os during expansion to fetch
additional bits for each mother hash (Wu et al., 2021). In contrast, Aleph
filter does not rely on storage I/Os to expand.

From Theory into Practice. Pagh, Segev, and Wieder prove a lower bound that if
we initialize a filter to constant capacity and expand it to contain $N$ keys,
the filter must at some point use at least $\lg\lg N$ bits per key in addition
to what is required for a filter with a fixed capacity of $N$ keys (Pagh et
al., 2013). Aleph Filter’s Widening and Predictive Regimes both meet this
lower bound. The former meets it after the $N$ data entries are inserted,
while the latter meets it before any entries are inserted.

The idea of duplicating void entries within a filter hash table to support
indefinite expansion with constant time queries can also be traced back to
Pagh, Segev, and Wieder (Pagh et al., 2013). Taffy Cuckoo Filter (Apple, 2022)
is an expandable Cuckoo filter based on these ideas, though it does not
support deletes or rejuvenation operations.

Aleph filter improves on these works in several ways. (1) It requires
$O(\lg\lg N)$ rather than $O(\lg\lg U)$ bits per key to support indefinite
growth while maintaining a stable false positive rate. This is a significant
difference if $U$, the universe size, is unknown or significantly larger than
$N$, the data size. (2) To support deletes, the data structure in (Pagh et
al., 2013) keeps track of the age of entries by encoding a binary age counter
alongside each slot for $\lg\lg N$ additional bits per key. In contrast, Aleph
filter keeps track of the ages of entries using a chain of exponentially
smaller hash tables that take up negligible space. (3) The data structure in
(Pagh et al., 2013) handles fingerprint collisions by storing the full keys of
entries with colliding fingerprints in an auxiliary dictionary. In contrast,
Aleph filter supports storing multiple identical fingerprints in the main hash
table by employing an underlying quotient filter with Robin Hood hashing. This
eliminates one dictionary access from the query path. (4) Aleph Filter
introduces the Predictive Regime, which can drastically reduce the memory
requirement.

The data structure by Liu, Yin, and Yu (Liu et al., 2020) performs constant
time operations with high probability and a lower space overhead of $\lg\lg
N+O(\lg\lg\lg N)$ bits per entry if $N$ and $U$ are polynomially related. This
matches the leading term of the lower bound. Nevertheless, this method has not
been shown to support deletes, and it does not support unbounded growth beyond
a universe size of $U$.

##  7\. Conclusion

We introduced Aleph Filter, the first practical, infinitely expandable filter
data structure to simultaneously support optimal memory vs. FPR trade-offs and
constant time operations.

## References

  * (1)
  * Almeida et al. (2007) Paulo Sérgio Almeida, Carlos Baquero, Nuno Preguiça, and David Hutchison. 2007.  Scalable Bloom Filters.  _Inform. Process. Lett._ (2007).
  * Andersen et al. (2009) David G. Andersen, Jason Franklin, Michael Kaminsky, Amar Phanishayee, Lawrence Tan, and Vijay Vasudevan. 2009.  FAWN: A Fast Array of Wimpy Nodes.  _SOSP_ (2009).
  * Apple (2022) Jim Apple. 2022\.  Stretching your data with taffy filters.  _Software: Practice and Experience_ (2022).
  * Bender et al. (2012) Michael A. Bender, Martin Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. 2012.  Don’t Thrash: How to Cache Your Hash on Flash.  _PVLDB_ (2012).
  * Bercea and Even (2020) Ioana O Bercea and Guy Even. 2020.  Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses.  _SWAT_.
  * Bloom (1970) Burton H. Bloom. 1970\.  Space/Time Trade-offs in Hash Coding with Allowable Errors.  _CACM_ 13, 7 (1970), 422–426.
  * Breslow and Jayasena (2018) Alex D Breslow and Nuwan S Jayasena. 2018.  Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, compression, and decoupled logical sparsity. In _VLDB_.
  * Celis et al. (1985) Pedro Celis, Per-Ake Larson, and J Ian Munro. 1985\.  Robin Hood Hashing. In _FOCS_.
  * Chandramouli et al. (2018) Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin J Levandoski, James Hunter, and Mike Barnett. 2018.  FASTER: A Concurrent Key-Value Store with In-Place Updates.  _SIGMOD_ (2018).
  * Chen et al. (2017) Hanhua Chen, Liangyi Liao, Hai Jin, and Jie Wu. 2017\.  The Dynamic Cuckoo Filter. In _ICNP_.
  * Clerry (1984) JG Clerry. 1984\.  Compact hash tables using bidirectional linear probing.  _IEEE Trans. Comput._ (1984).
  * Collet (2023) Yann Collet. 2023\.  XXHash.  _https://github.com/Cyan4973/xxHash_ (2023).
  * Conway et al. (2023) Alex Conway, Martín Farach-Colton, and Rob Johnson. 2023\.  SplinterDB and Maplets: Improving the Tradeoffs in Key-Value Store Compaction Policy.  _Proceedings of the ACM on Management of Data_ (2023).
  * Dayan et al. (2023) Niv Dayan, Ioana Bercea, Pedro Reviriego, and Rasmus Pagh. 2023\.  InfiniFilter: Expanding Filters to Infinity and Beyond.  _Proceedings of the ACM on Management of Data_ (2023).
  * Dayan and Twitto (2021) Niv Dayan and Moshe Twitto. 2021.  Chucky: A Succinct Cuckoo Filter for LSM-Tree. In _SIGMOD_.
  * Dayan et al. (2021) Niv Dayan, Moshe Twitto, Yuval Rochman, Uri Beitler, Itai Ben Zion, Edward Bortnikov, Shmuel Dashevsky, Ofer Frishman, Evgeni Ginzburg, Igal Maly, et al. 2021\.  The End of Moore’s Law and the Rise of the Data Processor.  _VLDB_ (2021).
  * Debnath et al. (2010) Biplob Debnath, Sudipta Sengupta, and Jin Li. 2010.  FlashStore: High Throughput Persistent Key-Value Store.  _PVLDB_ (2010).
  * Debnath et al. (2011) Biplob Debnath, Sudipta Sengupta, and Jin Li. 2011.  SkimpyStash: RAM space skimpy key-value store on flash-based storage.  _SIGMOD_ (2011).  https://doi.org/10.1145/1989323.1989327
  * Deeds et al. (2020) Kyle Deeds, Brian Hentschel, and Stratos Idreos. 2020\.  Stacked filters: learning to filter by structure.  _PVLDB_ (2020).
  * Dillinger et al. (2022) Peter C Dillinger, Lorenz Hübschle-Schneider, Peter Sanders, and Stefan Walzer. 2022.  Fast Succinct Retrieval and Approximate Membership Using Ribbon.  _SEA_ (2022).
  * Dillinger and Manolios (2009) Peter C. Dillinger and Panagiotis Pete Manolios. 2009.  Fast, All-Purpose State Storage. In _SPIN_.
  * Dutta et al. (2013) Sourav Dutta, Ankur Narang, and Suman K Bera. 2013\.  Streaming quotient filter: A near optimal approximate duplicate detection approach for data streams.  _PVLDB_ (2013).
  * Even et al. (2022) Tomer Even, Guy Even, and Adam Morrison. 2022.  Prefix Filter: Practically and Theoretically Better Than Bloom. In _VLDB_.
  * Fan et al. (2014) Bin Fan, David G. Andersen, Michael Kaminsky, and Michael Mitzenmacher. 2014.  Cuckoo Filter: Practically Better Than Bloom.  _CoNEXT_ (2014).
  * Goswami et al. (2014) Mayank Goswami, Allan Grønlund, Kasper Green Larsen, and Rasmus Pagh. 2014.  Approximate Range Emptiness in Constant Time and Optimal Space. In _SODA_.
  * Graf and Lemire (2020) Thomas Mueller Graf and Daniel Lemire. 2020.  Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters.  _JEA_ (2020).
  * Guo et al. (2006) Deke Guo, Jie Wu, Honghui Chen, and Xueshan Luo. 2006\.  Theory and Network Applications of Dynamic Bloom Filters. In _INFOCOM_.
  * Guo et al. (2009) Deke Guo, Jie Wu, Honghui Chen, Ye Yuan, and Xueshan Luo. 2009.  The Dynamic Bloom Filters.  _IEEE Trans Knowl Data Eng_ (2009).
  * Knorr et al. (2022) Eric R Knorr, Baptiste Lemaire, Andrew Lim, Siqiang Luo, Huanchen Zhang, Stratos Idreos, and Michael Mitzenmacher. 2022.  Proteus: A Self-Designing Range Filter. In _SIGMOD_.
  * Kraska et al. (2018) Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018.  The Case for Learned Index Structures.  _SIGMOD_ (2018).
  * Liu et al. (2020) Mingmou Liu, Yitong Yin, and Huacheng Yu. 2020.  Succinct Filters for Sets of Unknown Sizes. In _ICALP_.
  * Luo et al. (2019) Lailong Luo, Deke Guo, Ori Rottenstreich, Richard TB Ma, Xueshan Luo, and Bangbang Ren. 2019\.  The Consistent Cuckoo Filter. In _INFOCOM_.
  * Luo et al. (2020) Siqiang Luo, Subarna Chatterjee, Rafael Ketsetsidis, Niv Dayan, Wilson Qin, and Stratos Idreos. 2020.  Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. In _SIGMOD_.
  * McCoy et al. (2023a) Hunter McCoy, Steven Hofmey, Katherine Yelick, and Prashant Pandey. 2023a.  Singleton Sieving: Overcoming the Memory/Speed Trade-Off in Exascale $\kappa$-mer Analysis. In _SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23)_. SIAM.
  * McCoy et al. (2023b) Hunter McCoy, Steven Hofmeyr, Katherine Yelick, and Prashant Pandey. 2023b.  High-performance filters for gpus. In _Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming_.
  * Mitzenmacher et al. (2018) Michael Mitzenmacher, Salvatore Pontarelli, and Pedro Reviriego. 2018.  Adaptive cuckoo filters. In _SIAM ALENEX_.
  * Pagh et al. (2013) Rasmus Pagh, Gil Segev, and Udi Wieder. 2013.  How to Approximate a Set Without Knowing its Size in Advance. In _FOCS_.
  * Pandey et al. (2017) Prashant Pandey, Michael A Bender, Rob Johnson, and Rob Patro. 2017\.  A General-Purpose Counting Filter: Making Every Bit Count. In _SIGMOD_.
  * Pandey et al. (2021) Prashant Pandey, Alex Conway, Joe Durie, Michael A Bender, Martin Farach-Colton, and Rob Johnson. 2021\.  Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design. In _SIGMOD_.
  * Peterson (1957) W Wesley Peterson. 1957\.  Addressing for random-access storage.  _IBM journal of Research and Development_ (1957).
  * Ren et al. (2017) Kai Ren, Qing Zheng, Joy Arulraj, and Garth Gibson. 2017\.  SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data.  _PVLDB_ (2017).
  * Shetty et al. (2013) Pradeep Shetty, Richard P Spillane, Ravikant Malpani, Binesh Andrews, Justin Seyster, and Erez Zadok. 2013.  Building Workload-Independent Storage with VT-trees.  _FAST_ (2013).
  * Skarlatos et al. (2020) Dimitrios Skarlatos, Apostolos Kokolis, Tianyin Xu, and Josep Torrellas. 2020.  Elastic Cuckoo Page Tables: Rethinking Virtual Memory Translation for Parallelism. In _ASPLOS_.
  * Vaidya et al. (2022) Kapil Vaidya, Subarna Chatterjee, Eric Knorr, Michael Mitzenmacher, Stratos Idreos, and Tim Kraska. 2022.  SNARF: a Learning-Enhanced Range Filter.  _PVLDB_ (2022).
  * Wang et al. (2019) Minmei Wang, Mingxun Zhou, Shouqian Shi, and Chen Qian. 2019\.  Vacuum Filters: More Space-Efficient and Faster Replacement for Bloom and Cuckoo Filters. In _VLDB_.
  * Williger and Maier (2019) Robert Williger and Tobias Maier. 2019.  _Concurrent Dynamic Quotient Filters: Packing Fingerprints into Atomics_.  Ph.D. Dissertation. Karlsruher Institut für Technologie (KIT).
  * Wu et al. (2021) Yuhan Wu, Jintao He, Shen Yan, Jianyu Wu, Tong Yang, Olivier Ruas, Gong Zhang, and Bin Cui. 2021\.  Elastic Bloom Filter: Deletable and Expandable Filter Using Elastic Fingerprints.  _IEEE Trans Comput_ (2021).
  * Xie et al. (2007) Kun Xie, Yinghua Min, Dafang Zhang, Jigang Wen, and Gaogang Xie. 2007.  A Scalable Bloom Filter for Membership Queries. In _GLOBECOM_.
  * Xie et al. (2022) Minghao Xie, Quan Chen, Tao Wang, Feng Wang, Yongchao Tao, and Lianglun Cheng. 2022\.  Towards Capacity-Adjustable and Scalable Quotient Filter Design for Packet Classification in Software-Defined Networks.  _IEEE Open Journal of the Computer Society_ (2022).
  * Zhang et al. (2021) Fan Zhang, Hanhua Chen, Hai Jin, and Pedro Reviriego. 2021\.  The Logarithmic Dynamic Cuckoo Filter. In _ICDE_.
  * Zhang et al. (2018) Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018.  SuRF: Practical Range Query Filtering with Fast Succinct Tries.  _SIGMOD_ (2018).