# Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets:
A Comparative Analysis

Magdalen Dobson  Carnegie Mellon University<EMAIL_ADDRESS>,  Zheqi Shen
UC Riverside<EMAIL_ADDRESS>,  Guy E. Blelloch  Carnegie Mellon University
<EMAIL_ADDRESS>,  Laxman Dhulipala  University of Maryland<EMAIL_ADDRESS>,
Yan Gu  UC Riverside<EMAIL_ADDRESS>,  Harsha Vardhan Simhadri  Microsoft
Research<EMAIL_ADDRESS>and  Yihan Sun  UC Riverside<EMAIL_ADDRESS>
###### Abstract.

Algorithms for approximate nearest-neighbor search (ANNS) have been the topic
of significant recent interest in the research community. However, evaluations
of such algorithms are usually restricted to a small number of datasets with
millions or tens of millions of points, whereas real-world applications
require algorithms that work on the scale of billions of points. Furthermore,
existing evaluations of ANNS algorithms are typically heavily focused on
measuring and optimizing for queries-per-second (QPS) at a given accuracy,
which can be hardware-dependent and ignores important metrics such as build
time.

In this paper, we propose a set of principled measures for evaluating ANNS
algorithms which refocuses on their scalability to billion-size datasets.
These measures include ability to be efficiently parallelized, build times,
and scaling relationships as dataset size increases. We also expand on the QPS
measure with machine-agnostic measures such as the number of distance
computations per query, and we evaluate ANNS data structures on their accuracy
in more demanding settings required in modern applications, such as evaluating
range queries and running on out-of-distribution data. We optimize four graph-
based algorithms for the billion-scale setting, and in the process provide a
general framework for making many incremental ANNS graph algorithms lock-free.
We use our framework to evaluate the aforementioned graph-based ANNS
algorithms as well as two alternative approaches.

Artifact Availability:
The source code can be found at https://github.com/cmuparlay/pbbsbench-
vldb2024.

##  1\. Introduction

The past decade has seen the rapid growth of high-dimensional vector datasets
generated by machine learning algorithms (e.g., deep neural networks). These
datasets can contain billions of vectors representing embeddings of users,
documents, images, and other objects, and can span hundreds of dimensions. The
algorithms producing these embeddings are trained so that similar objects have
“close” embeddings (e.g., as measured by $L_{2}$ distance, or some other
metric). As a result, an important problem is to find the nearest and thus
most similar set of $k$ objects for a query point in the embedding space
$\mathbb{R}^{d}$.

Solving this problem is known as $k$-nearest neighbor search, and is
notoriously hard to solve exactly in high-dimensional spaces (Beygelzimer et
al., 2006). Since solutions for most real-world applications can tolerate
small errors, most deployments focus on the approximate nearest neighbor
search (ANNS) problem, which has been widely applied as a core subroutine in
fields such as search recommendations, machine learning, and information
retrieval (Wang et al., 2021). Modern applications are placing new demands on
ANNS data structures to be scalable to billions of points (Simhadri et al.,
[n.d.]), support streaming insertions and deletions (Singh et al., 2021;
Sundaram et al., 2013; Iwasaki and Miyazaki, 2018), work on a wide variety of
difficult datasets (Jaiswal et al., 2022), and support efficient nearest
neighbor queries as well as range queries (MetaAI, 2020). Furthermore, as the
emergence and popularity of large language models (LLMs) force a rethink of
the way software is developed and used, a new programming and application
development paradigm of retrieval augmented LLM has emerged. Application
development frameworks such as langchain (Chase, 2023), semantic kernel
(tawalke, 2023), and new information retrieval interfaces like retrieval-
augmented Chat GPT (cha, 2023) and copilot for web and enterprise (bin,
[n.d.]; Stallbaumer, 2023) use ANNS indices as their “long-term” database to
retrieve relevant information to prompt and ground LLMs.

Existing ANNS algorithms fall roughly into four categories: graph-based ANNS
algorithms (Fu et al., 2019; Subramanya et al., 2019; Malkov and Yashunin,
2020) build a graph on the input points and traverse the graph using a locally
greedy search to find the nearest neighbors of a query point. The other three
categories, locality-sensitive hashing, inverted indices (Andoni et al., 2015;
Jégou et al., 2011a; Jegou et al., 2023; Pham and Liu, 2022), and tree-based
indices (scy, 2022) all roughly work by partitioning vectors into buckets,
thus allowing queries to search only the elements in a small number of “close”
buckets. A recent empirical study (Wang et al., 2021) shows that graph-based
algorithms may be more promising to scale ANNS to billion and trillion-point
datasets, since they remain capable of searching only a small number of points
to converge to an answer as the number of input points grows.

A researcher or user of ANNS is typically subject to constraints imposed by
their target application (and corresponding data) and the available hardware.
For instance, the application will almost certainly have accuracy
requirements, a required number of nearest neighbors, and a target latency or
queries per second (QPS). Similarly, build times may need to be kept below a
certain threshold to meet data-freshness requirements. The user may have a
dataset that exhibits out-of-distribution properties, or wish to answer range
queries in addition to nearest neighbor queries. On the hardware side, their
machines may have strict memory constraints, or they may want to use
algorithms that achieve good speedup on multiple cores. The user will likely
be subject to many of these constraints, and seek to understand the tradeoffs
between them and select the best algorithm for their particular situation.
While some existing work has benchmarked ANNS in a variety of approaches
(e.g., (Wang et al., 2021; Aumüller et al., 2020; Simhadri et al., [n.d.])),
it mostly focused on smaller datasets and reported QPS; one or (usually) more
aforementioned objectives were not included.

In this paper, we provide a resource that will help users choose the right
ANNS algorithm given their application and hardware requirements at the scale
of large, billion-scale datasets. To do this, we carefully benchmark and
characterize the behavior of six successful algorithms from the ANNS
literature—DiskANN, HNSW, HCNNG, pyNNDescent, FALCONN, and FAISS (Malkov and
Yashunin, 2020; Subramanya et al., 2019; Muñoz et al., 2019; McInnes, 2020;
Andoni et al., 2015; Jégou et al., 2011a). As part of our effort, we
meticulously rewrote the four graph-based ANNS algorithms (DiskANN, HNSW,
HCNNG, and pyNNDescent) and significantly improved their parallel scalability.
Our work contributes to the benchmarking literature on ANNS in the following
key ways:

#### (1). We evaluate all algorithms at the scale of billions of data points.

Few ANNS algorithms have been carefully evaluated at the scale of billions of
data points (see Section 1.1). Many ANNS algorithms provide implementations
which, chiefly due to being poorly optimized for parallelism and memory
consumption, are unable to run on billion-size datasets, thus making it
impossible to evaluate whether the algorithmic ideas are viable at the billion
scale. We address this issue by carefully re-implementing all algorithms in
the same framework, using the same parallel primitives and scheduler, and make
novel contributions to understanding how to parallelize them.

#### (2) We evaluate machine-independent measures.

The most widely used measure of an ANNS algorithm’s quality is the QPS
(queries-per-second) it achieves at a given accuracy (recall value). While
this is arguably the most important measure of an algorithm’s performance, it
is a hardware-dependent measure that can vary greatly between different
machines, and thus the QPS results reported in the literature are difficult to
compare. In this work we measure hardware-agnostic measures such as distance
computations per query in addition to QPS.

#### (3) We study build times and design faster (parallel) build algorithms.

ANNS algorithms typically avoid high levels of scrutiny on their building
times: indeed, ANN benchmarks (Aumüller et al., 2020), the widely-consulted
benchmarking competition, and its billion-scale counterpart (Simhadri et al.,
[n.d.]) only impose a cutoff on build time rather than using it as part of
their rankings. However, in practice, indices must frequently be rebuilt as
vectors become stale and new vectors enter a system, making faster build times
highly desirable.111Very few ANNS algorithms support streaming updates while
retaining accuracy guarantees. Out of the algorithms cited in this work, only
five support insertions and deletions (Singh et al., 2021; Sundaram et al.,
2013; Iwasaki and Miyazaki, 2018; Chen et al., 2018; Klibisz, 2021), while two
others support insertions only (Malkov and Yashunin, 2020; Fu et al., 2019).
In our work we rewrite four graph-based ANNS algorithms for better parallel
build times; to do this, we provide a general technique for making incremental
algorithms (i.e., algorithms that build a graph by repeated calls to an
insertion procedure) lock-free.222Note that while incremental graph algorithms
automatically support insertions, they do not support deletions.

#### (4) We study out-of-distribution datasets.

The standard datasets for evaluating ANNS algorithms (such as BIGANN (Jégou et
al., 2011a; Jégou et al., 2011b), GIST (Jégou et al., 2011a; Jégou et al.,
2011b), DEEP (Baranchuk and Babenko, 2021), GLoVe (Aumüller et al., 2020), and
many others) all share a particular bias: the distribution of query data is
drawn from the base data. However, in many ANNS applications, the query
distribution is from an inherently different source from the base distribution
(e.g., text queries on images-embedded datasets). It is often significantly
harder to achieve good recall on such datasets, and most algorithms need to be
adapted by training with the query data (Jaiswal et al., 2022; Gupta et al.,
2022). We address this gap in the benchmarking literature, and measure how
each algorithm performs on out-of-distribution queries.

#### (5) We evaluate range queries.

Some ANNS applications, such as plagiarism or misinformation detection
(MetaAI, 2020), require returning candidates within a certain range of a query
point instead of the $k$ closest candidates. Even though standard ANNS
algorithms are easily adapted to serve range queries, ANNS algorithms are not
frequently evaluated on range search datasets. In this work, we show that with
minimal adaptation, ANNS algorithms can be used for range queries as well as
nearest neighbor queries and measure their performance on a range query
dataset.

Our efforts led to many interesting conclusions and new experimental findings
about each algorithm we benchmark, as well as new techniques for building ANNS
graphs; in Sections 5 and 6 we detail our results and conclusions, and in
Section 3 we discuss our algorithmic contributions.

###  1.1. Related Work

Approximate Nearest Neighbor Search Algorithms. Data structures for ANNS fall
roughly into four categories: graphs, inverted indices, locality-sensitive
hash tables, and trees. A graph-based algorithm constructs a graph where the
nodes represent points in the index and the edges represent proximity
relationships, and where nearest neighbor queries are answered by applying a
heuristic search on the graph. Prominent examples of graph-based algorithms
include NSG (Fu et al., 2019), HNSW (Malkov and Yashunin, 2020), DiskANN
(Subramanya et al., 2019), but the academic literature includes many other
graph-based approaches (Muñoz et al., 2019; Fu et al., 2022; Zhang et al.,
2022; Lu et al., 2022; Harwood and Drummond, 2016; Dong et al., 2011; McInnes,
2020; Iwasaki, 2016; Iwasaki and Miyazaki, 2018; Boytsov and Naidan, 2013;
ann, 2016; Chen et al., 2018; Ren et al., 2020; ope, 2022; n22, 2021; ves,
2022; kat, 2022).

Inverted File Indexing (IVF) algorithms truncate the search space of a nearest
neighbor algorithm by partitioning vectors into buckets called _posting lists_
, thus allowing a query to exhaustively search elements in only a small number
of lists instead of the entire space. One method of assignment is to use a
locality-sensitive hash (LSH) function, a hash function which is likely to map
similar vectors to the same list, and which answers queries by using the hash
function to map a query to the lists. Inverted file structures typically use a
clustering algorithm to assign vectors to posting lists, with distance to a
representative element used to determine which lists a query is mapped to.
Some notable IVF-based algorithms include PLSH (Sundaram et al., 2013), FAISS-
IVF (Jégou et al., 2011a; Douze et al., 2016; Johnson et al., 2021), and
FALCONN (Andoni et al., 2015), along with many others (Gupta et al., 2022; Xia
et al., 2013; Pham and Liu, 2022; Chen et al., 2021; Aumüller et al., 2019;
Klibisz, 2021; ope, 2022; n22, 2021).

