11institutetext: University of Texas Rio Grande Valley, Edinburg, TX, 78539,
USA
11email<EMAIL_ADDRESS>22institutetext: University of Maryland,
College Park, MD, 20742, USA 33institutetext: University of Pittsburgh,
Pittsburgh, PA, 15260, USA
33email<EMAIL_ADDRESS>Texas A&M University - Corpus
Christi, Corpus Christi, TX, 78412, USA 55institutetext: Emory University,
Atlanta, GA, 30322, USA 66institutetext: Lehigh University, Bethlehem, PA,
18015, USA 77institutetext: University of Illinois at Chicago, Chicago, IL,
60612, USA 88institutetext: University of Southern California, Los Angeles,
CA, 90032, USA

# Interpretable Spatio-Temporal Embedding for Brain Structural-Effective
Network with Ordinary Differential Equation

Haoteng Tang🖂 11 Guodong Liu 22 Siyuan Dai 33 Kai Ye 33 Kun Zhao 33 Wenlu Wang
44 Carl Yang 55 Lifang He 66 Alex Leow 77 Paul Thompson 88 Heng Huang 22 Liang
Zhan 🖂 33

###### Abstract

The MRI-derived brain network serves as a pivotal instrument in elucidating
both the structural and functional aspects of the brain, encompassing the
ramifications of diseases and developmental processes. However, prevailing
methodologies, often focusing on synchronous BOLD signals from functional MRI
(fMRI), may not capture directional influences among brain regions and rarely
tackle temporal functional dynamics. In this study, we first construct the
brain-effective network via the dynamic causal model. Subsequently, we
introduce an interpretable graph learning framework termed Spatio-Temporal
Embedding ODE (STE-ODE). This framework incorporates specifically designed
directed node embedding layers, aiming at capturing the dynamic interplay
between structural and effective networks via an ordinary differential
equation (ODE) model, which characterizes spatial-temporal brain dynamics. Our
framework is validated on several clinical phenotype prediction tasks using
two independent publicly available datasets (HCP and OASIS). The experimental
results clearly demonstrate the advantages of our model compared to several
state-of-the-art methods.

###### Keywords:

Effective networks Spatio-temporal Ordinary differential equation Brain
dynamics dMRI fMRI

Disclaimer. This preprint is an early version of the paper that has been
accepted by MICCAI 2024. This version has not yet undergone final formatting
and proofreading. The final version will be published in the MICCAI conference
proceedings.

##  1 Introduction

Neuroimaging techniques, such as Magnetic Resonance Imaging (MRI), have
significantly advanced our understanding of the brain by providing a non-
invasive way to explore its anatomical structures and functions. Recent
advances in network science have allowed for the analysis of MRI-derived brain
networks, revealing new biomarkers for diseases such as Alzheimer’s and
enabling the study of complex neural interactions across different brain
regions [4].

Different MRI techniques reveal diverse aspects of brain organization and
dynamics. For example, diffusion MRI (dMRI) maps white matter connections by
tracking water molecule diffusion, showing how brain regions are structurally
linked. Functional MRI (fMRI), on the other hand, utilizes blood-oxygen level-
dependent (BOLD) signals to monitor brain activity, offering insights into
functional brain dynamics. Recent research utilizing fMRI BOLD signals to
delineate functional brain networks has made significant strides in
identifying patterns of connectivity through temporal correlations (e.g.,
Pearson correlation) across different brain regions. These studies highlight
the utility of fMRI in mapping the intricate web of neural interactions,
presenting the brain’s complex connectivity patterns [24, 13]. However,
traditional methods primarily focus on synchronous BOLD signals, which may
overlook the nuanced directional influences (e.g., causality) between brain
regions over time. To capture the directional influences among brain regions,
we employ Dynamic Causal Modeling (DCM) [6, 11] with time-lagged BOLD signals
to construct temporal effective connectivity networks. The temporal effective
networks represent the dynamic causal relationships where the activity of one
brain region influences another over time.

In recent years, Graph Neural Networks (GNNs) [16] have become increasingly
prominent in brain network studies, showing significant advancements in mining
brain structural and functional networks [2, 34, 35, 15, 19, 30, 28, 31, 29,
36]. Despite this progress, a scarcity of graph learning methods is designed
for dynamic effective network learning [5]. The dynamic effective brain
networks are a series of time-evolving directed graphs, which may present two
challenges when we build up GNNs on these networks. First, existing GNNs
focused on embedding nodes in undirected graphs, which may not effectively
handle directed graph embeddings. Effective brain networks feature pairs of
brain regions connected by directed edges with different weights, where the
edge direction and weight represent the causal sequence and its magnitude,
respectively. To address this, we propose a directed graph encoder
specifically designed for capturing these causal sequences in brain node
embedding. Furthermore, the dynamic effective brain network consists of
temporal sequences of brain graphs, with changing connectivity over time.
Thus, current GNNs need to be adapted to capture both spatial and temporal
dynamics of the brain. Recent efforts in dynamic graph learning include
approaches such as recurrent graph neural network [7], graph temporal
attention network [18], and graph transformer [39]. In this study, we tackle
the brain spatial-temporal dynamics with an ordinary differential equation
(ODE) model. Particularly, we introduce a graph learning framework, Spatio-
Temporal Embedding ODE (STE-ODE), designed to simultaneously solve an Ordinary
Differential Equation (ODE) and embed brain networks, capturing both their
structural and functional properties. The framework’s unique approach ensures
that the training process yields brain network embeddings that are, in
essence, solutions to the ODE, thereby intertwining the learning model with
the ODE resolution. These embedded graph representations are then leveraged
for different clinical predictions, such as brain disease classifications.
Beyond prediction tasks, our study aims to identify most significant
connectomes related to various clinical phenotypes and neurodegenerative
diseases, tracking their changes over time for different tasks. To this end,
we develop an interpretable toolkit within our directed node embedding layer.
This toolkit focuses on pinpointing the top $K$ edges with significant
temporal changes, marking them as potential biomarkers for distinct
phenotypes. This method directly connects dynamic brain network changes to
specific biological traits, enhancing our comprehension of the mechanisms tied
to different phenotypes. Our contributions can be summarized as follows. (1)
We design a directed graph embedding layer tailored for encoding effective
network under the constrains of its structural counterpart. (2) We present a
learning framework with the directed graph embedding layer, referred to as
STE-ODE, which captures temporal effective network representations by solving
an ordinary differential equation that models the brain spatial-temporal
dynamics. (3) We develop a toolkit to enhance the interpretability of our
framework, which enables the identification of the most significant connectome
changes, marking them as potential biomarkers for different clinical
phenotypes.

Figure 1: (a) describes the construction of brain effective networks from the
BOLD signals. (b) is the directed graph embedding layer for structural and
effective networks. (c) presents the STE-ODE framework for different clinical
prediction tasks.

##  2 Methodology

We first introduce our method for constructing directed effective networks
through the dynamic causal model (DCM). Additionally, we propose our
interpretable directed graph node embedding layer, which is tailored to encode
both directed effective networks and their structural counterparts.
Subsequently, we detail our comprehensive spatio-temporal framework with the
directed graph embedding layer for downstream tasks. This framework involves
solving an ordinary differential equation that captures the spatial-temporal
dynamics of the brain.

###  2.1 Preliminaries

A brain network is a weighted graph $G=\\{V,E\\}=(A,X)$ with $N$ nodes, where
$V=\\{v_{i}\\}_{i=1}^{N}$ is the set of graph nodes representing brain
regions, and $E=\\{e_{i,j}\\}$ is the edge set. $X\in\mathbb{R}^{N\times c}$
is the node feature matrix where $x_{i}\in\mathbb{R}^{1\times c}$ is the
$i-$th row of $X$ representing the node feature of $v_{i}$.
$A\in\mathbb{R}^{N\times N}$ is the adjacency matrix where
$a_{i,j}\in\mathbb{R}$ represents the weights of the edge between $v_{i}$ and
$v_{j}$. A brain structural network, denoted as $G^{s}$, is an undirected
graph, where $e^{s}_{i,j}=e^{s}_{j,i}\geq 0$. In stead, a brain effective
network, denoted as $G^{f}$, is a directed graph, where $e^{f}_{i,j}\neq
e^{f}_{j,i}\in\mathbb{R}$. The sign of $e^{f}_{i,j}$ indicates the causal
sequence between $v_{i}$ and $v_{j}$, where $e^{f}_{i,j}>0$ signifies the
causal effect on $v_{j}$ induced by $v_{i}$, vice versa. Additionally, we
denote the blood-oxygen-level-dependent (BOLD) signal obtained from fMRI as
$B\in\mathbb{R}^{N\times b}$.

###  2.2 Construction of Brain Effective Network

We employ fMRI BOLD signals to construct brain effective networks using the
dynamic causal modeling (DCM) approach [21, 25]. Each brain region serves as a
graph node embedded within the brain effective network, while the temporal
dynamic effective connectivity comprises the edge set. Given the fMRI BOLD
signals, the dynamic adjacency matrix $A^{f}(t)$ can be modeled as follows:

$\frac{dB(t)}{dt}=\alpha A^{f}(t)B(t)+Cu(t)$ (1)

$Cu(t)$ represents the term governing the influence of external neuronal
inputs $u(t)$ on the dynamics of $A^{f}$. In this work, $Cu(t)=0$ as we
concentrate on resting-state fMRI studies. The parameter $\alpha$ serves as a
constant regulating the neuronal lag among brain nodes. Consequently, we can
derive the expression of $A^{f}$ as follows:

$A^{f}(t)=\frac{1}{\alpha B(t)}\frac{dB(t)}{dt}$ (2)