Trees such as kd-trees or cover trees are well-known data structures for
computing nearest neighbors in metric space with low dimensionality
(Beygelzimer et al., 2006; Arya and Mount, 1993; Gu et al., 2022; Klibisz,
2021), useful for many such applications (Blelloch and Dobson, 2022; Connor
and Kumar, 2008; Yesantharao et al., 2021). Their search methods are subject
to the curse of dimensionality, but there are some modified tree-based
approaches for high dimensional search (Muja and Lowe, 2009; Maciej Kula,
2019; scy, 2022; ann, 2022).

ANNS at a Billion Scale. Next, we review what is currently known about scaling
ANN algorithms to billion-scale datasets. Some early work on ANN measured
performance on data sets with up to a billion points using various forms of
IVF (Jégou et al., 2011b; Sundaram et al., 2013; Xia et al., 2013; Baranchuk
et al., 2018) (e.g., LSH, random $k$d-trees and k-means clustering). The
results for FAISS (Douze et al., 2016), the best known of the algorithms in
this class, have been reported for the BIGANN and DEEP billion scale datasets
(Jegou et al., 2023). These works do not include comparisons to graph-based
algorithms, and focus on recall for the single nearest neighbor instead of the
$k$ nearest neighbors (i.e., 1@$n$ instead of $k$@$k$ as defined in Section
2).

A handful of papers utilize secondary storage-based algorithms to scale to
billion-scale datasets. DiskANN (Subramanya et al., 2019), a graph-based
algorithm, gives numbers for BIGANN and DEEP for a billion points. They
present limited comparisons to the FAISS (Douze et al., 2016) and IVFOADC+G+P
algorithms (Baranchuk et al., 2018). The SPANN system (Chen et al., 2021) uses
an inverted index where the posting lists are stored in secondary memory. On
billion scale data (BIGANN, DEEP and MSSPACEV) it only compares to DiskANN.
Ren et al. report on a system that uses fast memory and Intel Optane
persistent memory on billion-size datasets BIGANN and DEEP, and compare to
HNSW and NSG (Ren et al., 2020). All three of these systems only report the
latency for one query at a time, presumably because running multiple queries
across cores does not scale well due to contended access to the secondary
memory and/or internal parallelism within the query (Chen et al., 2021). The
query throughput is therefore very much lower than in-memory-based systems we
report on in this paper even accounting for machine size (i.e., number of
cores), although they have the advantage of needing less primary memory.

Johnson, Douze, and Jégou (Johnson et al., 2021) report billion scale numbers
on a GPU-based implementation using an inverted-index-based approach. Here
again, the recall rates are low and the implementation is only compared to
another GPU-based system (Wieschollek et al., 2016). Recent work on BLISS
(Gupta et al., 2022) uses the same datasets as we do at a billion scale. They
compare their approach to HNSW, but the numbers they report for HNSW are very
much worse than those we have found and that are reported here (over an order
of magnitude). Several systems work on a billion or more points, but do not
report numbers or comparisons to other systems (Fu et al., 2019; Malkov and
Yashunin, 2020; ope, 2022; Klibisz, 2021).

In this work we distinguish ourselves from these prior studies by studying in-
memory algorithms for billion-scale ANNS in the high-recall setting.

Benchmarking ANNS Algorithms. There are three prominent surveys that benchmark
ANNS algorithms, two at the scale of millions of points and one at the scale
of billions. Wang et al. published a survey of ANN algorithms at the million
scale (Wang et al., 2021), which benchmarks 13 different graph-based ANNS
algorithms. They evaluate on eight datasets as well as compare construction
times and various measures of the “quality” of an ANNS graph.

The ANN Benchmarks repository, maintained by Aumueller et al (Aumüller et al.,
2020), is a benchmark suite of ANNS algorithms where any contributor may
submit an ANNS algorithm to be included in their public evaluations. Each
algorithm is run by the authors on up to nine datasets (all with fewer than 10
million points), and the results are hosted on a public website. The ANN
Benchmarks repository uses code submitted by the inventors of each algorithm,
thus allowing each project to submit its preferred set of tuned parameters.

The Billion Scale ANNS Challenge, a competition hosted at NeurIPS 2021
(Simhadri et al., [n.d.]), focused entirely on billion-scale ANNS algorithms
on three different hardware tracks: in-memory indices, SSD indices, and custom
hardware. Competition entrants had their algorithms evaluated on six different
billion-size datasets, including one range query dataset and two datasets that
exhibit out-of-distribution characteristics.

In our work, we build on these prior studies in two key ways: first, we extend
the work of prior million-size benchmarks to the billion scale. Second, we
implement billion-scale algorithms in the same framework, with great attention
to parallelism, to evaluate the algorithmic ideas rather than specific
implementations.

##  2\. Preliminaries

Given a dataset $S$ of $n$ elements, we use a $d$-dimension point (vector) $p$
to denote each $s\in S$, and denote all such vectors as set $\mathcal{P}$. For
two points $p,q\in\mathcal{P}$, define the _distance_ between $p$ and $q$ as
${\lVert p,q\rVert}$. Smaller distance between $p$ and $q$ indicates more
similarity. In this work we typically use Euclidean distance ($L_{2}$ norm).
We also use negative inner product as a distance function in order to use ANNS
algorithms for maximum inner product search.

$\displaystyle{\lVert p,q\rVert_{2}}=\sqrt{\sum_{i=0}^{d-1}(p_{i}-q_{i})^{2}}$
Euclidean Distance $\displaystyle\lVert
p,q\rVert_{\cdot}=\sum_{i=0}^{d-1}-(p_{i}*q_{i})$ Inner Product Distance

###### Definition 2.1.

($k$-NNS) Given a set of points $\mathcal{P}$ in $d$-dimensions and a query
point $q$, the $k$ nearest neighbor search ($k$-NNS) problem finds a set
$\mathcal{K}\subseteq\mathcal{P}$ with size $|\mathcal{K}|=k$, such that,

$\max_{p\in\mathcal{K}}{\lVert
p,q\rVert}\leq\min_{p\in\mathcal{P}\setminus\mathcal{K}}{\lVert p,q\rVert}$

We define $k$-ANNS as $k$-approximate NNS. With clear context, we omit $k$ and
call them NNS and ANNS. We now introduce the measure of accuracy most commonly
used for ANNS, frequently referred to as recall.

###### Definition 2.2.

($k$-recall at $n$) Let $\mathcal{P}$ be a set of points in $d$-dimensions and
let $q$ be a query point. Let $\mathcal{K}$ denote the true $k$-nearest
neighbors of $q$ in $\mathcal{P}$. Let $\mathcal{N}\subset\mathcal{P}$ be a an
output of an ANNS algorithm of size $n$. Then the $k$-recall at $n$ of $q$ is:

$\frac{|\mathcal{K}\cap\mathcal{N}|}{|\mathcal{K}|}.$

This is also denoted as $k@n$ recall.

The most common choice of recall is 10-recall at 10 (10@10). We use the term
“recall” without a signifier to refer to 10@10 recall. Throughout this paper
we also refer to the recall of an entire query set. This refers to the average
recall over all points in the query set.

A similar problem related to geometric processing is range search, which
refers to returning all points within a certain radius as opposed to only the
$k$ closest.

###### Definition 2.3.

(Exact range search) Given a set of points $\mathcal{P}$ in $d$-dimensions, a
query point $q$, and a radius $r>0$, the exact range search problem finds a
set $\mathcal{V}$ such that:

$\forall v\in\mathcal{V},\;||v,q||\leq r\;\;\text{and}\;\;\forall
p\in\mathcal{P}\setminus\mathcal{V},\;||p,q||>r.$

In this work, we use “range search” to refer to approximate range searching.
Since the number of results returned by a range query is not fixed, an
alternate definition of recall must be provided. We use the following
definition from (Simhadri et al., [n.d.]):

###### Definition 2.4.

(Range recall) Let $\mathcal{P}$ be a set of points in $d$-dimensions and let
$\mathcal{Q}$ be a set of query points. For each $q_{i}\in\mathcal{Q}$, let
$\mathcal{V}_{i}$ denote the true set of range results and let
$\mathcal{L}_{i}$ denote the set of reported range results. Then the range
recall of set $\mathcal{Q}$ is defined as

$\frac{1}{|\mathcal{Q}|}\left(\sum_{q_{i}\in\mathcal{Q}\;|\;\mathcal{V}_{i}\not=\emptyset}\frac{|\mathcal{V}_{i}\cap\mathcal{L}_{i}|}{|\mathcal{V}_{i}|}\right).$

##  3\. ANNS Algorithms

In total we carefully study six ANNS algorithms across the different
categories (see Section 1.1). Algorithms were chosen for inclusion based on
diversity of approach: we chose four exemplars out of graph-based algorithms
(_DiskANN, HNSW, HCNNG_ and _PyNNDescent_), one inverted index algorithm
(_FAISS-IVF_), and one locality-sensitive hashing algorithm (_FALCONN_). We
provide more details on excluded ANNS algorithms in Section 3.3.

###  3.1. Graph-Based Algorithms

In this section we introduce graph-based nearest neighbor search and
demonstrate how an incremental ANNS graph algorithm can be made lock-free. We
first present the high-level idea of the graph-based approaches, and then
introduce each of them in detail and discuss our efforts to make them
scalable.

Given point set $\mathcal{P}$, an ANNS graph $G_{\mathcal{P}}$ refers to a
directed graph with vertices representing points in $\mathcal{P}$. For a point
$p\in\mathcal{P}$, we define $\text{N}_{\text{out}}(p)$, or the out-neighbors
of $p$, as the set of points $q$ where $(p,q)$ is a directed edge in
$G_{\mathcal{P}}$. We illustrate nine points, their coordinates and an example
of an ANNS graph on them in Figure 1. The neighborhood of a point in the graph
roughly corresponds to other nearby points. The queries follow the graph edges
to find the nearest neighbors of the points.

Almost all ANNS graph algorithms use a variant of greedy (beam) search to
answer a NNS query. Such a search for a query $q$ maintains a _beam_
$\mathcal{L}$ with size at most $L$ as a set of candidates as the nearest
neighbors of $q$. We call $L$ the _width_ of the beam. We present an example
in Figure 1. The beam starts with a single starting point $s$. In each step,
the algorithm pops the closest vertex to $q$ from $\mathcal{L}$, and
_processes_ it by adding all its out-neighbors to the beam. We use a _visited
set_ $\mathcal{V}$ to maintain all points that have been processed (i.e., the
neighborhood of the point has been traversed and added to the beam). If
$|\mathcal{L}|$ exceeds $L$, only the $L$ closest points will be kept.

Figure 1. An example of ANNS graph and a greedy search. The arrows in the
graph represents directed edges in the proximity graph, which is a mix of long
and short edges. Below is an example of searching the nearest neighbor of
point $q$ (red point). The algorithm starts with adding the centroid $A$ as
the only point in the beam $\mathcal{L}$, and then in every step, finds the
closest unprocessed point in $\mathcal{L}$ (to $q$) and adds its out-
neighbors. Once $|\mathcal{L}|$ goes beyond $L$, it is refined to keep only
the $L$ nearest points. A set $\mathcal{V}$ is maintained for all processed
vertices. When all vertices in $\mathcal{L}$ are also in $\mathcal{V}$, the
algorithm finishes.

Input: Point $p$, starting point $s$, beam width $L$, integer $k$.

Output: Set $\mathcal{V}$ of visited points and set $\mathcal{K}$ of
$k$-nearest neighbors to point $p$.

1

2$\mathcal{V}\;\leftarrow\;\emptyset$

3 $\mathcal{L}\;\leftarrow\;\\{s\\}$

4 while  _$\mathcal{L}\setminus\mathcal{V}\not=\emptyset$_ do

5 $p^{*}\;\leftarrow\;\arg\min_{(q\in\mathcal{L}\setminus\mathcal{V})}\lVert
p,q\rVert$

6 $\mathcal{V}\;\leftarrow\mathcal{V}\cup\\{p^{*}\\}$

7 $\mathcal{L}\;\leftarrow\;\mathcal{L}\cup\text{N}_{\text{out}}(p^{*})$

8 if  _$|\mathcal{L}| >L$_ then retain only the $L$ closest points to $p$ in
$\mathcal{L}$

9

10$\mathcal{K}\;\leftarrow\;k$ closest points to $p$ in $\mathcal{V}$

11 return _$\mathcal{V},\mathcal{K}$_

Algorithm 1 greedySearch($p,s,L,k$).

Intuitively, for greedy search to converge quickly and produce accurate
answers, the ANNS graph should contain a mix of long edges (connecting with
neighbors that are far away) and short edges (connecting with neighbors that
are close). Long edges enable fast navigation from the starting point towards
the region close to a query point, and short edges enable the search to
quickly converge once it reaches this region of the graph.

#### Incremental ANNS Graph Algorithms

To build an ANNS graph, many existing systems use incremental algorithms,
which insert all points into the graph in some order, and upon inserting a
point, adds edges from the current point to the existing points in the graph.
We present the high-level idea of the insert() routine in Algorithm 2. Most
incremental graph algorithms, such as DiskANN, HNSW, and NSG (Subramanya et
al., 2019; Malkov and Yashunin, 2020; Fu et al., 2019) use the search
procedure as a substep during insertion. When inserting point $p$, after a
greedy search on the existing graph, the out-neighbors of $p$ are chosen among
the set of points visited during the search, as indicated by the prune()
routine in Algorithm 2. As discussed further in Section 3, the prune() routine
selects for a variety of edge lengths and directions. In addition to selecting
out-neighbors of $p$, the insert() algorithm must add $p$ to the out-neighbors
of other points in the graph so $p$ is reachable during a search. In the
example, this is done by adding $p$ to each of $p$’s out-neighbors, and
pruning if the degree bound $R$ is exceeded by this addition. Pruning is
specific to each system, and we will introduce examples in Section 3.

Input: Point $p$, starting point $s$, beam width $L$, degree bound $R$.

Output: Point $p$ is inserted into the nearest neighbor graph.

1 $\mathcal{V},\mathcal{K}\;\leftarrow\;\text{greedySearch}(p,s,L,1)$

2

3$\text{N}_{\text{out}}(p)\;\leftarrow\;\text{prune}(\mathcal{V})$

4 for  _$q\in\text{N}_{\text{out}}(p)$_ do

5 $\text{N}_{\text{out}}(q)\;\leftarrow\;\text{N}_{\text{out}}(q)\cup\\{p\\}$

6 if  _$|\text{N}_{\text{out}}(q)| >R$_ then

7
$\text{N}_{\text{out}}(q)\;\leftarrow\;\text{prune}(\text{N}_{\text{out}}(q))$

8

Algorithm 2 insert($p,s,R,L$).

Many existing parallel implementations of incremental ANNS graph construction
run insertions in a parallel for loop, with per-point locks used to ensure
that the out-neighbors of each point are accessed safely. However, this may
cause high contention when the number of available threads is large. To avoid
contention at high numbers of threads, our implementation is inspired by a
list of recent work of parallel incremental construction (Blelloch et al.,
2016; Gu et al., 2023, 2022; Shen et al., 2022; Dhulipala et al., 2021). The
high-level idea is to insert points in batches of exponentially increasing
size, as shown in Algorithm 3, which implements the insert() routine in
batches. This approach, also called _prefix-doubling_ , provides the balancing
among parallelism, low contention, and efficient work. In particular, all
points are splitted into at most $O(\log n)$ batches and each batch is
processed in parallel. We use this approach to parallelize DiskANN and HNSW,
and make them scalable to billion scale datasets.

Input: Point set $\mathcal{P}$, starting point $s$, beam width $L$, degree
bound $R$.

Output: A nearest neighbor graph consisting of all points in $\mathcal{P}$ and
start point $s$.

1 $i\;\leftarrow\;0$

2 while  _$2^{i}\;\leq\;|\mathcal{P}|$_ do

3 parallel for  _$j\in[2^{i},2^{i+1})$_ do

4
$\mathcal{V},\mathcal{K}\;\leftarrow\;\text{greedySearch}(\mathcal{P}[j],s,L)$

5
$\text{N}_{\text{out}}(\mathcal{P}[j])\;\leftarrow\;\text{prune}(\mathcal{V})$

6

7
$\mathcal{B}\;\leftarrow\;\bigcup_{j=2^{i}}^{2^{i+1}-1}\text{N}_{\text{out}}(P[j])$

8 parallel for  _$b\in\mathcal{B}$_ do

// Find $\mathcal{N}$ as all points in the current batch that added $b$ as
their neighbors

9
$\mathcal{N}\;\leftarrow\;\\{\mathcal{P}[j]\;|\;j\in[2^{i},2^{i+1})\;\land\;b\in\text{N}_{\text{out}}(\mathcal{P}[j])\\}$

10
$\text{N}_{\text{out}}(b)\;\leftarrow\;\text{N}_{\text{out}}(b)\cup\mathcal{N}$

11 if  _$|\text{N}_{\text{out}}(b)| >R$_ then
$\text{N}_{\text{out}}(b)\;\leftarrow\;\text{prune}(\text{N}_{\text{out}}(b))$

12

13 $i\;\leftarrow\;i+1$

14

Algorithm 3 batchBuild($\mathcal{P},s,R,L$).

Next, we introduce each individual graph-based algorithm we consider in this
paper. We carefully redesign each algorithm so it uses only primitives that
are highly parallelizable. We implement many of the basic primitives (e.g.,
sorting and filtering) from a parallel library ParlayLib (Blelloch et al.,
2020). In all cases, we optimize for space usage by using a flat array to
store edge identifiers.

#### DiskANN

DiskANN (Subramanya et al., 2019) is a system consisting of an incremental in-
memory ANNS graph algorithm as well as a system for storing the graph on an
SSD. We focus on only the incremental ANNS graph algorithm as our work only
deals with in-memory graph algorithms. The in-memory DiskANN algorithm is
almost completely described by Algorithm 2, with the exception of the pruning
step. In the paper on the navigating spreading-out graph (NSG) (Fu et al.,
2019), Fu et al. proposed a pruning method on the visited list $\mathcal{V}$:
roughly, they repeatedly select the point $p^{*}$ closest to $p$ in
$\mathcal{V}$, then filter out points $q$ that are closer to $p^{*}$ than
$p^{*}$ is to $p$. This can be thought of as pruning out long edges of
triangles, and the logic is that it streamlines navigation by removing
redundant edges. Subramanya et al. (Subramanya et al., 2019) refine this
pruning step by adding a slack parameter $\alpha$ which can be used to select
for a denser or sparser graph.

To adapt the in-memory version of DiskANN for machines with hundreds of cores,
we implemented a parallel batch build as shown in Algorithm 3. A crucial
ingredient for DiskANN’s parallelization is a parallel semisort (Gu et al.,
2015; Dong et al., 2023). Semisort enables an unsorted list of edges—i.e., the
back-edges added to the graph in Lines 3–3 of Algorithm 2—to be grouped by the
vertex whose out-neighbors they are joining, as shown in Lines 7–11.

#### HNSW

The hierarchical navigable small world (HNSW) algorithm (Malkov and Yashunin,
2020) builds a hierarchical structure also in an incrementall manner, where
each layer is a navigable small world (NSW) graph (Ponomarenko et al., 2011).
In a NSW graph, nodes tend to be connected to their near neighbors in the
point set. Although most nodes are not directly connected, the navigable
property allows a search to reach any node in a small number of hops.

HNSW builds multiple layers of NSW graphs so that the nodes in an upper layer
always appear in the lower layers. Each node corresponds to an input point.
The number of nodes in each layer increases geometrically from top to bottom,
and the bottom layer contains all the input points (conceptually this approach
is similar to a skip list). Insertion an NSW graph is as described in
Algorithm 2. The HNSW prune() is similar to the DiskANN pruning algorithm in
that it prunes out long edges of triangles, but it combines this idea with
additional heuristics.

During the search, HNSW traverses through all the layers to quickly approach
the target point. It starts at the top layer, looks for the single nearest
neighbor $p$ of the query point using Algorithm 1 with a beam size of 1, and
shifts down to the next layer at $p$ to repeat the procedure until reaches the
second-to-last layer. Then, taking the current result as the entry point, it
starts Algorithm 1 for $k$-nearest neighbors at the bottom layer.

We use parallel prefix-doubling to support efficient construction in the HNSW
algorithm. In addition to using parallel primitives from ParlayLib (Blelloch
et al., 2020), we replaced all of the internal data structures in HNSW with
non-locked equivalents. The main difficulty in adapting HNSW to hundred-core
machines comes from its multi-layer structure. To insert a batch of elements,
the elements are inserted in parallel without locks into the top layer of the
graph, then the second layer, and so on. Our implementation of HNSW also adds
a parameter of $\alpha$ in the prune() function (as in DiskANN) to control the
graph density in order to compare with the other algorithms more fairly.

#### HCNNG

The hierarchical clustering-based nearest neighbor graph (HCNNG) (Muñoz et
al., 2019) uses hierarchical clustering to separate the point set into smaller
cells, and calculates edges of the graph within points in those cells. It
recursively builds a hierarchical cluster tree by selecting two points from
the dataset at random, dividing the point set into those closer to the first
point and those closer to the second, and then recursing on the two halves
until a constant leaf size is reached. Within a leaf, it computes a degree-
bounded minimum spanning tree (MST), and the edges of the MST become the edges
in the graph. This process is repeated a constant number of times, with new
edges merged into the final graph on each iteration.

We parallelized HNNCG without locks by parallelizing recursive calls during
the hierarchical clustering. Since the process of assigning points to leaves
is relatively cheap, the majority of the work is over the MST construction
within the leaves, which in principle offers abundant parallelism, but
requires care when parallelizing. In particular, since computing an MST on the
points requires first precomputing the all-pairs distances within a leaf, when
adding parallelism, the temporary memory usage increases significantly. In our
experience, it increased beyond the capacity of the L3 cache on our machines,
and significantly limited speedup. To remedy this, instead of building the MST
over all potential edges, we built it only over edges between the $k$-nearest
neighbors of each point for some small $k$. This optimization significantly
improved parallelism with no drop in QPS for a given recall.

#### pyNNDescent

The pyNNDescent (McInnes, 2020) algorithm approximates a graph where the out-
neighbors of point $p$ are the $k$-nearest neighbors of $p$ in the base
dataset. It builds this graph based on the principle that the neighbors of
$p$’s out-neighbors are also good candidates for out-neighbors of $p$. It
first obtains a rough approximation of each point’s out-neighbors using random
clustering trees. Each tree is built down to a leaf of some constant size, and
the exact nearest neighbors within each leaf are used as initial edges in the
graph. It then runs the process of nearest neighbor descent in rounds. Each
round begins by undirecting the graph–that is, adding the opposite edge of
each directed edge. Then, each point $p$ computes its two-hop neighborhood
$\mathcal{Q}$ and retains the $k$ closest candidates among the points
$q\in\mathcal{Q}$. The algorithm terminates once no more than some small
fraction of edges change on each round (i.e., converges). After the descent
converges, a pruning algorithm is used to prune out the long edges of all
triangles. We find that employing the pruning optimization introduced in
DiskANN (Subramanya et al., 2019)—adding the additional slack factor to select
for a denser graph—yielded modest improvements over the original algorithm.