We construct the effective connectivity by deriving the discrete expression of
the Eq. (2):

$A^{f}(t)=\frac{1}{\alpha
B(t)}\frac{B(t+1)-B(t)}{t+1-t}=\frac{1}{\alpha}(\frac{B(t+1)}{B(t)}-1)$ (3)

We define the connectivity between brain node $v^{f}_{i}$ and $v^{f}_{j}$ at
timepoint $t$ as follows, with $\beta=\frac{1}{\alpha}\in[0,1]$:

$A^{f}_{i,j}(t)=\beta(\frac{B_{j}(t+1)}{B_{i}(t)}-1),$ (4)

where $B_{i}$ is the BOLD signal of $v_{i}$. The process of constructing brain
effective networks is illustrated in Fig. 1(a).

###  2.3 Interpretable Structural-Effective Network Embedding

Given a directed effective network $G^{f}=(A^{f},X^{f})$, we first perform
asymmetric Laplacian normalization on its adjacency matrix. The normalized
adjacency matrix can be represented as:

$\widetilde{A}^{f}=D_{\text{in}}^{-\frac{1}{2}}A^{f}D_{\text{out}}^{-\frac{1}{2}},$
(5)

where $D_{\text{in}}$ and $D_{\text{out}}$ are in-degree and out-degree of the
adjacency matrix, respectively. Then, our node embedding layer for the
structural-effective network can be formulated as a function
$\mathcal{F}_{\mathcal{G}}$:

$\displaystyle\overline{Z}$ $\displaystyle=$
$\displaystyle\mathcal{F}_{\mathcal{G}}(\widetilde{A}^{s},\widetilde{A}^{f},X^{f};W,\gamma,\lambda)$
(6) $\displaystyle=$
$\displaystyle\sigma(\gamma\odot\widetilde{A}^{s}\odot[\lambda\widetilde{A}^{f}+(1-\lambda)\widetilde{A}^{f\top}]X^{f}W),$

where $\widetilde{A}^{s}$ represents the Laplacian-normalized adjacency matrix
of the brain structural network [16]. The brain structural network serves as
spatial information to constrain the temporal function dynamics, under the
assumption that two brain regions are functionally interconnected as long as
they are structurally connected [26]. $\sigma(\cdot)$ is a nonlinear
activation function, such as ReLU. $\lambda\in[0,1]$ is a parameter that
balances the information flow into and out of each brain node. $W$ represents
trainable parameters for brain node embedding. $\gamma\in\mathbb{R}^{N\times
N}$ are trainable parameters used for model interpretability, enabling edge
weights to adapt themselves for different prediction targets. During the model
validation stage, we utilize self-adapted edge weights to track the most
important connectomes for various prediction tasks. The brain node embedding
layer is depicted in Fig. 1(b).

###  2.4 Spatio-Temporal Embedding with ODE

Given a series of temporal effective networks (i.e., $G^{f}(t),t\in[0,T]$),
their dynamic embeddings can be modeled using the following ordinary
differential equation:

$\mathcal{F}_{\mathcal{G}}(G^{f}(t+\triangle
t),\mathbf{\Theta})=\mathcal{F}_{\mathcal{G}}(G^{f}(t),\mathbf{\Theta})+\int_{t}^{t+\triangle
t}\mathcal{F}_{\mathcal{G}}(G^{f}(\tau),\mathbf{\Theta})d\tau,$ (7)

where $\mathbf{\Theta}$ is the parameter sets (i.e.,
$\mathbf{\Theta}=\\{W,\gamma,\lambda\\}$) of the embedding function. We can
approximate the Eq. 7 into the discrete expression with our proposed node
embedding layer (see Eq. 6) as:

$\displaystyle\overline{Z}(t+1)=\overline{Z}(t)+\sigma(\gamma\widetilde{A}^{s}\odot[\lambda\widetilde{A}^{f}(t+1)+(1-\lambda)\widetilde{A}^{f\top}(t+1)]X(t+1)W).$
(8)

We unfold the temporal brain network embedding into an residual graph learning
framework. In this framework, each embedding layer processes the dynamic
effective network at $G^{f}(t+1)$, while the previous dynamic network
embedding (i.e., $\overline{Z}(t)$) is treated as a residual term.

###  2.5 STE-ODE Framework for Brain Network Predictions

The proposed STE-ODE framework, incorporating the spatio-temporal embedding
model, is depicted in Fig. 1(c). Assuming we have obtained the last node
embedding (i.e., $\overline{Z}(T)$), we employ an average global pooling layer
($Z_{G}=\frac{1}{N}\sum_{i=1}^{N}\\\ \overline{Z}_{i}(T)$) to extract the
entire graph representation. Subsequently, a fully connected neural network
(such as a Multilayer Perceptron or MLP) is employed to generate the final
classification or regression output (i.e., $\hat{y}=MLP(Z_{G})$). For the
classification task, we utilize the negative log likelihood loss function,
where $\mathcal{L}=NLL\\_Loss(\hat{y},y)$. For the regression task, we use the
$L_{2}$ loss function, where $\mathcal{L}=L_{2}Loss(\hat{y},y)$.

Table 1: Classification accuracy and F1-scores, along with their standard
deviations under 5-fold cross-validation. The best results are highlighted in
red.

Method | HCP | OASIS
---|---|---
Gender | Disease | $\epsilon 4$
Acc. | F1 | Acc. | F1 | Acc. | F1
SVM | 59.25$\pm$1.39 | 60.85$\pm$2.29$\pm$ | 57.72$\pm$0.98 | 56.58$\pm$1.93 | 58.09$\pm$2.37 | 59.83$\pm$0.99
GCN | 68.83$\pm$1.48 | 67.48$\pm$2.32 | 64.64$\pm$1.05 | 66.58$\pm$2.12 | 65.56$\pm$1.51 | 64.28$\pm$1.11
DiffPool | 73.25$\pm$0.71 | 70.43$\pm$1.87 | 71.67$\pm$0.83 | 69.58$\pm$1.75 | 69.04$\pm$2.52 | 70.42$\pm$0.87
LSTM | 70.95$\pm$1.09 | 72.37$\pm$2.16 | 68.22$\pm$2.04 | 68.90$\pm$0.74 | 69.33$\pm$1.88 | 67.31$\pm$2.65
ST-GCN | 78.44$\pm$0.86 | 76.15$\pm$1.17 | 76.26$\pm$0.98 | 77.02$\pm$1.47 | 77.20$\pm$1.79 | 78.14$\pm$1.35
FE-STGNN | 81.04$\pm$0.39 | 81.75$\pm$1.26 | 79.92$\pm$0.73 | 79.39$\pm$1.15 | 78.98$\pm$0.92 | 80.06$\pm$0.85
Ours w/o SC | 80.66$\pm$2.02 | 80.77$\pm$0.63 | 80.59$\pm$1.71 | 81.05$\pm$1.20 | 78.42$\pm$1.07 | 78.59$\pm$1.63
Ours | 82.12$\pm$1.17 | 83.97$\pm$0.96 | 80.01$\pm$1.26 | 81.31$\pm$1.37 | 81.35$\pm$0.86 | 80.92$\pm$1.03

Table 2: Regression mean absolute values with their _std_ under 5-fold cross-validation. The best results are highlighted in red. Method | HCP | OASIS
---|---|---
MMSE | DSM-Depr | DSM-Antis | MMSE
SVM | 4.06$\pm$0.33 | 4.66$\pm$0.79 | 3.43$\pm$0.59 | 3.91$\pm$0.24
GCN | 3.16$\pm$0.43 | 3.62$\pm$0.98 | 3.41$\pm$0.37 | 3.70$\pm$1.06
DiffPool | 2.82$\pm$0.93 | 3.23$\pm$0.54 | 2.09$\pm$0.56 | 2.48$\pm$0.90
LSTM | 2.74$\pm$0.91 | 2.37$\pm$0.61 | 1.91$\pm$0.47 | 1.88$\pm$0.51
ST-GCN | 1.97$\pm$0.84 | 1.35$\pm$0.17 | 1.24$\pm$0.33 | 1.19$\pm$0.23
FE-STGNN | 0.73$\pm$0.29 | 1.19$\pm$0.14 | 1.08$\pm$0.06 | 0.96$\pm$0.15
Ours w/o SC | 0.93$\pm$0.44 | 1.24$\pm$0.32 | 1.19$\pm$0.24 | 1.08$\pm$0.33
Ours | 0.62$\pm$0.23 | 1.08$\pm$0.45 | 0.92$\pm$0.79 | 0.76$\pm$0.17

##  3 Experiments

###  3.1 Dataset Description and Preprocessing

Two publicly available datasets were used to evaluate our framework. The first
includes data from $1206$ young healthy subjects (mean age $28.19\pm 7.15$,
$657$ women) from the Human Connectome Project [32] (HCP). The second includes
1326 subjects (mean age $=70.42\pm 8.95$, $738$ women) from the Open Access
Series of Imaging Studies (OASIS) dataset [17]. Details of each dataset can be
found on their official websites. The preprocessing of functional BOLD signals
and the reconstruction of structural networks were conducted using CONN [33]
and FSL Probtrackx[14], respectively. For the HCP data, both structural and
effective networks have a dimension of $82\times 82$ based on 82 ROIs defined
using FreeSurfer (V6.0) [10]. For the OASIS data, both networks have a
dimension of $132\times 132$ based on the Harvard-Oxford Atlas and AAL Atlas.
This intentional variation in network resolutions for the HCP and OASIS
datasets served to examine whether the dimension of the network or the choice
of atlas influences the efficacy of our newly developed framework.

###  3.2 Implementation Details and Experimental Setup

Implementation Details. We divided the BOLD signal $B$ into $T=5$ time
segments and calculated the mean value of the points within each segment to
construct $4$ effective networks. The edge weights of both the effective
networks and structural networks were normalized to the intervals $[-1,1]$ and
$[0,1]$, respectively. Node features were initialized by sampling from a
standard Gaussian distribution with feature dimensions set to $16$. Each
dataset was randomly partitioned into $5$ disjoint sets for $5$-fold cross-
validation in subsequent experiments. The Adam optimizer was utilized to train
the model with a batch size of $128$. The initial learning rate was set to
$0.001$ and decayed by $(1-\frac{\text{current epoch}}{\text{max
epoch}})^{0.9}$. We also regularized the training with an $L_{2}$ weight decay
of $1e^{-5}$. We terminated training if the validation loss fails to improve
for $100$ epochs, following the epoch termination condition outlined in [23],
with a maximum of $500$ epochs. All experiments were conducted on $1\times$
NVIDIA A100 GPU.
Experimental Setup. We compared our approach against $6$ baseline methods,
including $3$ static models (SVM [27], GCN [16] with global pooling, and
DiffPool [38]), and $3$ dynamic brain network embedding methods (LSTM [9], ST-
GCN [12], and FE-STGNN [5]). The $\beta$ parameter is set to $0.5$ for all
experiments. We conducted a search for optimal $\lambda$ parameter within the
range of $[0.1,0.3,0.5,0.7,0.9]$ (See Fig. 2 for details). The resulting
values were $\lambda=0.3$ for HCP and $\lambda=0.5$ for OASIS.

Figure 2: $\lambda$ parameter analysis. The optimal points are encompassed by
black boxes.

###  3.3 Brain Network Predictions

Classification Tasks. $\epsilon 4$ allele is a strong risk factor for the
Alzheimers’ Disease (AD) [22]. Table 1 presents classification results for
gender on HCP, as well as for AD and $\epsilon 4$ on OASIS. It shows that our
model achieves the highest accuracy across all tasks compared to other
methods. Meanwhile, the comparison between results obtained with and without
structural connectivity (SC) demonstrates the importance of anatomical (or
spatial) constraints on effective network representation learning.
Furthermore, the dynamic methods consistently outperform the static methods,
indicating their efficacy in brain network analysis by capturing brain
dynamics.
Regression Tasks. The Mini-Mental State Exam (MMSE [3]) serves as a
quantitative assessment tool for cognitive status in adults. The Diagnostic
and Statistical Manual of Mental Disorders (DSM [1]) offers a comprehensive
measure system for mental disorders utilized by mental health professionals
worldwide. Within the DSM system, DSM-Depr and DSM-Antis gauge two mental
disorders linked to depression and rebellious personality, respectively. Table
2 summarizes the regression results for DSM and MMSE on the HCP and OASIS
datasets, showing that our model outperforms all baseline methods with lowest
mean absolute values.

Figure 3: (a) illustrates the importance of various effective connectomes
(i.e., $|\gamma|$) for disease classification and DSM-Depr regression, with
the most crucial connectomes highlighted in bold red. (b) visualizes the brain
dynamics of the identified effective connectomes during an fMRI scan period,
where colors tending towards red indicate large values. (c) quantifies the
change in the average strength of identified connectomes during an fMRI scan
period.

###  3.4 Biological Insights and Model Interpretability

We provided two distinct biological insights from our interpretable framework.
Firstly, we utilized the designed parameter ($\gamma$) to identify the most
crucial effective connectomes for various prediction tasks. Specifically, we
pinpointed the top $400$ and $256$ connectomes (highlighted in bold red curve
in Fig. 3(a)) with the highest $|\gamma|$ weights for disease classification
on OASIS and DSM-Depr regression tasks, respectively. Our disease
classification results indicate that the highlighted connectomes are
predominantly linked to the most relevant brain nodes of Alzheimer’s Disease
(AD), such as the right/left insula cortex, anterior/posterior cingulate
gyrus, and anterior/posterior divisions of the parahippocampal gyrus.
Additionally, connectomes associated with AD-relevant subnetworks, such as the
Default Mode Network (DMN) [8, 37], are highlighted. Similarly, connectomes
connected to the most relevant brain nodes (e.g., left/right amygdala,
hippocampus and orbitofrontal) of depression are identified from DSM-Depr
regression. The Salience Network (SN) subnetwork, crucial for emotional
regulation [20], is also highlighted. Furthermore, we present the brain
temporal dynamics of the identified connectomes in Fig. 3(b), visualizing the
related $\gamma\odot A^{f}$ derived from the disease classification task at
each of the four time-points to illustrate how the effective connectomes
change during an fMRI scan period. To quantify this change, we show the
average of these $\gamma$ weighted connectomes in Fig. 3(c). It demonstrates
that the causal influence strength of the normal control(NC) group and the AD
group decays simultaneously over time. However, the degree of decline in the
AD group is more pronounced than in the NC group.

##  4 Conclusion

We propose an interpretable spatio-temporal framework with directed graph
embedding layers for learning brain effective network representations,
leveraging ordinary differential equations to model brain dynamics. Our
framework contributes to important clinical prediction tasks, pinpointing
important connectomes linked to different clinical phenotypes and illustrating
dynamic causal influence strengths across fMRI scan periods. Future work will
investigate dynamic causal influences at the level of brain ROIs.

## Acknowledgments

This study was partially supported by the Presidential Research Fellowship
(PRF) in the Department of Computer Science at the University of Texas Rio
Grande Valley, and the UTRGV seed grant, as well as by the NSF (2112631,
2045848, 2319449, 2319450, 2319451), and the NIH (R01AG071243, R01MH125928,
U01AG068057).
This work used Bridges-2 at Pittsburgh Supercomputing Center from the Advanced
Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS)
program, which is supported by National Science Foundation grants #2138259,
#2138286, #2138307, #2137603, and #2138296. Data were provided in part by the
Human Connectome Project, WU-Minn Consortium (Principal Investigators: David
Van Essen and Kamil Ugurbil; 1U54MH091657) funded by the 16 NIH Institutes and
Centers that support the NIH Blueprint for Neuroscience Research; and by the
McDonnell Center for Systems Neuroscience at Washington University; and were
provided in part by OASIS-3.