The pyNNDescent algorithm required significant adaptation to scale for large
datasets, and indeed as shown in Section 5 could not be adapted for datasets
larger than a few hundred million points. The fundamental challenge to such an
adaptation is that calculating neighbors of neighbors requires work
proportional to the square of the graph degree. This issue can be addressed in
two ways. The initial step of undirecting the graph can increase the degree of
any vertex up to the number of vertices. Thus, we refine each vertex’s set of
undirected edges to be at most twice the directed degree bound by randomly
sampling edges. Furthermore, we compute sets of two-hop neighborhoods in
batches rather than all at once. Ultimately, even with these modifications,
the amount of temporary memory required to store both the intermediate graphs
and the edge updates made it infeasible to scale to a billion points.

#### Search and Layout Optimizations

In our experiments we use the same beam search algorithm for DiskANN, HCNNG
and pyNNDescent since they all generate a graph in the same format. The only
difference is in how we select a start vertex. Our search algorithm for HNSW
is also very similar, but slightly different since it needs to move between
levels of the hierarchy. We have made a handful of modest optimizations to the
search over the generic form given in Algorithm 1, which we describe here.
Firstly we use an optimized approximate hash table with one-sided negative
errors to quickly identify vertices that have already been visited during the
search. In particular we hash each vertex id to a bucket with a single
element. This means if two vertices map to the same bucket only one will be
stored, and the second will be revisited if encountered. The table size is
selected to be the square of the beam size, which is large enough that
revisiting is rare but typically small enough to fit in the first-level cache.

We also avoid levels of indirection in the graph layout. In particular the
edge-list for each vertex is kept at a fixed length so we can calculate its
offset from the vertex id. We use an $(1+\epsilon)$ pruning during the search
as suggested by Iwasaki and Miyazaki (Iwasaki and Miyazaki, 2018). In
particular we only search vertices which have a distance to the search point
that are within a factor of $(1+\epsilon)$ of the current $k$-th nearest
neighbor. The $\epsilon$ is tuned based on desired accuracy, but is never
greater than .25. In our sweeps of query parameters for different accuracies
we therefore sweep three parameters: the beam size, $k$, and $\epsilon$.

###  3.2. Inverted Indexing Algorithms

Next, we introduce inverted-indexing algorithms (IVF), which constitute a
large class of popular algorithms based on locality-sensitive hashing (LSH)
and clustering. At a high level, IVF algorithms partition the vectors into
buckets called _posting lists_ ; at query time the query only exhaustively
searches elements in only a small number of lists instead of the entire space.
We study two IVF-based algorithms in-depth in this paper, which we describe
next.

#### FAISS-IVF

FAISS is a widely-used and highly optimized library for efficient similarity
searching on CPUs and GPUs (Jégou et al., 2011b; Jégou et al., 2011a; Douze et
al., 2016; Johnson et al., 2021). It provides a variety of options for product
quantization (PQ)—that is, compressing vectors to a lower dimensionality to
make distance computations faster. The primary search structure of FAISS is
the inverted index; points are typically assigned to buckets via single-level
clustering or two-level clustering, but can add other techniques such as using
HNSW or NSG to help select buckets during search. At the billion scale, a
typical FAISS index follows three steps: (1) compute a PQ transform on the
vectors for the purpose of building the index, (2) build an inverted file
index, possibly with an HNSW structure over the buckets, and (3) compute a PQ
compression of the vectors for the purposes of querying the index.

We use the original implementation of FAISS, through the BigANN Benchmarks
testing framework (Simhadri et al., [n.d.]), in our experiments.

#### FALCONN

FALCONN is a C++ library for LSH-based ANNS algorithms (Andoni et al., 2015).
Locality-sensitive hash (LSH) functions are class of hash functions that can
easily cause collisions for close vectors in a space. More specifically, such
hash functions perform randomized space partitions of a unit sphere with the
same dimension as the input, and mark the vectors in the same partition (as a
bucket) with the identical hash value. FALCONN uses multiple hash functions to
create each hash table, thus increasing the number of buckets and decreasing
bucket size. This prevents buckets from having too many elements and thus
prevents the search from having to access too many candidates. To improve
accuracy, it builds multiple (replicated) hash tables for higher probability
of success, trading off accuracy for higher memory consumption. A search
hashes the queried point using each hash function, then collects all the
elements from corresponding buckets among the tables, and retains the nearest
neighbors among these candidates. Furthermore, by enabling multi-probe LSH,
which assigns a vector to more than one bucket in each hash table, FALCONN is
able to go consider more candidates from the additional buckets without
needing to create more hash tables, thus both improving accuracy and saving
memory.

###  3.3. Algorithms Excluded

Out of the algorithms appearing in ANN-benchmarks (Aumüller et al., 2020) and
cited in this work, we excluded algorithms for one of two reasons: either the
algorithm was consistently in the bottom half of the QPS distribution for most
datasets, or we already included an algorithm with a similar approach.
Algorithms excluded on the basis of similarity to DiskANN include NSG (Fu et
al., 2019), NSSG (Fu et al., 2022), FANNG (Harwood and Drummond, 2016), PANNG
(Iwasaki, 2016), ONNG (Iwasaki and Miyazaki, 2018), Vald (kat, 2022), and
kGraph (ann, 2016), as they are all incremental greedy search-based algorithms
producing a flat graph. Algorithms excluded on the basis of similarity to HNSW
(including re-implementations of HNSW appearing in ANN-benchmarks) include
HSSG (Zhang et al., 2022), HVS (Lu et al., 2022), Proximity Graph Maintenance
(Xu et al., 2022), HM-ANN (Ren et al., 2020), n2 (n22, 2021), and Vespa (ves,
2022), as they are incremental algorithms which produce a layered graph.
Algorithms excluded on the basis of similarity to FAISS-IVF include BLISS
(Gupta et al., 2022), Joint Inverted Indexing (Xia et al., 2013), SPANN (Chen
et al., 2021), and SCaNN (Guo et al., 2020) as they are other IVF methods.
Algorithms excluded on the basis of similarity to FALCONN include PLSH
(Sundaram et al., 2013), FALCONN++ (Pham and Liu, 2022), PUFFIN (Aumüller et
al., 2019), and ElastiKNN (Klibisz, 2021) as they are other LSH methods. The
NNDescent (Dong et al., 2011) algorithm was excluded on basis of similarity to
pyNNDescent. The SPTAG (Chen et al., 2018) algorithm was excluded on basis of
similarity to HCNNG. Algorithms excluded due to low performance in the
benchmark suite include FLANN (Muja and Lowe, 2009), RPForest (Maciej Kula,
2019), ANNOY (ann, 2022), OpenSearch KNN (ope, 2022), and ScyPy’s ckdTree
(scy, 2022).

##  4\. Experimental Setup

| BIGANN | MSSPACEV | TEXT2IMAGE | SSNPP
---|---|---|---|---
DiskANN | $R=64,L=128,\alpha=1.2$ | $R=64,L=128,\alpha=1.2$ | $R=64,L=128,\alpha=.9$ | $R=150,L=400,\alpha=1.2$
HNSW | $m=32,\mathit{efc}=128,\alpha=.82$ | $m=32,\mathit{efc}=128,\alpha=.83$ | $m=32,\mathit{efc}=128,\alpha=1.1$ | $m=75,\mathit{efc}=400,\alpha=.82$
HCNNG | $T=30,Ls=1000,s=3$ | $T=50,Ls=1000,s=3$ | $T=30,Ls=1000,s=3$ | $T=50,Ls=1000,s=3$
pyNNDescent |  | $K=40,Ls=100,$
---
$T=10,\alpha=1.2$
| $K=60,Ls=100,$
---
$T=10,\alpha=1.2$
| $K=60,Ls=100,$
---
$T=10,\alpha=.9$
| $K=60,Ls=1000,$
---
$T=10,\alpha=1.4$
FAISS |  | OPQ64_128,
---
IVF1048576_HNSW32,
PQ128x4fsr
| OPQ64_128,
---
IVF1048576_HNSW32,
PQ64x4fsr
| OPQ64_128,
---
IVF1048576_HNSW32,
PQ128x4fsr
| OPQ64_128,
---
IVF1048576_HNSW32,
PQ64
FALCONN | $l=30,rot=1$ | $l=30,rot=1$ | $l=30,rot=1$ | $l=30,rot=1$
Figure 2.  Parameters chosen for each dataset. For DiskANN, HCNNG, and
pyNNDescent, $\alpha$ denotes the pruning parameter. For DiskANN, $R$ denotes
degree bound and $L$ is the beam size. For HNSW, $m$ denotes the degree bound
and $\mathit{efc}$ is the efConstruction. For HCNNG and pyNNDescent, $Ls$
denotes leaf size and $T$ denotes number of cluster trees. For HCNNG, $s$
denotes MST degree. For pyNNDescent, $K$ is the degree bound. For FAISS, the
first string is the type of vector transform used for building the index, the
second denotes the IVF index type, and the third indicates the PQ compression
for the queries. For FALCONN, $l$ is the number of hash tables, and
$\mathit{rot}$ is the number of rotations.

#### Datasets

We chose four billion-size datasets for the majority of our experiments; we
accessed these datasets through the BigANN Benchmarks competition framework,
and some of these datasets were released for the competition (Simhadri et al.,
[n.d.]). The widely used _BIGANN dataset_333Note that throughout the paper we
use BigANN to refer to the benchmarking framework, and BIGANN to refer to the
data set. consists of SIFT image similarity descriptors applied to images
(Simhadri et al., [n.d.]; Jégou et al., 2011b; Jégou et al., 2011a). It is
encoded as 128-dimensional vectors using one byte per vector entry. The
_Microsoft SPACEV dataset ( MSSPACEV)_ encodes web documents and web queries
sourced from Bing using the Microsoft SpaceV Superior Model. The goal is to
match web queries with appropriate web documents; the dataset consists of
single byte signed integers in 100 dimensions (Contributors, 2021). The
_Text2Image dataset ( TEXT2IMAGE)_, released by Yandex Research, consists of a
set of images embedded using the SeResNext-101 model, and a set of textual
queries embedded using a DSSM model. Its vectors are represented using four-
byte floats in 200 dimensions (Baranchuk and Babenko, 2021). Finally,
_SimSearchNet++ ( SSNPP)_ is a range search dataset released by Meta AI
consisting of image descriptions. Its vectors are represented as one-byte
unsigned integers in 512 dimensions (we use the compressed version with 256
dimensions for the BigANN Benchmarks competition) (Sumbaly et al., 2020).

#### Machines and Measurement

For our billion-scale experiments, we used an Azure Msv2-series virtual
machine with four Intel® Xeon® Platinum 8280 Processors with 192 vCPUs
available to the user, and 2 TB main memory (referred to as Msv2). For some
smaller experiments, we used an Azure Ev5-series virtual machine with two 3rd
Generation Intel® Xeon® Platinum 8370C Processors with 96 vCPUs available to
the user, and 672 GiB main memory (referred to as ev5). In our experiments, we
report build times and QPS on all threads unless stated otherwise; throughout
the experiments, we use QPS as opposed to latency as QPS is more relevant to
large multicore machines, and algorithms are typically always within an
acceptable latency range.

#### Algorithm Parameters

In all cases, our interest is in optimizing for the high recall regime (from
.9 to .999) at the highest QPS possible. For all algorithms, we show our
parameter choices in Figure 2. For DiskANN, HCNNG, pyNNDescent, and HNSW, the
parameters shown are applied to all dataset sizes. For FAISS and FALCONN, the
parameters are specific to the size of the dataset.