## References

  * [1] American Psychiatric Association, D., Association, A.P., et al.: Diagnostic and statistical manual of mental disorders: DSM-5, vol. 5. American psychiatric association Washington, DC (2013)
  * [2] Amodeo, C., Fortel, I., Ajilore, O., Zhan, L., Leow, A., Tulabandhula, T.: Unified embeddings of structural and functional connectome via a function-constrained structural graph variational auto-encoder. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 406–415. Springer (2022)
  * [3] Arevalo-Rodriguez, I., Smailagic, N., i Figuls, M.R., Ciapponi, A., Sanchez-Perez, E., Giannakou, A., Pedraza, O.L., Cosp, X.B., Cullum, S.: Mini-mental state examination (mmse) for the detection of alzheimer’s disease and other dementias in people with mild cognitive impairment (mci). Cochrane Database of Systematic Reviews (3) (2015)
  * [4] Bullmore, E., Sporns, O.: Complex brain networks: graph theoretical analysis of structural and functional systems. Nature reviews neuroscience 10(3), 186–198 (2009)
  * [5] Chen, D., Zhang, L.: Fe-stgnn: Spatio-temporal graph neural network with functional and effective connectivity fusion for mci diagnosis. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 67–76. Springer (2023)
  * [6] Chuang, K.C., Ramakrishnapillai, S., Madden, K., St Amant, J., McKlveen, K., Gwizdala, K., Dhullipudi, R., Bazzano, L., Carmichael, O.: Brain effective connectivity and functional connectivity as markers of lifespan vascular exposures in middle-aged adults: The bogalusa heart study. Frontiers in Aging Neuroscience 15, 1110434 (2023)
  * [7] Demirbilek, O., Rekik, I.: Recurrent multigraph integrator network for predicting the evolution of population-driven brain connectivity templates. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 584–594. Springer (2021)
  * [8] Dennis, E.L., Thompson, P.M.: Functional brain connectivity using fmri in aging and alzheimer’s disease. Neuropsychology review 24, 49–62 (2014)
  * [9] Dvornek, N.C., Ventola, P., Pelphrey, K.A., Duncan, J.S.: Identifying autism from resting-state fmri using long short-term memory networks. In: Machine Learning in Medical Imaging: 8th International Workshop, MLMI 2017, Held in Conjunction with MICCAI 2017, Quebec City, QC, Canada, September 10, 2017, Proceedings 8. pp. 362–370. Springer (2017)
  * [10] Fischl, B.: Freesurfer. Neuroimage 62(2), 774–781 (2012)
  * [11] Friston, K.J., Harrison, L., Penny, W.: Dynamic causal modelling. Neuroimage 19(4), 1273–1302 (2003)
  * [12] Gadgil, S., Zhao, Q., Pfefferbaum, A., Sullivan, E.V., Adeli, E., Pohl, K.M.: Spatio-temporal graph convolution for resting-state fmri analysis. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 528–538. Springer (2020)
  * [13] Guo, L., Zhang, Y., Tang, H., Mackin, S.R., Thompson, P.M., Huang, H., Zhan, L.: Investigating the effect of neuropsychiatric symptoms on alzheimer’s diagnosis using multi-modal brain networks. Alzheimer’s & Dementia 19, e080376 (2023)
  * [14] Jenkinson, M., Beckmann, C.F., Behrens, T.E., Woolrich, M.W., Smith, S.M.: Fsl. Neuroimage 62(2), 782–790 (2012)
  * [15] Jia, Z., Wang, Z., Hong, F., Ping, L., Shi, Y., Hu, J.: Personalized deep learning for ventricular arrhythmias detection on medical iot systems. In: Proceedings of the 39th international conference on computer-aided design. pp. 1–9 (2020)
  * [16] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
  * [17] LaMontagne, P.J., Benzinger, T.L., Morris, J.C., Keefe, S., Hornbeck, R., Xiong, C., Grant, E., Hassenstab, J., Moulder, K., Vlassenko, A.G., et al.: Oasis-3: longitudinal neuroimaging, clinical, and cognitive dataset for normal aging and alzheimer disease. MedRxiv (2019)
  * [18] Li, J., Pan, W., Huang, H., Pan, J., Wang, F.: Stgate: Spatial-temporal graph attention network with a transformer encoder for eeg-based emotion recognition. Frontiers in Human Neuroscience 17, 1169949 (2023)
  * [19] Liu, G., Chen, H., Huang, H.: Sparse shrunk additive models. In: International Conference on Machine Learning. pp. 6194–6204. PMLR (2020)
  * [20] Pinto, A.M., Geenen, R., Wager, T.D., Lumley, M.A., Häuser, W., Kosek, E., Ablin, J.N., Amris, K., Branco, J., Buskila, D., et al.: Emotion regulation and the salience network: a hypothetical integrative model of fibromyalgia. Nature Reviews Rheumatology 19(1), 44–60 (2023)
  * [21] Sanchez-Romero, R., Ramsey, J.D., Zhang, K., Glymour, M.R., Huang, B., Glymour, C.: Estimating feedforward and feedback effective connections from fmri time series: Assessments of statistical methods. Network Neuroscience 3(2), 274–306 (2019)
  * [22] Serrano-Pozo, A., Das, S., Hyman, B.T.: Apoe and alzheimer’s disease: advances in genetics, pathophysiology, and therapeutic approaches. The Lancet Neurology 20(1), 68–80 (2021)
  * [23] Shchur, O., Mumme, M., Bojchevski, A., Günnemann, S.: Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018)
  * [24] Shinn, M., Hu, A., Turner, L., Noble, S., Preller, K.H., Ji, J.L., Moujaes, F., Achard, S., Scheinost, D., Constable, R.T., et al.: Functional brain networks reflect spatial and temporal autocorrelation. Nature Neuroscience pp. 1–12 (2023)
  * [25] Smith, S.M., Miller, K.L., Salimi-Khorshidi, G., Webster, M., Beckmann, C.F., Nichols, T.E., Ramsey, J.D., Woolrich, M.W.: Network modelling methods for fmri. Neuroimage 54(2), 875–891 (2011)
  * [26] Stam, C., Van Straaten, E., Van Dellen, E., Tewarie, P., Gong, G., Hillebrand, A., Meier, J., Van Mieghem, P.: The relation between structural and functional connectivity patterns in complex brain networks. International Journal of Psychophysiology 103, 149–160 (2016)
  * [27] Suykens, J.A., Lukas, L., Van Dooren, P., De Moor, B., Vandewalle, J., et al.: Least squares support vector machine classifiers: a large scale algorithm. In: European Conference on Circuit Theory and Design, ECCTD. vol. 99, pp. 839–842. Citeseer (1999)
  * [28] Tang, H., Guo, L., Fu, X., Qu, B., Ajilore, O., Wang, Y., Thompson, P.M., Huang, H., Leow, A.D., Zhan, L.: A hierarchical graph learning model for brain network regression analysis. Frontiers in Neuroscience 16, 963082 (2022)
  * [29] Tang, H., Guo, L., Fu, X., Wang, Y., Mackin, S., Ajilore, O., Leow, A.D., Thompson, P.M., Huang, H., Zhan, L.: Signed graph representation learning for functional-to-structural brain network mapping. Medical image analysis 83, 102674 (2023)
  * [30] Tang, H., Ma, G., Guo, L., Fu, X., Huang, H., Zhan, L.: Contrastive brain network learning via hierarchical signed graph pooling model. IEEE Transactions on Neural Networks and Learning Systems (2022)
  * [31] Tang, H., Ma, G., Zhang, Y., Ye, K., Guo, L., Liu, G., Huang, Q., Wang, Y., Ajilore, O., Leow, A.D., et al.: A comprehensive survey of complex brain network representation. Meta-Radiology p. 100046 (2023)
  * [32] Van Essen, D.C., Smith, S.M., Barch, D.M., Behrens, T.E., Yacoub, E., Ugurbil, K., Consortium, W.M.H., et al.: The wu-minn human connectome project: an overview. Neuroimage 80, 62–79 (2013)
  * [33] Whitfield-Gabrieli, S., Nieto-Castanon, A.: Conn: a functional connectivity toolbox for correlated and anticorrelated brain networks. Brain connectivity 2(3), 125–141 (2012)
  * [34] Wu, Y., Zeng, D., Wang, Z., Sheng, Y., Yang, L., James, A.J., Shi, Y., Hu, J.: Federated contrastive learning for dermatological disease diagnosis via on-device learning. In: 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD). pp. 1–7. IEEE (2021)
  * [35] Wu, Y., Zeng, D., Wang, Z., Shi, Y., Hu, J.: Federated contrastive learning for volumetric medical image segmentation. In: Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part III 24. pp. 367–377. Springer (2021)
  * [36] Ye, K., Tang, H., Dai, S., Guo, L., Liu, J.Y., Wang, Y., Leow, A., Thompson, P.M., Huang, H., Zhan, L.: Bidirectional mapping with contrastive learning on multimodal neuroimaging data. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 138–148. Springer (2023)
  * [37] Yildirim, E., SONCU BÜYÜKİŞCAN, E.: Default mode network connectivity in alzheimer’s disease. Turkish Journal of Psychiatry 30(4) (2019)
  * [38] Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems 31 (2018)
  * [39] Zhao, C., Zhan, L., Thompson, P.M., Huang, H.: Revealing continuous brain dynamical organization with multimodal graph transformer. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 346–355. Springer (2022)


Rasmus Pagh 1 15th Scandinavian Symposium and Workshops on Algorithm Theory
(SWAT 2016) SWAT 2016 SWAT 2016 June 22-24, 2016 Reykjavik, Iceland 53
10.4230/LIPIcs.SWAT.2016 David Eppstein

# Cuckoo Filter: Simplification and Analysis

David Eppstein111Supported in part by NSF grant 1228639. The author would like
to thank Michael Mitzenmacher for introducing him to cuckoo filters, and for
helpful discussions on this work. Computer Science Department, University of
California, Irvine, USA

###### Abstract.

The cuckoo filter data structure of Fan, Andersen, Kaminsky, and Mitzenmacher
(CoNEXT 2014) performs the same approximate set operations as a Bloom filter
in less memory, with better locality of reference, and adds the ability to
delete elements as well as to insert them. However, until now it has lacked
theoretical guarantees on its performance. We describe a simplified version of
the cuckoo filter using fewer hash function calls per query. With this
simplification, we provide the first theoretical performance guarantees on
cuckoo filters, showing that they succeed with high probability whenever their
fingerprint length is large enough.

###### Key words and phrases:

approximate set, Bloom filter, cuckoo filter, cuckoo hashing

###### 1991 Mathematics Subject Classification:

F.2.2 Nonnumerical Algorithms and Problems

##  1\. Introduction

Bloom filters [2] are a very widely used data structure for approximately
representing sets using low space. At the cost of $O(1)$ bits per element,
they can represent any set, with constant-time membership testing, no false
negatives, and an arbitrarily low false positive rate controlled by the bits
per element. Recently, Fan, Andersen, Kaminsky, and Mitzenmacher [8] proposed
an alternative data structure for the same purpose, the _cuckoo filter_. They
show experimentally that cuckoo filters are better than Bloom filters in
several important ways: they use (up to lower-order terms) 30% less space for
the same false positive rate, matching the information-theoretic lower bound.
They have better locality of reference, accessing only two contiguous blocks
of memory per query rather than the larger numbers of a typical Bloom filter.
And, unlike a Bloom filter, they can handle element deletions as well as
insertions and queries without any increase in storage. These good features
have already led to the use of cuckoo filters in several applications [11,
10]. (For a different and more theoretical replacement for Bloom filters with
similar advantages, see Pagh, Pagh, and Rao [13].)

A cuckoo filter uses a hash table to store a small _fingerprint_ for each
element, and answers queries by testing whether the fingerprint of the queried
element is present. Each element has two hash table cells where its
fingerprints might be stored, determined by a combination of a hash of the
element and a second hash of the fingerprint. As in cuckoo hashing [14],
fingerprints already stored in the table may be moved to their second location
to make room for a newly inserted fingerprint. The performance of a cuckoo
filter is controlled by the number $n$ of elements in the set it represents,
together with three design parameters: the table size $N$ (number of cells),
block size $b$ (fingerprints that can be stored in a single cell), and
fingerprint size $f$ (bits per fingerprint). A good choice of these parameters
allows the fingerprints for all elements in the given set to be stored in the
table, giving a data structure whose false positive rate $\epsilon$ (the
probability that an element not in the set is falsely reported to be in the
set) can easily be bounded by $\epsilon\leq 2b/(2^{f}-1)$. For bad choices of
parameters, or unlucky choices of hash function, the data structure may fail,
being unable to store all its elements’ fingerprints. Therefore, it is
important to analyze the likelihood of a failure, and to understand which
combinations of parameters have a guaranteed low failure probability.

We may define the _load factor_ $\frac{n}{bN}$ to be the ratio of the number
of stored fingerprints to the number that could be stored. As this number will
be close to one, it is convenient to represent its difference from one as a
parameter $\delta$, with $1-\delta=\frac{n}{bN}$. The experiments of Fan et
al. [8], show that the load factor can be made arbitrarily close to one while
keeping the failure rate low, by a large enough choice of the block size $b$.
With this choice and a small false positive rate $\epsilon$, the storage cost
is $\bigl{(}1+o(1)\bigr{)}\log(1/\epsilon)$ bits per element, matching the
information-theoretic lower bound on any approximate set data structure.
However, this combination of low storage costs and low failure rate has been
observed only in experiments. The only theoretical analysis so far, also by
Fan et al. [8], is a lower bound showing that $f$ must be $\Omega((\log n)/b)$
to have a low failure probability. They did not provide any matching upper
bound showing that some combination of parameters can ensure a low failure
probability.

In this paper we provide the first theoretical guarantees on the performance
of cuckoo filters. To do so, we describe a simplified version of cuckoo
filters, in which we determine the two cells for an element by using its
fingerprint directly rather than by using a hash of its fingerprint. This
simplification had previously been considered by Fan et al. [8], but they
discarded it without publishing any experimental test results for it. Like Fan
et al., we do not expect this simplification to be a practical improvement,
but it makes the data structure more amenable to analysis. Under this
simplification, we show that the cuckoo filter has (up to lower-order terms,
for the same choice of block size, with polynomially small failure
probability) nearly the same maximum load rate as the blocked cuckoo hash
table of Dietzfelbinger and Weidling [5], as long as a constraint that
$f=\Omega((\log n)/b)$ is also satisfied. In particular, this analysis allows
for the load factor to be arbitrarily close to one, controlled by the block
size $b$. Thus, $f=\Omega((\log n)/b)$ is both a necessary and a sufficient
condition for the high-probability success of cuckoo filters. We also describe
how to add a stash to the simplified cuckoo filter, allowing the cuckoo filter
to take advantage of the improved reliability of cuckoo filtering with a stash
[12] without any change in the false positive rate.

Our analysis uses the unrealistic assumption of a uniformly random hash
function. However, it uses only two properties of this function: that blocked
cuckoo hashing using it succeeds with high probability, and that with high
probability it balances the load of a set of balls distributed into a
significantly smaller number of bins. Therefore, it is likely that, if the
analysis of cuckoo hashing with realistic hash functions [15, 1] is extended
to blocked cuckoo hashing, the same analysis can also be extended to cuckoo
filters. It also seems likely that the original version of cuckoo filters
behaves at least as well as the simplified version, but we leave the problem
of proving this as open for future research. Our algorithm for cuckoo
filtering with a stash depends in an essential way on the structure of the
simplified cuckoo filter, so extending it to the original cuckoo filter also
remains open.

##  2\. Preliminaries

We begin by briefly reviewing the Bloom filter, whose operations the cuckoo
filter emulates, and the cuckoo hash table on which the organization of a
cuckoo filter is based. We then describe the cuckoo filter itself, in the
original version given by Fan et al.

As a notational convenience, we use $\log$ without a base to refer to the
binary logarithm $\log_{2}$. We will also use the natural logarithm, denoted
by $\ln$.

###  2.1. Bloom filter

A Bloom filter represents a set of $n$ elements by an array of $N$ cells
($N>n$), each containing a single bit of information, together with a hash
function mapping the potential elements of the set to $k$-tuples of cells (for
a chosen constant parameter value $k$). A cell contains a nonzero bit if at
least one of the elements is mapped to it by the hash function, and a zero bit
otherwise. To insert an element into the set, the hash function is used to
find its cells, and all of these cells are set to nonzero. To query whether an
element belongs to a set, all of its cells are examined, and the result of the
query is positive if and only if they are all nonzero. There is no deletion
operation.

A false positive occurs if an element that is not part of the given set
coincidentally has all of its cells nonzero. For a given choice of $N$, and a
given set size $n$, the optimal false positive rate is achieved by setting
$k\approx\frac{N\ln 2}{n}$, so that with high probability approximately half
of the cells in the table are nonzero. With these choices, the false positive
rate is approximately $2^{-k}$. Inverting this calculation, the Bloom filter
data structure achieves a false positive rate of $\epsilon$ using
approximately $\frac{1}{\ln 2}\log(1/\epsilon)\approx 1.44\log(1/\epsilon)$
bits of storage per element [8].

Many extensions of Bloom filters have been studied. For instance, a _counting
Bloom filter_ [9] stores a counter instead of a bit per cell; it can handle
deletions, and can also be used (with a smaller number of cells) as a _count-
min sketch_ to estimate the frequency of items in a data stream [3]. An
_invertible Bloom filter_ adds even more information per cell in order to be
able to recover the identities of the set elements stored in it, when there
are few enough elements; it also allows deletions, and can be used to find
stragglers in a data stream [6], or as a sketch to communicate the symmetric
difference of two similar sets using an amount of communication proportional
to the difference [7]. However, these methods blow up the size of the data
structure by a nonconstant factor, and so are less suitable for the original
task of the Bloom filter, of representing approximate sets using very little
memory.

###  2.2. Cuckoo hashing

Cuckoo filters are based on _cuckoo hashing_ , one of many hashing based
techniques for maintaining a collection of key–value pairs and looking up the
value associated with a query key [14]. Cuckoo hashing is a form of open
addressing, a family of hashing techniques in which each cell of a hash table
stores a single key–value pair. In cuckoo hashing, each key has only two
locations in which it may be stored, which are determined by a hash function.
Thus, answering a query is simple: look in those two cells and test whether
either cell contains the query key.

Inserting a key into a cuckoo hash table is more complicated. If one of the
two cells for the key is empty, it can be inserted there. But otherwise, one
of the other keys occupying one of these two cells must be kicked out, to make
way for the new key. The kicked-out key must then be re-inserted into its
second location, possibly kicking out another key there, and so on. This
process will either eventually terminate with all keys stored in one of their
two cells, or it may fail and force the data structure to be rebuilt. A
failure may occur, for instance, when some set of $q$ keys is mapped to fewer
than $q$ cells, so there is not enough room to store all of these keys in
their cells.

In analyzing this structure, we make the standard assumption that the two
cells for each key are chosen uniformly at random, independently from each
other and from all the other keys. However, there has also been much research
on practical hash function algorithms that do not obey this assumption but
nevertheless can be made to work with cuckoo hashing [4, 15].

Two of the shortcomings of this basic version of cuckoo hashing are that the
failure probability is only moderately small (proportional to $1/n^{2}$ per
insertion, for a hash table with a constant load factor, rather than being
adjustable to arbitrary inverse polynomials) and that the load factor it can
tolerate while achieving this failure probability is also bounded away from
$1$ (in fact, bounded below $1/2$). Because of these issues, researchers have
investigated modifications of cuckoo hashing that can tolerate higher loads
with improved failure probabilities. For the results that we report on in this
paper, we need to understand two such modifications, blocked cuckoo hashing
[5] and cuckoo hashing with a stash [12].

###  2.3. Blocked cuckoo hashing

Blocked cuckoo hashing was initially developed by Dietzfelbinger and Weidling
[5]; we follow here its description by Kirsch et al. [12]. In blocked cuckoo
hashing, each cell of the hash table stores a block of up to $b$ different
key–value pairs, for a parameter $b$ chosen as part of the implementation or
initialization of the data structure. A query may examine all of the pairs in
the two cells that it searches; however, the locality of reference of the
query is still as good as in the original version of cuckoo hashing.

When a key is inserted, and one of its two cells is not full (has fewer than
$b$ keys already stored in it) it may be placed directly in that cell.
However, when both of its cells are full, one of the keys already placed in
one of those cells must be kicked out, and moved to its other location. As
with standard cuckoo hashing, this move may cause another key to move,
possibly creating a chain of dislocations. This sequence of moves can
alternatively be viewed as an augmenting path in a graph whose vertices are
table cells and whose edges are the pairs of cells that each key maps to.
Kirsch et al. write that, for the analysis of the failure probability of this
algorithm, it is unimportant how the augmenting path is found, but that an
analysis of Dietzfelbinger and Weidling [5] shows constant expected time (in
the event of no failures) for a breadth-first algorithm for finding these
augmenting paths.

In order to achieve a load factor of $1-\delta$, blocked cuckoo hashing may be
used with any block size $b\geq 1+\frac{\ln(1/\delta)}{1-\ln 2}$. Thus, for
constant $\delta$, the block size is also a constant. With this block size and
load factor, the failure probability per insertion is $O(1/n^{b})$ [12].

###  2.4. Cuckoo hashing with a stash

A _stash_ is a small collection of key–value pairs that have not been included
in a cuckoo hash table. In cuckoo hashing with a stash, the stash is used to
store key–value pairs whose insertion would otherwise cause the hash table to
fail. To perform a query in a cuckoo hash table with a stash (in either the
original or blocked form of cuckoo hashing) one first checks the two cells
that can contain the query key. Then, if the key is not found in either of
those two locations, and both locations are full, the stash is also searched.
This causes an additional sequence of memory accesses for unsuccessful
searches (or for searches of keys already in the stash), but does not slow
down most searches, and in many cases greatly improves the reliability of this
structure [12].

To apply this technique to cuckoo filtering, we need an analysis of blocked
filtering with a stash. Kirsch et al. [12] claimed that, for blocked cuckoo
hashing with block size $b$ and a stash that can hold $\sigma$ key–value
pairs, the failure probability per insertion is $O(1/n^{(\sigma+1)(b-1)+1})$.
Unfortunately, this multiplicative improvement in the exponent of failure
probability, compared to the version without the stash, is incorrect. As
Martin Dietzfelbinger and Michael Rink observed, a failure mode in which
$\sigma+2b+1$ keys all map to the same pair of cells already causes the
failure probability to be much larger than this bound.222Michael Mitzenmacher,
personal communication, February 7, 2016. Therefore, any improvement to the
reliability of blocked cuckoo hashing, obtained by adding a stash, should be
considered conjectural.