Figure 3.  QPS on FAISS builds with varying centroids; solid lines indicate
$2^{16}$ centroids and dashed lines indicate $2^{18}$ centroids. All builds
are on a dataset size of 100 million on the ev5machine.

#### DiskANN

The main parameters for the DiskANN index build are (1) the degree bound $R$,
(2) the beam width $L$ used during insertion, and (3) the pruning parameter
$\alpha$. In our experiments, we found that no single parameter setting was
optimal for all recall regimes, and that there were significant tradeoffs in
other recall values when maximizing for recall above .99; thus we chose to use
parameters optimized for the .94-.97 range. Note that for TEXT2IMAGE, which
minimizes negative inner product, the $\alpha$ value must be less than one in
order to select for a denser graph.

#### HNSW

The parameters for the HNSW index build have similar meanings to those of
DiskANN where (1) $m$ is the general degree bound, (2) $\mathit{efc}$ is the
beam width for index build, and (3) $\alpha$ controls the graph density.
Specifically, the bottom layer has degree bound $2m$ while all the other
layers have degree bound $m$. This design is referred to in the source code of
hnswlib (hns, 2019) and performs better in practice than setting all layers to
have the same degree bound. To make the results of DiskANN and HNSW
comparable, we keep $2m=R$ and $\mathit{efc}=L$ through all the datasets and
adjust $\alpha$ to reach similar average degrees at the bottom layer.

#### HCNNG

The relevant parameters for the HCNNG index build are (1) the leaf size $Ls$
of the random clustering tree, (2) the maximum degree $s$ of the MST built in
each leaf, and (3) the number $T$ of random clustering trees. In our
experiments we found that a leaf size of $1000$ sufficed for all dataset
sizes. We use the original authors’ suggested parameter of $3$ for the maximum
degree of the MST. In our experiments we found that $30-50$ trees sufficed for
our datasets, and we found that QPS began to increase after more than $50$
trees.

(a) Build times shown on MSSPACEV as dataset size increases.

(b) QPS for fixed recall (.8) as dataset size increases.

(c) Distance comparisons per query for fixed recall (.8) as the dataset size
increases.

Figure 4.  Figures showing the effect of dataset size on different metrics
using the MSSPACEVdataset.

#### pyNNDescent

The relevant parameters for the pyNNDescent index build are (1) the degree
bound $K$, (2) the pruning parameter $\alpha$, (3) the number $T$ of random
clustering trees used to seed the initial graph, and (4) the leaf size $Ls$ of
the random clustering trees. In our experiments we found that a degree bound
of $40-60$ worked for most datasets.

#### FAISS

The three main aspects of FAISS index construction are (1) the PQ vector
transform for the index build, (2) the IVF index, and (3) the PQ compression
for the queries. To choose index parameters for FAISS, we referred to the
index parameters published in the Big ANN Benchmarks competition (Simhadri et
al., [n.d.]) as well as the optimal parameters for BIGANN published on the
FAISS Wiki (Jegou et al., 2023). Since these parameters optimized for small
space usage (limiting the index size to 128 GB for a billion-scale build), we
experimented with increasing the number of bits in the PQ compression as well
as increasing the number of posting lists in order to optimize for the high-
recall region. In Figure 3, we show the effects of increasing the number of
centroids on the 100M slices of all datasets. In Figure 2 we show the
parameters chosen for billion-scale builds. For hundred-million scale builds,
there is no single dominant option for MSSPACEV and BIGANN, so we include two
FAISS builds in Figure 6.

#### FALCONN

We sweep the index parameters in reasonable ranges using the documentation in
the FALCONN code repository (fal, 2018) and choose the best combination in our
observation. There are many parameters for FALCONN to build hash tables.
Considering that we focus on large datasets, the hash family is fixed to
cross-polytope LSH for better performance on large datasets. The number of
hash tables, $l$, is a core parameter that affects the building time, query
accuracy, and memory usage. In our experiments, we found that $l=30$ maximizes
accuracy within the available memory capacity. The number of hash functions
per table follows the recommended setting from the helper functions in the
authors’ code, computed based on the input size and the dimension. We also
tried manually setting it to other values but they did not perform better.

#### Search Parameters

In all cases, we test a wide variety of search parameters and report those
that maximize QPS for a given recall. For general graph search, we vary $Q$
(beam width), $k$ (the discard threshold), and $c$ (the discard parameter) and
report the best results for a variety of recall thresholds. For FAISS-IVF, we
vary the number of cells probed as well as the HNSW efSearch parameter (for
FAISS settings which use HNSW as a sub-quantizer) and report the best results.
For FALCONN, we vary both the number of probes and the maximum number of
candidates in a wide range.

##  5\. Experimental Results

Figure 5.  QPS on a single thread on BIGANN-1M on ev5. Shown to compare with
ann-benchmarks.

In this section, we present our experimental results, which support the
following broad conclusions. At the end of the section we present more
specific conclusions and directions for future work.

  1. (1)

Graph-based ANNS algorithms stand out significantly when comparing machine-
agnostic measures: we demonstrate that graph-based algorithms compute orders
of magnitude fewer distance comparisons than their IVF- and LSH-based
competitors, with the exception of range search datasets. Most interestingly,
even when our IVF algorithm achieved higher QPS than graph-based algorithms,
it still performed more distance comparisons.

  2. (2)

Only graph-based algorithms are capable of achieving high recall (greater than
.9) at the scale of billions of points for QPS in the 10k-100k range.

  3. (3)

Incremental and MST-based graph algorithms distinguish themselves specifically
at the billion scale.

  4. (4)

All algorithms struggle to perform at high QPS on out-of-distribution data,
but IVF methods stand out as particularly unable to adapt.

  5. (5)

All algorithms struggle to adapt to range searches, but IVF stands out as
better able to adapt, especially at the intermediate recall regime.

###  5.1. Parallelism and Size Scaling

#### Baseline

We first provide some experimental results showing that our re-implementations
of graph-based nearest neighbor algorithms are on par with their original
implementations. Figure 5 shows the QPS and recall of each algorithm on the
BIGANN-1M dataset on a single thread; the interested reader may compare with
the ANN Benchmarks website (Aumüller et al., 2020) and verify that our results
roughly match the ANN benchmarks website. For FAISS, we show both a parameter
choice that is specialized for the million-scale (IVF with no quantization),
and a parameter choice that is more consistent with the ideal parameters for
billion-scale builds.

(a) BIGANN-100M

(b) BIGANN-100M in high recall regime

(c) TEXT2IMAGE-100M

(d) MSSPACEV-100M

(e) MSSPACEV-100M in high recall regime

(f) SSNPP-100M, Range Search.

Figure 6. QPS-recall curves on all 100-million size datasets on the ev5
machine (QPS as a function of recall).

#### Parallelism

To substantiate our claims of improving the parallelism of each graph-based
algorithms as well as illustrate issues with the parallelism of original
implementations, we measure the total work (threads $\times$ time) each
algorithm uses as the number of threads increases. We measure both our
implementation and the original implementation of the graph-based algorithms,
and we measure the original implementation of FAISS and FALCONN. For a
perfectly-parallelized algorithm, we expect to see an almost flat line until
the number of threads increases from 48 to 96; at this point, each core is
hyper-threaded and we expect some increase in total work. The results are
shown in Figure 7.

For DiskANN, whose original implementation was parallelized using with OpenMP
(Chandra et al., 2001), we find a small amount of improvement in parallelism
compared to the original implementation. DiskANN’s original implementation is
parallelized using locks on each vertex of the graph, which works well in the
range of 30-60 threads but eventually leads to performance degradation on high
numbers of threads. HCNNG’s original implementation, parallelized using
OpenMP, builds each random clustering tree using one thread and thus could
only scale up to the number of trees. Our implementation of HCNNG was both
faster on a single thread and used less total work as the number of threads
increases. However, since each thread builds a leaf of the random clustering
tree, its temporary memory requirements increase with the number of threads,
and thus the total work begins to increase slightly from 24 to 48 threads due
to more cache misses. PyNNDescent’s original implementation used Numba (Lam et
al., 2015) for parallelism and did not scale beyond 20 threads. HNSW does not
introduce parallelism by default but its original implementation is thread-
safe with locks on the critical structures. We enable parallel insertion and
querying using ParlayLib. The insertion performance is good due to its
efficient memory layout and deep optimizations in many aspects; however, the
total work has an increasing trend with the number of threads goes high,
indicating a potential scalability issue on machines with more CPU cores.

FAISS, whose implementation we use via the BigANN Benchmarks repository
(Simhadri et al., [n.d.]), uses OpenMP and also does not scale well past 20
threads, even increasing in clock time when going from 48 to 96 threads. We
expect that FAISS could be parallelized more effectively with further work,
and we note that FAISS appears to have better parallelism on datasets in the
100 million to 1 billion range. For MSSPACEV-100M, we found a decrease in
clock time as the number of threads incrased from 24 to 48 to 96. As for
FALCONN, its parallelism is driven by the implementation of std::async in C++
STL. Since it builds each hash table using one thread, the scalability is up
to the number of hash tables, which is usually low for the memory consumption
if working with large datasets.

Figure 7.  Build times on BIGANN-1M. Shown varying threads from 1 to 96 and
multiplying threads by time to show work.

#### Dataset Size Scaling

One of our objectives in this benchmark is to understand the relationship
between dataset size and various metrics for ANNS algorithms. To explore this,
we use MSSPACEV dataset as an example and measure build times, QPS, and
average distance computations per query for each algorithm in Figure 4.

For HNSW, HCNNG, pyNNDescent, and DiskANN, we found the build times incurred
slightly superlinear speedup as the dataset size increased (Figure 4(a));
build times increased by a multiplicative factor of 11-12 when the size of the
dataset increased tenfold. For HNSW and DiskANN, this superlinear increase can
be attributed to the mechanics of the beam search: on a larger graph, beam
search will take longer to terminate as there are more suitable candidates in
its frontier. For pyNNDescent, we found that the nearest neighbor descent
process consistently took more rounds to terminate for larger dataset sizes;
since the nearest neighbor graph for a larger dataset will likely have a
larger diameter, two-hop exploration takes longer to “propagate” through the
entire graph. For FAISS we found an unusually small increase in build time
between the 10M and 100M datasets, but this can be attributed to the
aforementioned parallelism issues, which seem to decrease as the dataset size
increases. FALCONN has consistently low build times as partitioning space and
building hash tables are much less costly than building a graph or assigning
points to centroids.

DiskANN and HNSW show a steady decrease in QPS as the dataset size increases.
Part of the reason for this decrease is that a beam search with the same
parameters on a larger graph will not only be slower than the same search on a
smaller graph, it will also be less accurate since it visits a much smaller
fraction of all the vertices. Since Figures 4(b) and 4(c) keep the recall
fixed at .8, they must use an increased beam width at larger dataset sizes,
thus contributing to lower QPS.

HCNNG and pyNNDescent both show steeper drops in QPS for fixed recall than
DiskANN and HNSW. This may be because they only express close neighbor
relationships with their edges, as the dataset size increases, the
relationships they express cover smaller and smaller proportions of the whole
dataset. Thus, they require sharply increased parameters to remain at constant
recall at scale.

FALCONN has relatively low QPS at all dataset sizes, perhaps because a pure
LSH algorithm has a difficult time collecting many true nearest neighbors. To
reach a fixed recall, it has to push the number of candidates sufficiently
large and thus searches a large number of buckets, causing low QPS.

Somewhat surprisingly, QPS and distance computations for FAISS remained almost
the same for the 100M and 1B datasets. We confirmed that this phenomenon
persisted through a wide range of quantization and centroid choices.

(a) BIGANN-1B

(b) MSSPACEV-1B

(c) TEXT2IMAGE-1B

(d) SSNPP-1B, Range Search

QPS as a function of recall.

(e) BIGANN-1B

(f) SPACEV-1B

(g) TTI-1B

(h) SSNPP-1B, Range Search

Distance comparisons per query as a function of recall.

Figure 8.  Graphs showing QPS in the high and low recall regimes as well as
distance comparisons per query on all billion-size datasets on the Msv2
machine.

###  5.2. Full Billion-Scale Results

In this section we give a full set of results for all algorithms and datasets
for both 100 million and billion size datasets 444The QPS results for HCNNG on
BIGANN-1B and MSSPACEV-1B for some lower recall data points are excluded in
this version due to a technical problem and will be corrected in a later
version.. In Figure 6, we show the QPS-recall curves for each 100-million
scale dataset; Figure 2 shows the build times. In Figure 8 we show both QPS
and distance computations for each billion-scale dataset, while Figure 2 shows
the build times. As mentioned in Section 3, pyNNDescent is not present in
Figures 8 and 2 since its memory requirements were infeasible for billion-
scale datasets. We discuss results on each dataset and present our
conclusions. In all cases, we found that FALCONN performs at poor recall and
with many more distance computations than the other algorithms. Interestingly,
FALCONN and FAISS achieve almost the same maximum recall on each nearest
neighbor dataset, suggesting an inherent limit to bucketing-based methods.

#### BIGANN

For BIGANN, we observe fast build times for all algorithms. DiskANN performs
extremely well on BIGANN, completely dominating the QPS-recall curves for both
100 million and 1 billion points. At the 100 million scale, HNSW, pyNNDescent,
and HCNNG show similar curves to DiskANN, but shifted slightly downwards, with
HNSW at the bottom of the distribution. This may suggest that HNSW’s method of
hierarchical search is overzealous and wastes too much time in the top layers
of the search for this scenario. Similarly, HCNNG and pyNNDescent perform
especially poorly in the low recall range. This may be because HCNNG and
pyNNDescent are both locally greedy—that is, their edge selection process
looks for close neighbors. On the other hand, DiskANN and retains some close
neighbors, but also selects for longer edges to enable fast navigation. This
phenomena may put HCNNG and pyNNDescent at a disadvantage for lower recall.
DiskANN can achieve recall in the range of .2-.9 while visiting very few
nodes, while on the other hand, HCNNG and pyNNDescent may spend more of their
“budget” on convergence when the number of hops in the graph is limited for
lower recall.

FAISS shows good performance in the lower recall range, although it performs
more distance computations than DiskANN, HCNNG, and HNSW. This is likely due
to FAISS’s compressed distance comparisons being less expensive.

#### MSSPACEV

Results on MSSPACEV are shown in Figures 6(d), 8(b), 6(e), and 8(f). Since the
index vectors are drawn from web pages and the search vectors are drawn from
web queries, MSSPACEV is somewhat out-of-distribution, as measured by Jaiswal
et al. (Jaiswal et al., 2022), but the difference between distributions is not
nearly as significant as in TEXT2IMAGE. The relative ordering and comparison
of each algorithm is the same as for BIGANN.

####  TEXT2IMAGE (Out-of-Distribution)

The TEXT2IMAGE dataset is an example of out-of-distribution queries, meaning
that the queries are drawn from a different source and embedded using a
different model than the data in the index. Furthermore, its dimension (200)
is higher than those BIGANN and MSSPACEV, and its vectors are represented
using four-byte floats as opposed to single-byte signed or unsigned integers.
At the scale of 100 million points, we find that all graph-based algorithms
are roughly equivalent; at 1 billion points we find that HNSW dominates in the
lower recall range while HCNNG dominates at higher recall. FAISS and FALCONN
stand out as particularly unable to adapt to this dataset. This is likely
because for both algorithms, the cells are adapted for serving the query
distribution and ill-suited to out-of-distribution queries. As evidenced by
the build times in Figure 2, DiskANN’s beam search takes significantly longer
on TEXT2IMAGE than on MSSPACEV or BIGANN; this can be extrapolated from the
fact that its slowdown is much larger than the comparable slowdown for HCNNG,
which can be explained by distance computations taking almost twice as long
due to floats and higher dimensionality. This slow convergence is also
reflected in the search times and numbers of distance comparisons, as shown in
Figures 6(c), 8(c), and 8(g). Interestingly, HNSW’s index build does not seem
to be subject to the same issues, perhaps due to the less influence from
search performance or the differences in pruning.

####  SSNPP (Range Search)

The SSNPP dataset, a range search dataset, highlights the situations where IVF
methods such as FAISS dominate. For SSNPP, we show results for the 10 million,
100 million, and 1 billion size datasets in Figures 9, 6(f), and 8(d). Each
increase in dataset size widens the gap between FAISS and the graph-based
methods. As the dataset size increases, so does the maximum number of in-range
neighbors for any point in the query set. As it increases from a few hundred,
to a few thousand, to ten thousand, FAISS’s approach of visiting all data
points in a given cell proves superior to beam search, which can only clumsily
adapt by increasing its beam width. Similar to TEXT2IMAGE, HCNNG performs
about the same as DiskANN at the billion scale despite the high choice of
parameters for DiskANN (shown in Figure 2). One possible reason for this
phenomena is that HCNNG’s locally greedy approach makes it comparatively
easier to find close neighbors once the beam search finds a single closer
neighbor. In Figure 6(c), pyNNDescent performs particularly poorly on
TEXT2IMAGE; during our experiments, we found that pyNNDescent was very slow to
converge and even after about 20 rounds was still changing up to 30% of its
vertices. This could be caused by each point in the dataset having a large
number of near neighbors, as would be typical for a range search dataset.

Figure 9.  QPS as a function of recall on range search dataset SSNPP-10M.

##  6\. Conclusion and Future Work

In this paper, we provide a framework on ANNS with new parallel
implementations for ANNS algorithms that scales to billion-scale datasets on a
single machine. We evaluate the build time and query time and well as machine-
independent measures such numbers of distance comparisons, on up to billion-
scale datasets. We also studied out-of-distribution datasets and range
queries, which were not covered in most of the previous ANNS algorithms and
benchmarks. Many interesting findings are summarized in Section 5. In addition
to our broad conclusions, we present some further, more specific conclusions,
along with discussion of future research directions inspired by this paper.

  1. (1)

DiskANN’s beam search does not terminate quickly enough on more difficult
datasets such as TEXT2IMAGE and SSNPP and is thus a less preferable choice for
these datasets. We note that on the out-of-distribution TEXT2IMAGE dataset,
recent improvements to the DiskANN algorithm allow DiskANN to adapt much
better to out-of-distribution data (Jaiswal et al., 2022).

  2. (2)

HCNNG, a comparatively less widely used algorithm for ANNS, is extremely
competitive on billion-scale datasets. Although it struggles in the low recall
regime, its performance is on par with other algorithms in the case of high
recall, and it is especially effective at both building and querying on out-
of-distribution indices.

  3. (3)

For all nearest neighbor datasets (i.e. excluding range search), FAISS and
FALCONN are slower and bottom out at lower recall compared to graph-based
algorithms. Notably even when FAISS performs faster than some graph-based
algorithms, it performs more distance computations (see Figures 8(b) and
8(f)).

Our experiments illuminate many opportunities for future work. Here we
highlight a few of the most interesting. One of our most surprising
conclusions is that no algorithm is dominant for all datasets, or even all
nearest neighbor search datasets. This brings us to our first open question:

Open Question 1: Can the techniques from incremental graph algorithms be
combined with insights from HCNNG to produce an algorithm which dominates
both?

Another of our most interesting conclusions is the clear superiority of IVF
methods for range search, or, worded differently, the shocking inability of
graph-based algorithms to adapt for range search. Due to ANNS graphs’ ability
to save distance comparisons by navigating quickly through the graph, our next
two open questions ask how these insights can be used for range search:

Open Question 2: How can ANNS graph structures be adapted to quickly answer
range search queries?

Another surprising result was the clear inability of IVF and LSH algorithms to
answer out-of-distribution queries. This brings us to our final open problem:

Open Question 3: How can IVF and LSH algorithms be adapted to perform better
on out-of-distribution queries?

| BIGANN | MSSPACEV | TEXT2IMAGE | SSNPP
---|---|---|---|---
DiskANN | 11.0 | 15.1 | 61.6 | 83.1
HNSW | 9.2 | 6.7 | 14.9 | 91.6
HCNNG | 8.6 | 15.8 | 21.4 | 19.0
FAISS | 5.2 | 4.1 | 4.5 | 4.5
FALCONN | 1.75 | 1.12 | 1.45 | 1.42

Table 1.  Build times (hours) on billion-scale datasets.

| BIGANN | MSSPACEV | TEXT2IMAGE | SSNPP
---|---|---|---|---
DiskANN | .89 | 1.12 | 5.36 | 9.27
HNSW | .92 | .77 | 1.79 | 11.85
HCNNG | .74 | 1.22 | 2.43 | 1.52
pyNNDescent | .52 | .83 | 2.43 | 1.52
FAISS | .28 | .17 | .29 | .21
FALCONN | .06 | .06 | .08 | .08

Table 2.  Build times (hours) on hundred million scale datasets.