###  2.5. Cuckoo filter

A _cuckoo filter_ [8] modifies the blocked cuckoo hash table by storing a
small _fingerprint_ for each element in a set, instead of storing a key–value
pair. As in the blocked cuckoo hash table, each cell of the table can store a
small number $b$ of (fingerprints of) elements. For each element there are two
cells at which its fingerprint could be stored. To test whether an element
belongs to the filter, we examine these two cells and report yes when a
matching fingerprint is found in one of them.

In order to pack its fingerprints into these cells, the cuckoo filter (like a
cuckoo hash table) may sometimes move them to the other location for their
key. However, when it does this, it will not know the key from which the
fingerprint was generated. Therefore, it must determine the other location for
a fingerprint from the fingerprint alone. This limitation means that the two
locations for the fingerprint of a key can no longer be chosen independently
of each other, complicating the analysis of this data structure.

To keep things simple, we will assume that the number of cells $N$ in the
cuckoo filter is a power of two.333It is tempting to try modular addition in
place of exclusive ors to extend this method to other choices of $N$, but this
fails because exclusive or is an involution and modular addition isn’t.
However, the simplified cuckoo filter that we describe later can have a number
of subtables that is not a power of two. Thus, if $x$ and $y$ are indices into
the table (numbers in the range from $0$ to $N-1$ inclusive), we can combine
them by a bitwise exclusive or operation giving a number $x\oplus y$ that is
also an index into the table. Cuckoo filtering depends on three hash
functions, $\phi$, $h_{1}$, and $h_{2}$, assumed (for purposes of analysis) to
be independent random functions:

  * •

Function $\phi$ maps each potential set element to its fingerprint, an $f$-bit
binary number. It is convenient to restrict $\phi$ to have nonzero values so
that a zero fingerprint can be used to mark an unused cell of the cuckoo
filter; this has no significant effect on the asymptotic behavior of the
structure.

  * •

Function $h_{1}$ maps each potential set element to a number from $0$ to
$N-1$. This gives the location of one of the two hash table cells into which
the fingerprint for that element can be placed.

  * •

Function $h_{2}$ maps fingerprints to numbers in the range from $1$ to $N-1$
(inclusive). This is not the index of a hash table cell, but rather the
difference (or more precisely the bitwise exclusive or) of any pair of
locations at which that fingerprint should be stored.

Thus, using these functions, the fingerprint $\phi(x)$ for any element $x$ of
the given set will be stored either in cell $h_{1}(x)$ or cell $h_{1}(x)\oplus
h_{2}(\phi(x))$ of the hash table. If some subset of two or more elements all
have the same fingerprint and are all mapped by $h_{1}$ to the same cell, then
each of the fingerprints for these elements will be stored separately in one
of the two cells for these elements, even when that would cause two copies of
the same fingerprint to be stored in the same cell. That is, in order to make
deletions possible, we do not allow different elements to share a copy of a
stored fingerprint.

To query whether a value $x$ is a member of the set represented by a cuckoo
filter, we examine the $2b$ fingerprints stored at cells $h_{1}(x)$ and
$h_{1}(x)\oplus h_{2}(\phi(x))$, and check whether any of them equal
$\phi(x)$; if so we report that $x$ is indeed a member. Thus, this check
always answers correctly when $x$ belongs to the set, and may give a false
positive with probability at most $2b/2^{f-1}$ when $x$ does not belong to the
set. This query may be performed using a number of binary word operations
(including multiplication of binary numbers) proportional to the number of
words needed to store the two cells, rather than being proportional to the
larger number of fingerprints stored in these cells; see section 6 for
details.

To insert a value $x$ into the set, we compute its fingerprint and place this
fingerprint into one of the two cells associated with $x$, possibly relocating
other fingerprints along an augmenting path in the graph of cells and pairs of
cells associated with the elements of the set. The second location for each
fingerprint can be calculated from its first location and the fingerprint
itself, without needing to know the element from which the fingerprint is
generated; otherwise, the insertion operation proceeds exactly as in the
blocked cuckoo hash table. Following Kirsch et al. [12], we do not specify
precisely how the augmenting path is to be found, except to note that one
possible choice for finding it is to use a breadth first search.

To remove a value $x$ from the set, we find a matching fingerprint for $x$,
and remove it from its cell. If there are multiple matching fingerprints, we
remove only one copy; it does not matter whether that copy is the one created
when $x$ was inserted.

##  3\. The simplification and its graph

In the simplified version of cuckoo filters that we analyze here, we omit the
second hash function, $h_{2}$. Thus, given any set element $x$, the two
locations in which we may store the fingerprint $\phi(x)$ are the cells with
index $h_{1}(x)$ and $h_{1}(x)\oplus\phi(x)$. Other than this change, the
operation of the simplified cuckoo filter remains the same as in the original
version.

Figure 1. The graph of cuckoo filter cells, and pairs of cells that can be the
two locations of any fingerprint, for a cuckoo filter with 16 cells and two-
bit fingerprints. The edges for each fingerprint are colored green for
fingerprint $01$, blue for fingerprint $10$, and red for fingerprint $11$.
Left: the original cuckoo filter, with $h_{2}(01)=0111$, $h_{2}(10)=1001$, and
$h_{2}(11)=1000$. Right: the simplified cuckoo filter without $h_{2}$.

The effect of this simplification may be visualized using a graph whose
vertices are the cells of the hash table, and whose edges connect the possible
pairs of locations of a single fingerprint (Figure 1). In the original cuckoo
filter, the endpoints of each edge differ (in their exclusive or) by one of
the values of the hash function $h_{2}$. The resulting graph is regular, as
each vertex has one incident edge for each possible hash function value, and
has the symmetries of a hypercube. When $2^{f}>\log n$, the graph has
probability $\Omega(1)$ of being connected, in which case it is a Cayley graph
of the group generated by exclusive ors of the values of $h_{2}$. For smaller
values of $f$, with probability $\Omega(1)$ the hashes of all the fingerprints
will be independent vectors over the two-element field, and if so the graph
will be a disjoint union of $N/2^{2^{f}-1}$ hypercube subgraphs with
$2^{2^{f}-1}$ vertices per hypercube. However, when the second hash function
$h_{2}$ is omitted, the corresponding graph of cell pairs is much less well-
connected: it is a disjoint union of $N/2^{f}$ subgraphs, each of which is a
clique. The graph of the simplified cuckoo filter is not connected unless
$f>\log n$, a much stronger requirement than is needed for the likely
connectivity of the graph of the original cuckoo filter.

This simplification had previously been considered by Fan et al. [8]. However,
they discarded it without publishing any test results for it. They write:

> “If the alternate location were calculated …without hashing the fingerprint,
> the items kicked out from nearby buckets would land close to each other in
> the table … Hashing the fingerprints ensures that these items can be
> relocated to buckets in an entirely different part of the hash table, hence
> reducing hash collisions and improving the table utilization.”

Although we agree with this criticism, the simplification has the advantage
that it makes the method more amenable to analysis. In particular, we can
bound the failure probability of the simplified cuckoo filter by treating each
connected component of the graph described above as an independent cuckoo hash
table. Within each component, all pairs of table cells are equally likely to
be chosen by any element that maps to that component, so the previous analysis
of cuckoo hash tables may be applied directly. Although we expect the failure
probability for the original cuckoo filter to be at least as good as for the
simplified version, we do not know how to extend our analysis to it.

We remark that, instead of randomly choosing a function $h_{2}$, and
constructing a graph of cells and fingerprint-edges based on it, it would be
possible to develop a generalized version of cuckoo filtering whose graph is
any desired $(2^{f}-1)$-regular graph on the cells of the cuckoo filter. If
this graph is also $(2^{f}-1)$-edge-colorable, this may be done by associating
each fingerprint with an edge color, and making the two cells that can store
the fingerprint of an element $x$ be $h_{1}(x)$ and the neighbor of $h_{1}(x)$
along the edge with color $\phi(x)$. In the more general case, in which the
graph is not $(2^{f}-1)$-edge-colorable, this may be done by choosing a one-
to-one correspondence between fingerprints and outgoing locations at each
cell, and either storing $\phi(x)$ in $h_{1}(x)$ or storing $\varphi(x)$ in
the neighbor of $h_{1}(x)$ associated with fingerprint $\phi(x)$, where
$\varphi(x)$ is the fingerprint associated with the edge back to $h_{1}(x)$.
In this way, for instance, it would be possible to make the graph connected
even when $2^{f}\leq\log n$, something that is not possible for the original
cuckoo filter.

##  4\. Analysis

We have seen by the graphical analysis in the previous section that, in the
simplified version of cuckoo filtering that we study here, the table of cells
can be partitioned into connected components of the fingerprint-edge graph,
each of which is a clique. A single connected component consists of $2^{f}$
cells. Each two cells within a connected component have locations that differ
only within their least significant $f$ bits. We call each of these connected
components a _subtable_. Essentially, each subtable is itself a cuckoo filter,
on a subset of the input data. We analyze two different failure modes of the
global filter: either it can fail to uniformly distribute the set elements to
its subtables, or the cuckoo filtering within a subtable can fail.

###  4.1. Even distribution into subtables

We assume a cuckoo filter representing $n$ elements, with $b$ fingerprints per
cell and $N=(n/b)/(1-\delta-\delta^{2})$ cells where $\delta$ and $b$ are
related as $b\geq 1+\frac{\ln(1/\delta)}{1-\ln 2}$, the same relation used by
Kirsch et al. (Prop. 4.1) for blocked cuckoo hashing [12]. We also assume that
the fingerprints of the cuckoo filter have $f$ bits each, so that the cuckoo
filter may be partitioned into $N/2^{f}$ subtables of $2^{f}$ cells per
subtable.

The subtable into which an element $x$ is mapped is given by the most
significant $-f+\log N$ bits of $h_{1}(x)$. Assuming that $h_{1}$ is a random
hash function, the probability that each element falls into a particular
subtable $S$ is $2^{f}(1/N)$, and the events that elements fall into a
subtable (for different elements) are mutually independent. Thus, the number
of elements that are mapped into subtable $S$ is the sum of $n$ i.i.d.
Bernoulli random variables with probability $p=2^{f}(1/N)$ of being $1$ and
probability $1-p$ of being $0$. The expected number $\mu$ of elements that are
mapped into subtable $S$ is $2^{f}(n/N)=2^{f}b(1-\delta-\delta^{2})$.

We will say that a subtable is _overfull_ when the number of elements mapped
to it exceeds
$\mu(1-\delta)/(1-\delta-\delta^{2})=\mu(1+\delta^{2}+o(\delta^{2}))$, giving
it a load factor greater than $1-\delta$. By a standard form of the
multiplicative Chernoff bound, for $\delta$ sufficiently smaller than 1, the
probability that $S$ is overfull is at most
$\exp\bigl{(}-\delta^{4}\mu/3\bigr{)}$. To achieve probability $1/n^{s}$ of
avoiding any overfull subtable, it suffices (by the union bound) to achieve
probability $1/n^{s+1}$ that one table $S$ is overfull. Plugging $\mu\geq
2^{f}b$ into the probability that $S$ is overfull and solving for $f$ gives
that no table is overfull, with high probability $\geq 1-1/n^{s}$, whenever

$f\geq\log\left(\frac{3(s+1)\ln n}{\delta^{4}b}\right)=\log\left(\frac{\log
n}{b}\right)+O(1).$

where the simplification on the right hand side is based on the assumption
that $\delta$ and $s$ are constants. This $\Omega\bigl{(}\log((\log
n)/b)\bigr{)}$ constraint on $f$ will be insignificant in comparison with the
$\Omega\bigl{(}(\log n)/b\bigr{)}$ constraint coming from the failure
probability within each subtable.

We summarize the results of this subsection as a lemma:

######  Lemma 4.1.

Let $n$, $N$, $b$, $f$, and $\delta$ be as above. Suppose also that
$f=\log\bigl{(}(\log n)/b\bigr{)}+\Omega(1)$. Then the probability that a
simplified cuckoo filter with these parameters has any overfull subtables is
polynomially small, with an exponent that can be made arbitrarily large by
using a larger constant factor in the $\Omega$-notation of the bound for $f$.

###  4.2. Failure probability within each subtable

Let $S$ be a subtable that is not overfull; that is, at most
$2^{f}b/(1+\delta)$ elements of the given $n$-element set are mapped into it,
where again $f$ is the fingerprint length, $b$ is the number of fingerprints
per cell, and $\delta$ is a constant that is yet to be determined. If an
element $x$ is mapped to subtable $S$, then the location within $S$ to which
it is mapped (the low-order bits of $h_{1}(x)$) are independent of the
information causing it to be mapped to $S$ (the high-order bits of
$h_{1}(x)$), so these locations are uniformly distributed within $S$.
Additionally, the fingerprint $\phi(x)$ is uniformly distributed among all of
the valid fingerprints, and the set of locations given by the bitwise
exclusive or of these fingerprints with $h_{1}(x)$ is exactly the set of all
remaining locations within $S$. Therefore, we may analyze each subtable
independently, as a data structure containing at most $2^{f}b/(1+\delta)$
fingerprints, each of which is mapped to a uniformly random pair of distinct
locations within the subtable. That is, limiting our attention to a single
subtable has eliminated the dependence between the pairs of locations used by
each element of the cuckoo filter.

Such a data structure behaves exactly the same as a blocked cuckoo hash table
with the same elements. Thus, we can apply the previously known analysis of a
blocked cuckoo hash table directly. However we must keep in mind the fact
that, because we are studying events that hold with high (inverse-polynomial)
probability, the reduced size of a subtable (relative to an $n$-element cuckoo
hash table) translates into weaker bounds on the failure probability.

Choose $b$ and $\delta$ so that $b\geq 1+\frac{\ln(1/\delta)}{1-\ln 2}$, the
same constraints on $b$ and $\delta$ made in the analysis of blocked cuckoo
hash tables. With these choices, $\delta$ may be made arbitrarily small by
choosing $b$ large enough, and in particular the factor $(1+\delta)^{2}$
appearing in the analysis of how evenly the subtables are distributed may also
be made arbitrarily close to one. Then by the previous analysis of blocked
cuckoo hash tables, the failure probability per insertion, for a subtable
containing $\Theta(b2^{f})$ elements, is $O\bigl{(}(b2^{f})^{-b}\bigr{)}$,
inversely proportional to the $b$th power of the number of elements.

We desire the data structure to succeed with high probability; that is, for an
arbitrarily chosen constant $s$, we should be able to achieve failure
probability $O(1/n^{s})$. This will be true when $(b2^{f})^{b}=\Omega(n^{s})$
or, taking logarithms of both sides, when $b(f+\log b)>s\log n+O(1)$. The
$b\log b$ term can be assumed to cancel the $O(1)$, giving $f>(s\log n)/b$ as
a sufficient condition for high-probability success. This matches the
$f=\Omega\bigl{(}(s\log n)/b\bigr{)}$ necessary condition of Fan et al. [8]
(based on a calculation of the probability that more than $2b$ elements hash
to the same location/fingerprint pair), which also applies to this version of
cuckoo filters.

We summarize the results of this subsection as a lemma:

######  Lemma 4.2.

Let $b$ be any sufficiently large constant, and let $s$ also be constant. Let
$n$, $N$, $\delta$, and $f$ be as defined above, and suppose that $f>(s\log
n)/b$. Then the probability of failure for an insertion of an element into a
simplified cuckoo filter with these parameters and without any overfull
subtables is at most $1/n^{s}$.

###  4.3. Overall failure probability

Combining our results on the two failure modes of cuckoo filters, we have the
following result.

######  Theorem 4.3.

Let $n$ and $b$ be given, and let the maximum load factor for high-
probability-of-success blocked cuckoo hashing with block size $b$ be
$1-\delta$, where $b\geq 1+\frac{\ln(1/\delta)}{1-\ln 2}$. Then creating a
cuckoo filter for $n$ elements with block size $b$ and fingerprint size $f$
succeeds with high probability for load factor $1-\delta-\delta^{2}$ when
$f=\Omega\bigl{(}(\log n)/b\bigr{)}$. More specifically, to achieve
probability $O(1/n^{s})$ of failure it is sufficient for $b$ to be a
sufficiently large constant and for $f$ to obey the inequality $f>(s+1)(\log
n)/b$.

The $1+o(1)$ factor by which the load factor $1-\delta$ of blocked cuckoo
hashing differs from the load factor $1-\delta-\delta^{2}$ of this result is
caused by the fact that, when $n$ elements are filtered into subtables, some
subtables will likely be larger than their expected size. The term
$\delta^{2}$ could be replaced here by any fixed power of $\delta$. One way of
avoiding this change in load factor altogether would be to redo the analysis
of blocked cuckoo hashing based on the assumption that the input is chosen by
including elements independently at random at a fixed rate, rather than that
the set of input elements has a fixed size. With this modified input model,
the same model with the same rate would automatically apply to each subtable,
without need of Chernoff bounds. However, this refinement would make little
difference to our overall results.

##  5\. Cuckoo filter with a stash

The extra structure of the subtables in the simplified cuckoo filter that we
analyze here also makes it easier to add a stash to this structure, to amplify
its success probability. Specifically, we add a separate stash for each
subtable of the filter. Each stash will store a collection of
(location,fingerprint) pairs, for fingerprints that were not able to be stored
within its subtable. Because the stash is specific to the subtable, the
location part of the stash need only store the low-order $f$ bits of the
location, specifying one of the two cells within the subtable that its
fingerprint could have been stored in.

Recall that, in the simplified cuckoo filter, Each fingerprint $\phi(x)$ can
be stored in two locations, $h_{1}(x)$ and $h_{1}(x)\oplus\phi(x)$. However,
after storing the fingerprint in the filter, we no longer know which of its
two locations is $h_{1}$. Therefore, in the pair that we store in the stash,
we use the location with the smaller index, given by (the low-order $f$ bits
of) $\min(h_{1}(x),h_{1}(x)\oplus\phi(x))$.

To query whether an element $x$ belongs to the set represented by a cuckoo
filter with a stash, we test whether either of the two locations for $x$ in
the filter contains the fingerprint for $x$. If not, we determine the minimum
of those two locations, and search for the resulting (location,fingerprint)
pair in the stash for the subtable of $x$. To insert an element $x$ into the
filter, we attempt to insert it into the cuckoo filter as before, and if this
fails we add it to the stash. And to delete an element $x$, we perform a query
to determine which of the two locations for $x$ contains its fingerprint, or
whether the fingerprint is located in the stash, and remove one copy of this
fingerprint from one of its locations.

The same analysis as for the cuckoo filter without a stash goes through in the
same way as before, replacing the failure probability of a blocked cuckoo hash
table (used to prove 4.2) with any improved failure probability (currently
only conjectural) that can be proved for a blocked cuckoo hash table with a
stash.