## References

  * (1)
  * bin ([n.d.]) [n.d.].  https://www.bing.com/new
  * ann (2016) 2016\.  KGraph: A Library for Approximate Nearest Neighbor Search.  Webpage.  Retrieved December 20, 2022 from https://github.com/aaalgo/kgraph
  * fal (2018) 2018\.  FALCONN - FAst Lookups of Cosine and Other Nearest Neighbors.  Webpage.  Retrieved September 14, 2017 from https://github.com/FALCONN-LIB/FALCONN
  * hns (2019) 2019\.  Hnswlib - fast approximate nearest neighbor search.  Webpage.  Retrieved December 16, 2019 from https://github.com/nmslib/hnswlib
  * n22 (2021) 2021\.  N2.  Webpage.  Retrieved December 27, 2022 from https://github.com/kakao/n2
  * ann (2022) 2022\.  Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk.  Webpage.  Retrieved January 1, 2023 from https://github.com/spotify/annoy
  * ope (2022) 2022\.  OpenSearch k-NN.  Webpage.  Retrieved December 27, 2022 from https://github.com/opensearch-project/k-NN
  * scy (2022) 2022\.  Spacial algorithms and data structures.  Webpage.  Retrieved December 27, 2022 from https://docs.scipy.org/doc/scipy/reference/spatial.htmla
  * kat (2022) 2022\.  Vald: A Highly Scalable Distributed Vector Search Engine.  Webpage.  Retrieved December 27, 2022 from https://github.com/vdaas/vald
  * ves (2022) 2022\.  vespa.  Webpage.  Retrieved December 27, 2022 from https://github.com/vespa-engine/vespa
  * cha (2023) 2023\.  CHATGPT-Retrieval-plugin/readme.md at main · openai/CHATGPT-retrieval-plugin.  https://github.com/openai/chatgpt-retrieval-plugin/blob/main/README.md
  * Andoni et al. (2015) Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015\.  Practical and Optimal LSH for Angular Distance. In _Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_. 1225–1233.
  * Arya and Mount (1993) Sunil Arya and David M. Mount. 1993.  Approximate Nearest Neighbor Queries in Fixed Dimensions. In _ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA)_. ACM/SIAM, 271–280.
  * Aumüller et al. (2020) Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2020.  ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms.  _Inf. Syst._ 87 (2020).
  * Aumüller et al. (2019) Martin Aumüller, Tobias Christiani, Rasmus Pagh, and Michael Vesterli. 2019.  PUFFINN: Parameterless and Universally Fast Finding of Nearest Neighbors. In _27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany_ _(LIPIcs, Vol. 144)_. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 10:1–10:16.
  * Baranchuk and Babenko (2021) Dmitry Baranchuk and Artem Babenko. 2021.  Benchmarks for Billion-Scale Similarity Search.  Webpage.  Retrieved March 16, 2023 from https://research.yandex.com/blog/benchmarks-for-billion-scale-similarity-search
  * Baranchuk et al. (2018) Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018\.  Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In _Computer Vision \- ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XII_ _(Lecture Notes in Computer Science, Vol. 11216)_. Springer, 209–224.
  * Beygelzimer et al. (2006) Alina Beygelzimer, Sham M. Kakade, and John Langford. 2006\.  Cover trees for nearest neighbor. In _Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006_ _(ACM International Conference Proceeding Series, Vol. 148)_. ACM, 97–104.
  * Blelloch et al. (2020) Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020\.  ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_. ACM, 507–509.  https://doi.org/10.1145/3350755.3400254
  * Blelloch and Dobson (2022) Guy E. Blelloch and Magdalen Dobson. 2022.  Parallel Nearest Neighbors in Low Dimensions with Batch Updates. In _Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, January 9-10, 2022_. SIAM, 195–208.  https://doi.org/10.1137/1.9781611977042.16
  * Blelloch et al. (2016) Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. 2016\.  Parallelism in Randomized Incremental Algorithms. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_. ACM, 467–478.  https://doi.org/10.1145/2935764.2935766
  * Boytsov and Naidan (2013) Leonid Boytsov and Bilegsaikhan Naidan. 2013.  Engineering Efficient and Effective Non-metric Space Library. In _Similarity Search and Applications - 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings_ _(Lecture Notes in Computer Science, Vol. 8199)_. Springer, 280–293.
  * Chandra et al. (2001) Rohit Chandra, Leo Dagum, David Kohr, Ramesh Menon, Dror Maydan, and Jeff McDonald. 2001\.  _Parallel programming in OpenMP_.  Morgan Kaufmann.
  * Chase (2023) Harrison Chase. 2023\.  Vector DB text generation.  https://python.langchain.com/en/latest/modules/chains/index_examples/vector_db_text_generation.html
  * Chen et al. (2018) Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018\.  _SPTAG: A library for fast approximate nearest neighbor search_.  https://github.com/Microsoft/SPTAG
  * Chen et al. (2021) Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021\.  SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In _Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 5199–5212.
  * Connor and Kumar (2008) M. Connor and P. Kumar. 2008.  Parallel Construction of k-Nearest Neighbor Graphs for Point Clouds. In _Eurographics / IEEE VGTC Symposium on Volume and Point-Based Graphics - 7th International Symposium on Volume Graphics, VG/PBG@SIGGRAPH 2008, Los Angeles, CA, USA, August 10-11, 2008_ , Hans-Christian Hege, David H. Laidlaw, Renato Pajarola, and Oliver G. Staadt (Eds.). Eurographics Association, 25–31.  https://doi.org/10.2312/VG/VG-PBG08/025-031
  * Contributors (2021) SpaceV Contributors. 2021\.  SPACEV1B: A billion-Scale vector dataset for text descriptors.  Webpage.  Retrieved March 16, 2023 from https://github.com/microsoft/SPTAG/tree/main/datasets/SPACEV1B
  * Dhulipala et al. (2021) Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2021\.  Theoretically efficient parallel graph algorithms can be fast and scalable.  _ACM Transactions on Parallel Computing (TOPC)_ 8, 1 (2021), 1–70.
  * Dong et al. (2011) Wei Dong, Moses Charikar, and Kai Li. 2011.  Efficient k-nearest neighbor graph construction for generic similarity measures. In _Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 - April 1, 2011_ , Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar, M. P. Ravindra, Elisa Bertino, and Ravi Kumar (Eds.). ACM, 577–586.
  * Dong et al. (2023) Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2023\.  High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_.
  * Douze et al. (2016) Matthijs Douze, Hervé Jégou, and Florent Perronnin. 2016.  Polysemous Codes. In _Computer Vision - ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 9906)_. Springer, 785–801.
  * Fu et al. (2022) Cong Fu, Changxu Wang, and Deng Cai. 2022.  High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility.  _IEEE Trans. Pattern Anal. Mach. Intell._ 44, 8 (2022), 4139–4150.
  * Fu et al. (2019) Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019\.  Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph.  _Proc. VLDB Endow._ 12, 5 (2019), 461–474.
  * Gu et al. (2023) Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan. 2023.  Parallel Longest Increasing Subsequence and van Emde Boas Trees. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_.
  * Gu et al. (2022) Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang. 2022\.  Parallel Cover Trees and their Applications. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_. 259–272.
  * Gu et al. (2015) Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015\.  A Top-Down Parallel Semisort. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_. ACM, 24–34.  https://doi.org/10.1145/2755573.2755597
  * Guo et al. (2020) Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020.  Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , Vol. 119. PMLR, 3887–3896.  http://proceedings.mlr.press/v119/guo20h.html
  * Gupta et al. (2022) Gaurav Gupta, Tharun Medini, Anshumali Shrivastava, and Alexander J. Smola. 2022.  BLISS: A Billion scale Index using Iterative Re-partitioning. In _KDD ’22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 - 18, 2022_. ACM, 486–495.
  * Harwood and Drummond (2016) Ben Harwood and Tom Drummond. 2016.  Fanng: Fast approximate nearest neighbour graphs. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 5713–5722.
  * Iwasaki (2016) Masajiro Iwasaki. 2016\.  Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search. In _Similarity Search and Applications - 9th International Conference, SISAP 2016, Tokyo, Japan, October 24-26, 2016. Proceedings_ _(Lecture Notes in Computer Science, Vol. 9939)_. 20–33.
  * Iwasaki and Miyazaki (2018) Masajiro Iwasaki and Daisuke Miyazaki. 2018.  Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data.  _CoRR_ abs/1810.07355 (2018).  arXiv:1810.07355 http://arxiv.org/abs/1810.07355
  * Jaiswal et al. (2022) Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, and Sheshansh Agrawal. 2022.  OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries.  _CoRR_ abs/2211.12850 (2022).  https://doi.org/10.48550/arXiv.2211.12850
  * Jegou et al. (2023) Herve Jegou, Matthijs Douze, Jeff Johnson, Lucas Hosseini, Chengqi Deng, and Alexandr Guzhva. 2023\.  FAISS Wiki.  Webpage.  Retrieved March 21, 2023 from https://github.com/facebookresearch/faiss/wiki
  * Jégou et al. (2011a) Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011a.  Product Quantization for Nearest Neighbor Search.  _IEEE Trans. Pattern Anal. Mach. Intell._ 33, 1 (2011), 117–128.
  * Jégou et al. (2011b) Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011b.  Searching in one billion vectors: Re-rank with source coding. In _Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011, May 22-27, 2011, Prague Congress Center, Prague, Czech Republic_. IEEE, 861–864.  https://doi.org/10.1109/ICASSP.2011.5946540
  * Johnson et al. (2021) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021\.  Billion-Scale Similarity Search with GPUs.  _IEEE Trans. Big Data_ 7, 3 (2021), 535–547.
  * Klibisz (2021) Alex Klibisz. 2021\.  Tour de Elastiknn.  Webpage.  Retrieved December 27, 2022 from https://elastiknn.com/posts/tour-de-elastiknn-august-2021/
  * Lam et al. (2015) Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. 2015\.  Numba: A llvm-based python jit compiler. In _Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC_. 1–6.
  * Lu et al. (2022) Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2022\.  HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search.  _Proc. VLDB Endow._ 15, 2 (2022), 246–258.
  * Maciej Kula (2019) Anonymous Maciej Kula, Matthew Ward. 2019\.  rpforest.  Webpage.  Retrieved December 20, 2022 from https://github.com/lyst/rpforest
  * Malkov and Yashunin (2020) Yury A. Malkov and Dmitry A. Yashunin. 2020.  Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs.  _IEEE Trans. Pattern Anal. Mach. Intell._ 42, 4 (2020), 824–836.
  * McInnes (2020) Leland McInnes. 2020\.  PyNNDescent for Fast Approximate Nearest Neighbors.  Webpage.  Retrieved December 15, 2022 from https://pynndescent.readthedocs.io/en/latest/
  * MetaAI (2020) MetaAI. 2020.  Using AI to detect COVID-19 misinformation and exploitative content.  Webpage.  Retrieved January 26, 2022 from https://ai.facebook.com/blog/using-ai-to-detect-covid-19-misinformation-and-exploitative-content/
  * Muja and Lowe (2009) Marius Muja and David G. Lowe. 2009.  Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In _VISAPP 2009 - Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, Lisboa, Portugal, February 5-8, 2009 - Volume 1_. INSTICC Press, 331–340.
  * Muñoz et al. (2019) Javier Alvaro Vargas Muñoz, Marcos André Gonçalves, Zanoni Dias, and Ricardo da Silva Torres. 2019\.  Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search.  _Pattern Recognit._ 96 (2019).
  * Pham and Liu (2022) Ninh Pham and Tao Liu. 2022\.  Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search.  _CoRR_ abs/2206.01382 (2022).  https://doi.org/10.48550/arXiv.2206.01382 arXiv:2206.01382
  * Ponomarenko et al. (2011) Alexander Ponomarenko, Yury Malkov, Andrey Logvinov, and Vladimir Krylov. 2011.  Approximate nearest neighbor search small world approach. In _International Conference on Information and Communication Technologies & Applications_, Vol. 17.
  * Ren et al. (2020) Jie Ren, Minjia Zhang, and Dong Li. 2020.  HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous Memory. In _Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).
  * Shen et al. (2022) Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun. 2022\.  Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient. In _ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)_.
  * Simhadri et al. ([n.d.]) Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. [n.d.].  Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neighbor Search. In _NeurIPS 2021 Competitions and Demonstrations Track, 6-14 December 2021, Online_ _(Proceedings of Machine Learning Research, Vol. 176)_. PMLR, 177–189.
  * Singh et al. (2021) Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021.  FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search.  _CoRR_ abs/2105.09613 (2021).  arXiv:2105.09613 https://arxiv.org/abs/2105.09613
  * Stallbaumer (2023) Colette Stallbaumer. 2023\.  Introducing Microsoft 365 copilot.  https://www.microsoft.com/en-us/microsoft-365/blog/2023/03/16/introducing-microsoft-365-copilot-a-whole-new-way-to-work/
  * Subramanya et al. (2019) Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019.  DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In _Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_. 13748–13758.
  * Sumbaly et al. (2020) Roshan Sumbaly, Mahalia Miller, Hardik Shah, Yang Xie, Sean Chang Culatana, Tim Khatkevich, Enming Luo, Emanuel Strauss, Gergely Szilvasy, Manika Puri, Pratyusa Manadhata, Benjamin Graham, Matthijs Douze, Zeki Yalniz, and Hervé Jegou. 2020.  Using AI to detect COVID-19 misinformation and exploitative content.  Webpage.  Retrieved March 16, 2023 from https://ai.facebook.com/blog/using-ai-to-detect-covid-19-misinformation-and-exploitative-content/
  * Sundaram et al. (2013) Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish, Todd Mostak, Piotr Indyk, Samuel Madden, and Pradeep Dubey. 2013.  Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing.  _Proc. VLDB Endow._ 6, 14 (2013), 1930–1941.
  * tawalke (2023) tawalke. 2023.  PR: SK Vectordb Connector Work - Merging forked branch; PR from Fork to SK Branch by Tawalke · pull request 83 · Microsoft/Semantic-Kernel.  https://github.com/microsoft/semantic-kernel/pull/83
  * Wang et al. (2021) Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021\.  A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search.  _Proc. VLDB Endow._ 14, 11 (2021), 1964–1978.
  * Wieschollek et al. (2016) P. Wieschollek, O. Wang, A. Sorkine-Hornung, and H. P. A. Lensch. 2016.  Efficient large-scale approximate nearest neighbor search on the GPU. In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Xia et al. (2013) Yan Xia, Kaiming He, Fang Wen, and Jian Sun. 2013\.  Joint inverted indexing. In _Proceedings of the IEEE International Conference on Computer Vision_. 3416–3423.
  * Xu et al. (2022) Zhaozhuo Xu, Weijie Zhao, Shulong Tan, Zhixin Zhou, and Ping Li. 2022.  Proximity Graph Maintenance for Fast Online Nearest Neighbor Search.  _CoRR_ abs/2206.10839 (2022).  https://doi.org/10.48550/arXiv.2206.10839 arXiv:2206.10839
  * Yesantharao et al. (2021) Rahul Yesantharao, Yiqiu Wang, Laxman Dhulipala, and Julian Shun. 2021.  Parallel Batch-Dynamic kd-Trees.  _CoRR_ abs/2112.06188 (2021).  arXiv:2112.06188 https://arxiv.org/abs/2112.06188
  * Zhang et al. (2022) Jiaru Zhang, Ruhui Ma, Tao Song, Yang Hua, Zhengui Xue, Chenyang Guan, and Haibing Guan. 2022.  Hierarchical Satellite System Graph for Approximate Nearest Neighbor Search on Big Data.  _ACM/IMS Trans. Data Sci._ 2, 4 (2022).