The failure probability can also be boosted, with theoretical guarantees
rather than conjectures on the improvement, by increasing the block size $b$
rather than adding a stash. Adding a stash to each subtable would increase the
memory requirements of the data structure by only a lower-order term, but
increasing the block size could actually decrease the memory requirements
(assuming the fingerprint size $f$ is kept constant) by allowing a load factor
closer to $1$ to be used. So, given that stashes are not an improvement over
increased block sizes in the guarantees they provide, in the reliability that
can be obtained with them, or in the storage space they use, why would one
ever use a stash? The answer lies in another feature of their analysis, their
effect on the false positive rate of the data structure.

Recall that, in a cuckoo filter with block size $b$ and fingerprint size $f$,
the false positive rate is at most $2b/(2^{f}-1)$: each query examines at most
$2b$ fingerprints, each of which has a $1/(2^{f}-1)$ chance of colliding with
a given query of an element that does not belong to the set. The probability
is at most $2b/(2^{f}-1)$ rather than exactly $2b/(2^{f}-1)$ for two reasons:
a block of cells may not be full, or it may have more than one copy of the
same fingerprint. However, for typical choices of parameters, neither of these
reasons gives a large effect on the false positive rate. Based on this
calculation, increasing the block size from $b$ to $b^{\prime}$ would also
increase the false positive rate by the same $b^{\prime}/b$ factor. Naively, a
stash of size $\sigma$ would again increase the false positive rate to
$(2b+\sigma)/(2^{f}-1)$, since now there are potentially $\sigma$ additional
fingerprints that could collide with any given query. However, as we now
prove, the stash does not actually change the false positive rate at all. The
analysis below also gives a tighter analysis on the false positive rate for
cuckoo hashes even without a stash, taking into account the possibility of
under-full blocks.

######  Theorem 5.1.

The false positive rate of a cuckoo filter with $b$ blocks, $n$ elements, $N$
hash table cells, fingerprint size $f$, and load factor $1-\delta=n/Nb$,
regardless of whether it uses a stash or not, is at most
$\tfrac{2n}{N(2^{f}-1)}=\tfrac{2b(1-\delta)}{2^{f}-1}$.

######  Proof 5.2.

There are $n$ elements in the set represented by the filter, each of which
independently selects a hash table location and fingerprint. A query collides
with an element if and only if it has the same fingerprint and is mapped to
one of the same two locations. Based on this choice, any single element has a
$2/N(2^{f}-1)$ probability of colliding with the given query; the factor of
$2$ in the numerator comes from the fact that two different choices of hash
table location give rise to the same pair of cells in which the fingerprint
can be stored. The result follows by the union bound.

Based on this result, and assuming that adding a stash to a blocked cuckoo
hash table can be proved to improve its reliability, the same improvement to
reliability can be obtained in a cuckoo filter with a stash, without
sacrificing the failure rate or compensating for it by increasing the
fingerprint size.

##  6\. Bit-parallel querying

A query in a cuckoo filter involves testing whether a given fingerprint
$\phi(x)$ is stored in one of two cells of the filter. However, a fingerprint
may have many fewer bits than a word in the machine architecture on which the
filter is implemented; therefore, it may be necessary to test whether the same
fingerprint appears at each of several positions in a machine word. We
describe here how to perform this task in constant time (independent of the
number of positions to be tested) using only bitwise binary operations and
arithmetic operations on binary numbers. This analysis shows that cuckoo
filter queries can take constant time even for non-constant block sizes, as
long as the fingerprint length multiplied by the block size is $O(\log n)$,
machine words store $\Omega(\log n)$-bit words, and multiplication takes
constant time.

Suppose that each fingerprint has $f$ bits, and that $b$ fingerprints are
packed into a word $w$ of $bf$ bits. We perform the following steps:

  * •

Let $F=\sum_{i=0}^{b-1}2^{if}$, a word in which $b$ fingerprints are packed,
all equal to the number $1$. This step can be done when the filter is created,
so its calculation does not figure into the time complexity of the query
algorithm.

  * •

Compute $q=w\oplus(\phi(x)\oplus(2^{f}-1))F$. The subexpression
$\phi(x)\oplus(2^{f}-1)$ creates a fingerprint complementary to $\phi(x)$, and
the subexpression $(\phi(x)\oplus(2^{f}-1))F$ packs $b$ copies of this
complementary fingerprint into a single word. Thus, the whole expression,
which combines $w$ with these complementary fingerprints by a bitwise
exclusive or, gives a word packed with $b$ fingerprints which are all-ones
when they match $\phi(x)$, and which have at least one zero in their binary
representations when they do not match.

  * •

Compute $r=((q+F)\oplus q\oplus F)\mathbin{\&}2^{f}F$. Here the $\&$ operator
represents bitwise Boolean and. The expression $q+F$ produces a carry above
each matching fingerprint, and no carry above the fingerprints that do not
match. The expression $q\oplus F$ has, in the positions of each of these carry
bits, a binary value representing what would be in that position if no carry
occurred. The exclusive or of these two subexpressions gives the carry bits
that differ from their non-carry values. Masking with $2^{f}F$ keeps only the
bits in the carry positions of this computation, setting the other bits to
zero.

  * •

If $r$ is zero, there is no match. Otherwise, there is a match at the position
given by shifting the least significant nonzero bit of $r$ right by $f$
positions. This least significant nonzero can be calculated as
$r\mathbin{\&}\mathop{\sim}(r-1)$, where $\sim$ is the bitwise complement
operator.

Once a value with a nonzero bit at the position of the first match has been
obtained, it is straightforward to perform other operations such as removing
the fingerprint at that position; we omit the details. We summarize the
results here as a theorem:

######  Theorem 6.1.

Suppose that a cuckoo filter with block size $b$ packs each block of $b$
fingerprints into $B$ machine words, in a model of computation in which
bitwise Boolean operations and binary number arithmetic (including
multiplication) take constant time per operation. Then each query in the
filter may be performed in time $O(B)$.

## References

  * [1] Martin Aumüller, Martin Dietzfelbinger, and Philipp Woelfel.  Explicit and efficient hash families suffice for cuckoo hashing with a stash.  Algorithmica, 70(3):428–456, 2014.  doi:10.1007/s00453-013-9840-x.
  * [2] Burton H. Bloom.  Space/time trade-offs in hash coding with allowable errors.  Commun. ACM, 13(7):422–426, 1970.  doi:10.1145/362686.362692.
  * [3] Graham Cormode and S. Muthukrishnan.  An improved data stream summary: the count-min sketch and its applications.  J. Algorithms, 55(1):58–75, 2005.  doi:10.1016/j.jalgor.2003.12.001.
  * [4] Martin Dietzfelbinger and Ulf Schellbach.  On risks of using cuckoo hashing with simple universal hash classes.  In Proc. 20th ACM–SIAM Symp. Discrete Algorithms (SODA ’09), pages 795–804, 2009.
  * [5] Martin Dietzfelbinger and Christoph Weidling.  Balanced allocation and dictionaries with tightly packed constant size bins.  Theoret. Comput. Sci., 380(1-2):47–68, 2007.  doi:10.1016/j.tcs.2007.02.054.
  * [6] David Eppstein and Michael T. Goodrich.  Straggler identification in round-trip data streams via Newton’s identities and invertible Bloom filters.  IEEE Trans. Knowledge and Data Engineering, 23(2):297–306, 2011\.  arXiv:0704.3313, doi:10.1109/TKDE.2010.132.
  * [7] David Eppstein, Michael T. Goodrich, Frank Uyeda, and George Varghese.  What’s the difference? Efficient set reconciliation without prior context.  In Proc. ACM SIGCOMM 2011, pages 218–229, 2011.  doi:10.1145/2018436.2018462.
  * [8] Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher.  Cuckoo filter: Practically better than Bloom.  In Proc. 10th ACM Int. Conf. Emerging Networking Experiments and Technologies (CoNEXT ’14), pages 75–88, 2014.  doi:10.1145/2674005.2674994.
  * [9] Li Fan, Pei Cao, Jussara Almeida, and Andrei Broder.  Summary cache: A scalable wide-area web cache sharing protocol.  IEEE/ACM Trans. Networking, 8(3):281–293, 2000.  doi:10.1109/90.851975.
  * [10] M. Grissa, A.A. Yavuz, and B. Hamdaoui.  Cuckoo filter-based location-privacy preservation in database-driven cognitive radio networks.  In Proc. World Symp. Computer Networks and Information Security (WSCNIS 2015), pages 1–7. IEEE, 2015.  doi:10.1109/WSCNIS.2015.7368280.
  * [11] Vikas Gupta and Frank Breitinger.  How cuckoo filter can improve existing approximate matching techniques.  In Joshua I. James and Frank Breitinger, editors, Proc. 7th Int. Conf. Digital Forensics and Cyber Crime (ICDF2C 2015), volume 157 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pages 39–52. Springer, 2015.  doi:10.1007/978-3-319-25512-5_4.
  * [12] Adam Kirsch, Michael D. Mitzenmacher, and Udi Wieder.  More robust hashing: cuckoo hashing with a stash.  SIAM J. Comput., 39(4):1543–1561, 2010.  doi:10.1137/080728743.
  * [13] Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao.  An optimal Bloom filter replacement.  In Proc. 16th ACM–SIAM Symposium on Discrete Algorithms (SODA ’05), pages 823–829. ACM, New York, 2005.
  * [14] Rasmus Pagh and Flemming Friche Rodler.  Cuckoo hashing.  J. Algorithms, 51(2):122–144, 2004.  doi:10.1016/j.jalgor.2003.12.002.
  * [15] Mihai Pătraşcu and Mikkel Thorup.  The power of simple tabulation hashing.  J. ACM, 59(3):A14, 2012.  doi:10.1145/2220357.2220361.