###  E.2 Proof for Section A

###### Proof of Theorem 5, Linear $\phi$, Regression, Lower Bound.

Assume $\Sigma_{1,1}=Var(x_{1})=I_{d_{1}}$ and
$\Sigma_{2,2}=Var(x_{2})=I_{d_{2}}$. When using linear $\phi$, it is easy to
see that $\phi^{*}(x_{1})=\Sigma_{2,1}x_{1}$ for
$\Sigma_{2,1}=Cov(x_{2},x_{1})$. Thus when SSL is unbiased, we have
$\theta_{0}x_{1}\equiv a^{\top}\Sigma_{2,1}x_{1}$, i.e.
$\theta_{0}=a^{\top}\Sigma_{2,1}$ for some vector $a$. From Lemma 3, we have
known fixed $a$,

$\displaystyle\inf_{\widehat{\theta}}\sup_{\Sigma_{1,2}}\mathbb{E}\|\widehat{\theta}-\Sigma_{1,2}a\|^{2}=\Omega\left(\frac{d_{1}+d_{2}}{n_{1}+n_{3}}\|a\|^{2}\right),$

and for known $\Sigma_{1,2}$, from Lemma 2 we have

$\displaystyle\inf_{\widehat{\theta}}\sup_{a}\mathbb{E}\|\widehat{a}-a\|^{2}=\Omega\left(\frac{\sigma^{2}d_{2}}{n_{1}+n_{2}}\right).$

Using the strong convexity property of the risk, we then obtain

$\displaystyle\inf_{\widehat{\theta}}\sup_{\Sigma_{1,2}}\mathbb{E}R(\widehat{\theta})-R^{*}=\Omega\left(\frac{d_{1}+d_{2}}{n_{1}+n_{3}}\|a\|^{2}+\frac{\sigma^{2}d_{2}}{n_{1}+n_{2}}\right),$

where $\|a\|=\Theta(\|\theta_{0}\|)$ based on assumption. ∎

###### Proof of Theorem 5, Linear $\phi$, Regression, Upper Bound.

The proof is similar to the square loss case in Theorem 3. Denote
$(X_{1},X_{2})$ as the data matrix for $S_{1},S_{3}$ (without response), and
$(X_{1}^{\prime},X_{2}^{\prime},Y^{\prime})$ as the data matrix for
$S_{1},S_{2}$. Denote $\Sigma_{i,j}=\mathbb{E}x_{i}x_{j}^{\top}$ for
$i,j\in\\{1,2\\}$. Also denote $\Sigma_{i,y}$ as $\mathbb{E}x_{i}y$ for
$i\in\\{1,2\\}$.

We first look at the asymptotics of $\widehat{\phi}\widehat{W}$. From the
problem setup, we can directly solve $\widehat{\phi}$:

$\displaystyle\widehat{\phi}=(X_{1}^{\top}X_{1})^{-1}X_{1}^{\top}X_{2}\rightarrow\Sigma_{1,1}^{-1}\Sigma_{1,2},$

and further write down $\widehat{W}$:

$\displaystyle\widehat{W}=(\widehat{\phi}(X_{1}^{\prime})^{\top}\widehat{\phi}(X_{1}^{\prime}))^{-1}\widehat{\phi}(X_{1}^{\prime})^{\top}Y^{\prime}\rightarrow(\Sigma_{2,1}\Sigma_{1,1}^{-1}\Sigma_{1,2})^{-1}\Sigma_{2,1}\theta_{0}.$

Thus

$\displaystyle\widehat{\theta}=\widehat{\phi}\widehat{W}\rightarrow\Sigma_{1,1}^{-1}\Sigma_{1,2}(\Sigma_{2,1}\Sigma_{1,1}^{-1}\Sigma_{1,2})^{-1}\Sigma_{2,1}\theta_{0}.$

When $\theta_{0}=\Sigma_{1,1}^{-1}\Sigma_{2,1}a_{0}$ for some $a_{0}$, we have

$\displaystyle\Sigma_{1,1}^{-1}\Sigma_{1,2}(\Sigma_{2,1}\Sigma_{1,1}^{-1}\Sigma_{1,2})^{-1}\Sigma_{2,1}\theta_{0}=\theta_{0},$

i.e., SSL is unbiased.

We next study the convergence rate. Denote $\theta_{0}$ as the
$\widehat{\theta}$ obtained when $n_{i}\rightarrow\infty$ for all $i=1,2,3$.
For classification task, there is no preference on the magnitude of
$\theta_{0}$ as it works as a linear classifier, so we take
$\|\theta_{0}\|=1$. For the pretext task, one can see that

$\displaystyle\widehat{\phi}-{\phi}^{*}$ $\displaystyle=$
$\displaystyle(\widehat{\phi}(X_{1}^{\prime})^{\top}\widehat{\phi}(X_{1}^{\prime}))^{-1}\widehat{\phi}(X_{1}^{\prime})^{\top}Y^{\prime}-{\phi}^{*}$
$\displaystyle=$
$\displaystyle\Sigma_{1,1}^{-1}\left(\frac{X_{1}^{\top}X_{2}}{n_{1}+n_{3}}-\Sigma_{1,2}\right)+\Sigma_{1,1}^{-1}\left(\frac{X_{1}^{\top}X_{1}}{n_{1}+n_{3}}-\Sigma_{1,1}\right)\Sigma_{1,1}^{-1}\Sigma_{1,2}+o.$
$\displaystyle\widehat{W}-W^{*}$ $\displaystyle=$
$\displaystyle(\widehat{\phi}(X_{1}^{\prime})^{\top}\widehat{\phi}(X_{1}^{\prime}))^{-1}\widehat{\phi}(X_{1}^{\prime})^{\top}Y^{\prime}-W^{*}$
$\displaystyle=$
$\displaystyle\left(\frac{\phi^{*}(X_{1}^{\prime})^{\top}\phi^{*}(X_{1}^{\prime})}{n_{1}+n_{2}}+(\widehat{\phi}-\phi^{*})^{\top}\Sigma_{1,2}+\Sigma_{2,1}(\widehat{\phi}-\phi^{*})+o\right)^{-1}$
$\displaystyle\cdot\left(\frac{\phi^{*}(X_{1}^{\prime})^{\top}Y^{\prime}}{n_{1}+n_{2}}+(\widehat{\phi}-\phi^{*})^{\top}\Sigma_{1,1}\theta_{0}+o\right)-W^{*},$

where

$\displaystyle\left(\frac{\phi^{*}(X_{1}^{\prime})^{\top}\phi^{*}(X_{1}^{\prime})}{n_{1}+n_{2}}+(\widehat{\phi}-\phi^{*})^{\top}\Sigma_{1,2}+\Sigma_{2,1}(\widehat{\phi}-\phi^{*})+o\right)^{-1}-\left(\frac{\phi^{*}(X_{1}^{\prime})^{\top}\phi^{*}(X_{1}^{\prime})}{n_{1}+n_{2}}\right)^{-1}$
$\displaystyle=$
$\displaystyle\left(\frac{\phi^{*}(X_{1}^{\prime})^{\top}\phi^{*}(X_{1}^{\prime})}{n_{1}+n_{2}}\right)^{-1}\left((\widehat{\phi}-\phi^{*})^{\top}\Sigma_{1,2}+\Sigma_{2,1}(\widehat{\phi}-\phi^{*})\right)\left(\frac{\phi^{*}(X_{1}^{\prime})^{\top}\phi^{*}(X_{1}^{\prime})}{n_{1}+n_{2}}\right)^{-1}+o.$

As a result, denoting $\widehat{\theta}=\widehat{\phi}^{\top}\widehat{W}$, we
have

$\displaystyle\widehat{\theta}-\theta_{0}$ $\displaystyle=$
$\displaystyle(\widehat{\phi}-\phi^{*})^{\top}W^{*}+(\phi^{*})^{\top}(\widehat{W}-W^{*})+o,$

therefore,

$\displaystyle\mathbb{E}\|\widehat{\theta}-\theta_{0}\|^{2}=O\left(\frac{d_{2}\sigma_{2}^{2}}{n_{1}+n_{2}}+\frac{d_{1}+d_{2}}{n_{1}+n_{3}}\|\theta_{0}\|^{2}\right).$

∎

###### Proof of Theorem 5, Linear $\phi$, Regression, Adversarial.

For the convergence upper bound, following the decomposition of estimation
error in Xing et al. (2021b), beside the part from
$\|\widehat{\theta}-\theta_{0}\|^{2}$ in clean training, there is one extra
part due to the information limit on $\Sigma_{1,1}$. However, since there are
$\sum n_{i}$ samples to provide information of $x_{1}$, the new term can be
ignored, so the minimax lower bound in adversarial training is the same to
clean training.

In terms of the lower bound, we know that

$\displaystyle\theta(\epsilon)=(\Sigma_{1,1}+\lambda
I_{d_{1}})^{-1}\Sigma_{1,1}\theta(0),$

thus following Xing et al. (2021b), we consider two scenarios: (3)
$\Sigma_{1,1}$ is known and we impose prior distribution on $\theta(0)$; (4)
$\theta(0)$ is known and we impose prior distribution on $\Sigma_{1,1}$.
Following the arguments in clean training, we have scenario (3) reduces to
clean training setup. For scenario (4), following Xing et al. (2021b) we
obtain

$\displaystyle\inf_{\widehat{\theta}}\sup_{\Sigma,a,\epsilon}\mathbb{E}\|\widehat{\theta}-\theta(\epsilon)\|^{2}=\Theta\left(\frac{d_{1}}{n_{1}+n_{2}+n_{3}+n_{4}}\right).$

To conclude,

$\displaystyle\inf_{\widehat{\theta}}\sup_{\Sigma,a,\epsilon}\mathbb{E}\|\widehat{\theta}-\theta(\epsilon)\|^{2}=\Theta\left(\frac{\sigma^{2}d_{2}}{n_{1}+n_{2}}+\frac{d_{1}}{n_{1}+n_{3}}+\frac{d_{1}}{n_{1}+n_{2}+n_{3}+n_{4}}\right)=\Theta\left(\frac{\sigma^{2}d_{2}}{n_{1}+n_{2}}+\frac{d_{1}}{n_{1}+n_{3}}\right).$

∎