Reproducibility protocol for ANN-Benchmarks: A
benchmarking tool for approximate nearest neighborsearch algorithms⋆,⋆⋆Martin Aumüllera , Erik Bernhardssonb , Alexander Faithfullaa IT University of Copenhagen, Denmarkb Better, Inc., United States

Abstract
In (Aumüller, Bernhardsson, Faithful, Information Systems, 2020), a benchmarking framework for nearest neighbor search implementations was introduced.
The framework was used to evaluate a selection for nearest neighbor searchalgorithms on different datasets. This reproducibility companion paper details
the experimental setup and provides a step-by-step description to reproduce theoriginal results.

1

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1. Introduction
Nearest neighbor search is one of the central techniques in many diverse
areas of computer science such as image processing, recommender systems, data
mining, and machine learning. The task of a nearest neighbor search algorithm
is to preprocess a dataset X ⊆ Rd of n d-dimensional data points to answer
nearest neighbor queries: Given a query point x ∈ Rd , return the k nearest
neighbors to x in X. While this can be efficiently solved for low-dimensionalsettings, such as d ∈ {2, 3}, exact algorithms often fall back to being similar (orworse) than a linear scan in high dimensions, a phenomenon called the “curse ofdimensionality”.
The present paper is a reproducibility companion paper of our primary
paper [1], which introduces a benchmarking framework for implementations ofnearest neighbor search algorithms called ANN-Benchmarks. [1] focused on a
succinct description of the general approach of the framework, and presented anevaluation of state-of-the-art nearest neighbor search algorithms at the end of2017 until the submission in mid-2018.
As discussed by Chirigati et al. in [2], many areas of science are in a reproducibility crisis. In particular in experimental computer science, there exist little⋆ DOI of original article: https://doi.org/10.1016/j.is.2019.02.006⋆⋆ Code repository: https://github.com/maumueller/ann-benchmarks-reproducibility

Research artifacts: https://doi.org/10.5281/zenodo.4607761

Preprint submitted to Elsevier

July 18, 2023

19
20
21
22
23
24
25

26
27
28
29
30
31
32

33
34
35
36
37
38
39
40
41
42
43
44
45

systematic effort to ensure soundness and reproducibility of experimental results.
The contribution of the present paper is to provide an exact reproducibility
protocol for benchmarking approximate nearest neighbor search algorithms,
thus contributing to increasing reproducibility in this area. Firstly, it allows to
reproduce our primary paper [1]. Secondly, it contains information on how toextend ANN-Benchmarks to include new algorithms and datasets, thus serving
as starting point for future research on the topic.
Relation to current state of ANN-Benchmarks. This reproducibility companion
paper details the exact steps needed to reproduce the plots in the paper [1].
Since the submission of the paper, many new algorithms were added to ANNBenchmarks, and existing ones were refined. See http://ann-benchmarks.com
for an up-to-date overview of nearest neighbor search implementations. Whilethe current setup targets the reproduction of [1], the steps mentioned here arealso valid for the more recent version of the benchmarking tool.
Experiments in Aumüller et al. [1]. We invite the reader to first take a look at[1] to get an idea about the scope of the framework. In a nutshell, we used ourframework to compare many state-of-the-art nearest neighbor search algorithms
on a broad collection of high-dimensional datasets. From each dataset, a certain
collection of points was chosen as queries and presented to the algorithms.1
Implementations were measured on their ability to quickly return a “goodapproximation” of the true nearest neighbors. Usually, this means that thethroughput (measured in queries per second ) was put into relation to the average
recall (the average of the fraction of correct nearest neighbors among the queryanswers over all queries).
Results were reported on these performance/quality measures, but also onquestions such as “how long does it take to build an index that will allow toachieve a recall of at least .9?” and “how adaptive are algorithms?”

48

A note to the reviewers. To speed up the reproducibility process, we would
appreciate if problems are directly reported as issues via https://github.com/
maumueller/ann-benchmarks-reproducibility.

49

2. ANN-Benchmarks framework overview

46
47

50
51
52
53
54
55
56

2.1. Code base
ANN-Benchmarks is primarily written in Python. Please refer to Table 1 fortechnical and legal information of the source code.
ANN-Benchmarks takes care of setting up, running, and evaluating a nearest
neighbor search experiment. An experiment consists of running k-NN queries fora specified implementation on a predefined dataset. All implementations considered in [1] are listed in Table 2. One run consists of building the index for a list of
1 For [1] those queries were chosen at random, but more refined approaches were later
introduced in [3].

2ANN-Benchmarks
Github Repository
Release used in this work
Legal code license
Source code languages
Runtime requirements
Documentation

Description
https://github.com/maumueller/
ann-benchmarks-reproducibility/
is minor revision1
MIT
Python 3
Python at least 3.6, Docker version at least 1.41
Source code and readme

Table 1: Technical and legal information of the latest version of the ANN-Benchmarks software
library used in our experiments.

57
58
59
60
61
62

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

78
79
80
81
82
83
84
85
86
87
88

dataset points (using parameters related to index building), and running queries
with parameters related to query processing. The authors of the individual implementations provided these parameter choices themselves, and ANN-Benchmarks
just carries out the experiment using these parameters. The actual wrappers forthe implementations are found in ann benchmarks/algorithms/, a standard
set of parameters can be found in algos.yaml.
2.2. An Overview over the Architecture
ANN-Benchmarks uses Docker to encapsulate different implementations. A
conceptional overview over the architecture is given in Figure 1. This was anecessary step to allow easy handling of different implementations, which eachone having its own dependencies. The Python runner invokes these Docker
containers with the arguments necessary to run the experiment at hand. One
container contains exactly one library tested by the benchmarking framework.
Using Docker allows to limit the resources of each container, since we run
all implementations single-threaded and enforce a limit on the memory usage.
The main controller that manages all experiments lives outside the Docker
environment and invokes different Docker containers based on the experimentthat is run. During setup of the container, it mounts the Python module andthe data/ folder containing all datasets as read-only into the container to readthe data, and mounts the results/ directory as read-write to write the resultsback to the filesystem.
2.3. Dataset format
Table 3 gives an overview over the datasets considered in [1]. Generatingthese datasets is done by the script create datasets.py, which internally calls
ann benchmarks/dataset.py. Each dataset is internally stored as an hdf5
file, that contains the dataset points, the query points, the ids of the 100nearest neighbors to each query point, and the distances of these points to thequery. Since building this ground truth takes a considerable amount of time,
all datasets are stored on https://ann-benchmarks.com. Before creating thedataset locally, the script always tries to download the hdf5 file first. For thesake of reproducibility, all of the datasets are stored in the research artifacts
detailed in Section 3.2.
3

Figure 1: Conceptual overview over the architecture.

Principle
graph-based
tree-based
LSH
other

Algorithms
KGraph (KG) [4], SWGraph (SWG) [5, 6], HNSW [7, 6]
PyNNDescent (NND) [8], PANNG [9], ONNG [9, 10]
FLANN [11], BallTree (BT) [6], Annoy (A) [12]RPForest (RPF) [13], MRPT [14]MPLSH [15, 6]
Multi-Index Hashing (MIH) [16] (exact Hamming search),
FAISS-IVF (FAI) [17] (inverted file)

Table 2: Overview of tested algorithms (abbr. in parentheses).

89
90
91
92
93
94
95
96
97
98
99
100
101

102
103
104
105
106
107

2.4. Result format
After finishing a run, a single hdf5 file containing the results of the run
is written to the file system in the results/ folder. See Figure 2 for a partial
snapshot of this directory. We stress that we write the raw answer of the queryalgorithm of the algorithm under consideration, that means the identifiers of thenearest neighbors returned for the individual queries. Only later on, this data isused to compute metrics such as (approximate) recall. The hierarchy it uses isdataset/number of nearest neighbors/algorithm/. Each file contains the resultsof a single run (i.e., one set of query parameters). Each file contains general
information of the run and details of the measurements, such as the identifiers of
the nearest neighbors that were returned, query times, build time of the index,
etc. The result file can be explored in the interactive Python console as shownin Figure 3.
2.5. Post-Processing results
After running the experiments, there are a couple of choices to visualize orprocess the data for another setting. The script plot.py creates a single PNG
plot on a specific dataset for two given metrics, such as recall and throughput.
create website.py generates a website that visualizes all runs that can befound in the results/ directory, split up by dataset (with varying algorithms)

4

results/
gist-960-euclidean/
10/
annoy/
euclidean 100 100
euclidean 100 1000
BallTree(nmslib)/
euclidean vptree desiredRecall 0 1 tuneK 10 false
euclidean vptree desiredRecall 0 2 tuneK 10 false
bruteforce-blas/
euclidean
Figure 2: Overview over results in results/ folder>>> f = h5py . File ( " e u c l i d e a n _ r e v e r s e _ 1 _ t r u e _ 1 0 0 " )>>> dict ( f ){ ’ metrics ’: < HDF5 group " / metrics " (3 members ) >, ’,→ distances ’: < HDF5 dataset " distances " : shape,→ (1000 , 10) , type " < f4 " >, ’ times ’: < HDF5,→ dataset " times " : shape (1000 ,) , type " < f4 " >,,→ ’ neighbors ’: < HDF5 dataset " neighbors " :,→ shape (1000 , 10) , type " < i4 " >}>>> dict ( f . attrs ){ ’ algo ’: ’ kgraph ’ , ’ distance ’: ’ euclidean ’ , ’,→ run_count ’: 2 , ’ batch_mode ’: False , ’ dataset,→ ’: ’ gist -960 - euclidean ’ , ’ build_time ’:,→ 2678.368325471878 , ’ count ’: 10 , ’ name ’: ’,→ KGraph ( euclidean ) ’ , ’ best_search_time ’:,→ 0.01496616005897522 , ’ index_size ’:,→ 2022140.0 , ’ expect_extra ’: False , ’,→ candidates ’: 10.0}>>> f [ " times " ][:10] # individual query times of,→ the first 10 queries
array ([0.0064466 , 0.01282668 , 0.00558615 ,,→ 0.0106256 , 0.01036716 , 0.005831 ,,→ 0.00877213 , 0.01525331 , 0.00530338 ,,→ 0.01109028] ,dtype = float32 )Figure 3: Structure of5 the HDF5 result file.

Dataset
SIFT
GIST
GLOVE
NYTimes
Rand-Euclidean
SIFT-Hamming
Word2Bits

Internal Name
sift-128-euclidean
gist-960-euclidean
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-256-hamming
word2bits-800-hamming

Data/Queryd Metric
1 000 000/10 000 128 Eucl.
1 000 000/10 000 960 Eucl.
1 183 514/10 000 100 Cos.
234 791/10 000 256 Eucl.
1 000 000/10 000 128 Cos.
1 000 000/1 000 256 Ham.
399 000/1 000 800 Ham.

Table 3: Datasets under consideration.

108
109
110
111

112
113
114
115
116
117
118
119
120

or algorithm (with varying datasets). For reproducing [1], the main scripts aredata export.py and reproducibility/generate result tables.py, which exports theraw data to a csv file and generates data that can be plotted via pgfplots. The
latter script also has special code to generate Figures 10 and 13 in [1].
2.6. Adding a new dataset
Adding a new dataset works by writing a Python function that takes careof downloading and parsing the original dataset into numpy arrays. ANNBenchmarks takes care of computing the ground truth nearest neighbors automatically. The code for this has to be added to ann benchmarks/datasets.py
by adding the respective function that calls write output as its final step, andadding the dataset in the bottom to the dictionary DATASETS. If runs on thesedatasets should be carried out, the dataset name has to be included in the forloops present in reproducibility/run experiments.sh.

132

2.7. Adding a new algorithm
Adding a new implementation of an ANN algorithm requires to install thealgorithm in a docker environment. If the library is called XXX, the installation
goes into the file install/Dockerfile.XXX that inherits the ann-benchmarks
base image. Next, a wrapper class that inherits from BaseANN has to be added
to the wrappers in ann benchmarks/algorithms/. Finally, an entry into thealgos.yaml file has to be created that points to the constructor, the docker
image, and contains the collection of parameters that should be tested. If
runs with this implementation should be carried out, the yaml entries foundin reproducibility/ have to be edited to add the implementation with theparameter space that should be inspected. Most prominently, this has to bedone in reproducibility/standard runs.yaml.

133

3. The reproducibility experiments

121
122
123
124
125
126
127
128
129
130
131

134
135
136
137

This section describes the workflow to reproduce the experimental resultsfrom [1]. The original experiments were carried out on an Amazon EC2 c5.4xlarge
instance, which was equipped with Intel Xeon Platinum 8124M CPU (16 available
cores, 3.00 GHz, 25MB L3 Cache) and 32 GB of RAM using Amazon Linux.
6Platform
Ubuntu 1†,♢

Operating Sys.
Ubuntu 16.10

Ubuntu 2†

Ubuntu 18.04

Configuration
2x 14-core Intel Xeon E5-2690v4
2.60GHz, 512 GB RAM
Quadro M4000, 6 TB HDD
12-core Intel Xeon E5645
2.40GHz, 48 GB RAM, 2 TB HDD

Tested by
Authors

Authors
Reviewers
Reviewers

Table 4: Detailed configurations of platforms used in the reproducibility study. † supports
CPU-based experiments; ♢ supports GPU-based experiments.

Platform
Ubuntu 1
Ubuntu 2

Libraries & Env. Variables
Python 3.6.5, Cuda 10.2
PARALLELISM = 20
Python 3.6.5
PARALLELISM = 3
GISTPARALLELISM = 1

Running time (CPU)
4 days, 2 hours, 17 mins

Tested by
Authors

9 days, 27 mins

Authors

Reviewers
Reviewers
Table 5: Timings, libraries, and environmental variables used for reproducing the experiments.

138
139
140
141

Table 4 reports on the configurations used to reproduce the results of theexperiment. Table 5 reports on the time it took to carry out the experiments,
and the environmental variables used for running them on the specific machines.
More details on the requirements to run all experiments can be found below.

149

Minimum requirements. To run all experiments, a modern (Intel) CPU with
AVX-2 support, at least 20 GB of RAM, and a GPU supporting CUDA 10.2
or newer is required. If a GPU is not present, the GPU experiments cannot be
carried out. If fewer than 20 GB of RAM are present, the dataset GIST-960Euclidean cannot be processed. If fewer than 10 GB of RAM are available, theexperiments cannot be run. If the CPU does not support AVX-2, the algorithm
ONNG cannot run. At least 30 Gb of free space is necessary on a fresh installation
to run all experiments.

150

3.1. General Overview

142
143
144
145
146
147
148

151
152
153
154
155
156
157
158

Figure 4 depicts the overall flow of the reproducibility protocol. There are two
ways to carry out the reproducibility protocol. If an existing Linux-based machineis available, one can set up the framework following the guide in Section 3.3.
Otherwise, a Vagrant box is available that sets up an Ubuntu 18.04 VM witha pre-installed framework. This method is covered in Section 3.4. After the
installation succeeded, one can proceed to carry out the experiments as describedin Section 3.5. After completing these experiments, raw results are processed
into csv files and plots that allow reproducing the paper.
7

Figure 4: Overview over the reproducibility protocol. The framework can be installed on an
existing system or using a Vagrant box that sets up a virtual machine with Ubuntu 18.04.
Afterwards, experiments can be carried out. From these, quality metrics are computed and theoriginal paper is reproduced. Detailed checks are possible via inspecting intermediate outputs,
such as the csv file.

159
160
161
162
163
164
165
166
167
168
169

3.2. Research Artifacts
All research artifacts are provided in [18]. It fixes the version of the codeused to produce the results in this reproducibility study. It also contains tar
archives containing (i) all datasets used in the study, (ii) the original raw results
used to produce [1], (iii) the raw results that we got from this reproducibility
work, (iv) a Vagrantfile that spawns an Ubuntu VM ready to run all experiments,and (v) a tar file containing all binary Docker images. In these research artifacts, as well as in the Github repository at https://github.com/maumueller/
ann-benchmarks-reproducibility/, the steps necessary to install, run, andevaluate the reproducibility protocol are documented, enabling easy copy-andpasting in a more convenient way than from a PDF.

8

Step

(1)

(2)

(3)

(4)

Installation Guide for Ubuntu 18.04
Install docker$ sudo apt-get remove docker docker-engine docker.io containerd runc
$ sudo apt-get update && sudo apt-get -y install apt-transport-https
ca-certificates curl gnupg lsb-release$ curl -fsSL https://download.docker.com/linux/ubuntu/gpg |sudo gpg - -dearmor -o /usr/share/keyrings/docker-archive-keyring.gpg$ echo ”deb [arch=amd64 signed-by=/usr/share/keyrings/docker-archive-keyring.gpg]
https://download.docker.com/linux/ubuntu $(lsb release -cs) stable” |sudo tee /etc/apt/sources.list.d/docker.list >/dev/null$ sudo apt-get update && sudo apt-get install -y docker-ce docker-ce-cli containerd.io$ sudo usermod -aG docker $USER # logout and login again
Install nvidia-docker (GPU, requires working nvidia driver)$ distribution=$(. /etc/os-release;echo $ID$VERSION ID)&& curl -s -L https://nvidia.github.io/nvidia-docker/gpgkey | sudo apt-key add && curl -s -L https://nvidia.github.io/nvidia-docker/$distribution/nvidia-docker.list |sudo tee /etc/apt/sources.list.d/nvidia-docker.list$ sudo apt-get update$ sudo apt-get install -y nvidia-docker2$ sudo systemctl restart docker
Install Python 3.6, Git, LATEX(for post-processing)$ sudo apt-get update$ sudo apt-get install -y python3-pip build-essential git texlive-fonts-extra texlive-science latexmk
Clone Github Repository, prepare docker images, setup datasets$ git clone https://github.com/maumueller/ann-benchmarks-reproducibility$ cd ann-benchmarks-reproducibility$ pip3 install -r requirements py36.txt # requirements py38.txt if running Python 3.8.
$ python3 install.py - -proc 5$ wget https://zenodo.org/record/4607761/files/data.tar?download=1 -O data.tar$ tar xf data.tar
Table 6: Installation guide on existing machine

170
171
172
173
174
175
176
177
178
179
180

3.3. Installation on an Existing Linux System
Installation. To install the software on an existing machine, a version of Linuxwith a Python version of at least 3.6 and a Docker version of at least 1.41 isrequired. For Ubuntu 18.04, the steps to set up a machine are detailed in Table 6.
Step (1) in this table sets up Docker on the system. Step (2) sets up the GPU
support for Docker containers in Ubuntu. Step (3) sets up a Python installationand LATEX. These first three steps depend on the choice of distribution and willvary on existing systems. Step (4) sets up the local framework and will notvary. At the end of running the installation script install.py, the individual
implementations will report on a successful or failed installation. It is necessarythat all installations succeeded before proceeding.

9

Step
(1)

(2)

Installation Guide from Vagrantfile
Install Virtualbox and Vagrant on Ubuntu$ sudo apt-get update && sudo apt-get install -y wget virtualbox vagrantInstall Vagrant Box$ mkdir ann-benchmarks-reproducibility && cd ann-benchmarks-reproducibility$ wget https://zenodo.org/record/4607761/files/Vagrantfile?download=1 -O Vagrantfile
Edit Line 51 and 52 in Vagrantfile to set suitable CPUs and RAM for the VM$ vagrant up$ vagrant ssh
Table 7: Vagrant guide

181

182
183
184
185
186
187
188
189

190
191
192
193
194
195

Troubleshooting.
• pip3 install -r requirements py36.txt (or pip3 install -r requirements py38.txt)
does not succeed. If the local Python installation already has different
versions of the necessary libraries installed, the installation might fail.
In this case, pip3 install -r requirements.txt will try to install thedependencies without fixing library versions. If this does not work as well,
we recommend creating virtual environments to start with a clean state
for reproduction, as discussed https://docs.python.org/3.8/tutorial/
venv.html.
• python3 install.py - -proc 5 reports failed installations. While we
fixed all versions of the git repositories of the tested implementations,
we do not control these repositories. If an installation fails, the research
artifacts [18] contain binary images of the containers used for this reproducibility experiment. These can be loaded into docker via docker load
< docker-images.tar.gz.

197

If these steps do not help, we recommend to set up a fresh VM using Vagrant asdetailed in the next subsection.

198

3.4. Installation using Vagrant

196

203

We provide a Vagrantfile in the research artifacts discussed in Section 3.2 that
automatically sets up a VM ready to carry out the experiments. A step-by-step
installation guide for this case is given in Table 7. (The installation of Vagrant
will be different on non-Ubuntu-based systems.) This setup does not allow tocarry out the GPU experiments.

204

3.5. Running experiments

199
200
201
202

205
206
207

All the details to run the experiments and reproduce the paper are given in
Table 8. Figure 5 provides a more detailed view on running and processing theexperiments and the raw results.

10

Figure 5: Overview of the reproducibility process in Table 8.

208
209

210
211
212
213

214
215
216

217
218
219
220

221
222
223

224

225
226

227
228
229
230

General comments. Before detailing the execution of the experiments, we provide
the following general remarks.
• Log files. Running the experiments will give an high-level overview overthe status of the experiments. Detailed logs are stored in logs/. Eachdataset and k-NN combination, for k ∈ {10, 100}, creates exactly one log
file.
• Failures. If experiments are interrupted, the framework will recover andonly run those experiments for which it did not yet store results. Thus, thescripts can be re-run exactly as they are and do not have to be adapted.
• Graceful degradation. The framework gracefully handles unavailable
installations and resource limitations, e.g., the amount of RAM available.
It will fail on carrying out these experiments, as can be seen in the detailed
logs, but will attempt to run all other experiments.
• Detailed overview. Appendix A contains detailed information about
the amount of time certain experiments take and the amount of memorythat is approximately necessary to carry out these experiments.
• Adapting experiments. The main bash script will take care of running$ python3 run.py - -algorithm ALGO - -dataset DATA - -count[10, 100] [- -batch]with the arguments to reproduce the paper. If certain runs should be leftout, they can be removed from the bash script in reproducibility/run experiments.shor the yaml configuration files in reproducibility/, or the experiments
can be started directly by invoking python3 run.py.
11

Step

Running Experiments and Reproducing Results
Running CPU-based experiment(1)$ PY=python3 PARALLELISM=10 GISTPARALLELISM=3
bash reproducibility/run experiments.sh | tee -a runs.log
Installing and running GPU-based experiment(2)$ python3 install.py - -algorithm faissgpu$ bash reproducibility/run gpu.shCreate output files

(3)

(4a)

(4b)

$ sudo chmod -R 777 results && python3 data export.py - -out res.csv$ mkdir -p paper/result tables/$ python3 reproducibility/create result tables.py res.csv paper/result tables/$ python3 reproducibility/generate and verify plots.py
Produce LATEX paper with working latex installation$ cd paper && latexmk -pdf paper.tex
Produce LATEX from Docker$ cd paper$ docker build . -t ann-benchmarks-reproducibility-latex$ docker run -it -v ”$(pwd)”/:/app/:rw ann-benchmarks-reproducibility-latex:latest
Table 8: Running guide for experiments

231
232

233
234
235

236
237
238
239
240
241
242
243
244
245
246
247
248
249

250
251

Running CPU-based experiments. First, we run all CPU-based experiments by
invoking:$ PY = python3 PARALLELISM =10 GISTPARALLELISM =3 bash
reproducibility / run_experiments . sh | tee -a runs .
log
The environmental variable PY can be used to point to a custom Python
3.6 installation, e.g., provided by Anaconda. All individual runs of experimentsin this part are carried out on a single CPU using Docker. The environmental
variable PARALLELISM can be used to spawn multiple containers in parallel. On
the machine Ubuntu 1, we used PARALLELISM=20. In general, around 10 GB
of RAM are needed per process for most of the datasets. Thus, on a machinewith 32GB of RAM, PARALLELISM can be set to at most 3. Note that for thelargest dataset GIST-960-Euclidean, around 20GB of RAM are necessary perprocess, which meant in our setup that we had a peak memory usage of 400 GB.
The environmental variable GISTPARALLELISM controls the number of parallel
instances run for the GIST dataset. This was set to 20 as well on the Ubuntu 1
machine. On a machine with 32GB of RAM, GISTPARALLELISM must be set to
1. The script run experiments.sh will report on the time it took to carry out
all experiments.
Running GPU-based experiments. The paper [1] contains a single run of a
GPU-based experiments in Figure 12. This run was carried out in a local
12

Step

Reproduce Results From Primary Paper
Getting raw results(1)$ wget https://zenodo.org/record/4607761/files/results original.tar?download=1 -O results.tar$ tar xf results.tar
Create output files

(2)

(3a)

(3b)

$ sudo chmod 777 -R results/$ python3 data export.py - -out res.csv$ mkdir -p paper/result tables/$ python3 reproducibility/create result tables.py res.csv paper/result tables/$ python3 reproducibility/generate and verify plots.py
Produce LATEX paper with working latex installation$ cd paper && latexmk -pdf paper.tex
Produce LATEX from Docker$ cd paper$ docker build . -t ann-benchmarks-reproducibility-latex$ docker run -it -v ”$(pwd)”/:/app/:rw ann-benchmarks-reproducibility-latex:latest

Table 9: Reproduce paper from existing, raw results. Requires installation steps from Table 6
or Table 7 to be completed; the working directy is ann-benchmarks-reproducibility.

252
253
254
255
256
257

258
259

260
261
262
263
264

265
266
267

268
269

environment outside a docker container. To reproduce this run, we provide a
script in reproducibility/run gpu.sh. A Linux-based environment with a CUDA
runtime of at least 10.2 is necessary. This can be checked by inspecting theoutput of nvidia-smi. Furthermore, the nvidia-runtime for Docker must be
installed, as detailed in Table 6. If these requirements are met, the GPU run isreproduced by running:$ python3 install . py -- algorithm faissgpu$ bash reproducibility / run_gpu . sh
Ubuntu 1 was equipped with a Quadro M4000 with compute engine 5.2 andall runs were finished within 10 minutes. If the reproducibility environment
features an older GPU, the version of the compute engine must be manually set
during compilation of FAISS in install/Dockerfile.faissgpu by editing theflag DCMAKE CUDA ARCHITECTURES="75;72;52".2
3.6. Processing Raw Results
If all runs above have been carried out, we can start reproducing the plots inthe paper. Run$ sudo chmod 777 -R results /$ python3 data_export . py -- out res . csv
2 An overview over the compute engines can be found on https://developer.nvidia.com/
cuda-gpus.

13

270
271
272
273

274
275
276
277
278
279
280
281
282
283
284

285

286
287
288
289
290

291
292
293
294
295
296

297
298
299
300

301
302
303
304
305
306
307
308
309
310

$ mkdir -p paper / result_tables /$ python3 reproducibility / c r e a t e _ r e s u l t _ t a b l e s . py res .
csv paper / result_tables /$ python3 reproducibility / g e n e r a t e _ a n d _ v e r i f y _ p l o t s . py
to create all the raw tables used by pgfplots during the final LATEX compilation.
Since exporting the results will compute all quality metrics, it took around 1
hour on our machine. (However, results are cached, so this cost applies only
once.) All runs that have to be completed in order to build the paper are listed inTable 10. The script generate and verify plots.py will generate the plot tex
files necessary to compile the document. It will also list missing data points from
Table 10, e.g., because the computation timed out, a too old CPU architecture
was used, or no GPU was present. It will print the commands that can be used
to directly re-run these experiments. However, the paper can be compiled evenif files are missing, the respective lines in plots are then just omitted. Compile
the paper by changing to the paper directory and compiling paper.tex, i.e.,$ cd paper&& latexmk - pdf paper . tex

This requires a standard latex installation for scientific writing that was installedin Table 6. If such a system is not present, we provide another Docker containerin paper. The reproducibility steps are then from within the paper directory.
The final PDF can be seen in paper/paper.pdf and the plots can be compared tothe original paper [1].
3.7. Comparison to Original Results
The result of the final step of the previous section is a version of the paperthat is produced from the results obtained by running the experiments. A moredetailed comparison can be achieved by comparing the csv files individually. We
provide a Jupyter notebook eval.ipynb with some example comparisons in the
Github repository.
3.8. Reproduction from the original raw results
To avoid rerunning all experiments, the raw result of the original runs can beaccessed from the research artifacts (see Section 3.2). It is required to complete
the Installation step in Table 6. Then, carry out the steps in Table 9.
3.9. Reflection on the Reproducibility Setup
Given the use of Docker in the ANN-Benchmarks setup, it proved difficult
to provide a fully dockerized environment. We resorted to providing a VM
image which uses docker internally. However, this makes it difficult to run the
GPU-based experiments. On the other hand, ANN-Benchmarks comes with avery lightweight set of dependencies and is easy to install locally.
ANN-Benchmarks is a work in progress. Many parts of the benchmarking
framework and the benchmarked implementations changed over time. This
present reproducibility companion paper describes the steps to reproduce [1],but the very same setup works for producing all results on more recent versions.
14

Datasetgist-960-euclidean

Count
100

glove-100-angular

10100
nytimes-256-angularrandom-10nn-euclidean

1010

sift-128-euclidean

10100
sift-256-hamming
word2bits-800-hamming

10
10

Implementations
mrpt, annoy, SW-graph(nmslib),
faiss-ivf, hnsw(nmslib), pynndescentbruteforce-blas, BallTree(nmslib), hnsw(nmslib),
pynndescent, annoy, SW-graph(nmslib), faiss-ivf,
kgraph, flann, NGT-onng
BallTree(nmslib), hnsw(nmslib), pynndescent, annoy,
SW-graph(nmslib), faiss-ivf, kgraph, flann, NGT-onng
hnsw(nmslib), annoy, faiss-ivf
pynndescent, annoy, SW-graph(nmslib), faiss-ivf,
kgraph, hnsw(nmslib), NGT-onng
faiss-ivf-gpu-batch, BallTree(nmslib), hnsw(nmslib),
pynndescent, annoy, SW-graph(nmslib), faiss-ivf-batch
faiss-gpu-bf-batch, hnsw(nmslib)-batch, faiss-ivf,
kgraph, flann, NGT-onng
BallTree(nmslib), hnsw(nmslib), pynndescent, annoy,
SW-graph(nmslib), faiss-ivf, kgraph, flann, NGT-onng
annoy-euclidean, NGT-panng, annoy, faiss-ivf
annoy-euclidean, NGT-panng, annoy, faiss-ivf

Table 10: Runs that need to finish before generating all plots.

318

In particular, we used the version of ANN-Benchmarks from January 2021 toreproduce the old results from 2017 and 2018. The main difficulty was in tracing
the exact versions of the nearest neighbor search implementations in their GitHub
repositories.
Of the time of writing, ANN-Benchmarks compares 26 different nearest
neighbor search implementations while the experiments in this reproducibility
companion paper used only 14. See ann-benchmarks.com for an up-to-date
overview of nearest neighbor search algorithms.

319

4. Differences regarding our primary paper

311
312
313
314
315
316
317

320
321
322
323
324
325
326
327
328
329

330
331

Since most of our experiments consider the raw throughput achieved by the
implementations, the compute architecture has a big influence on the individual
plots. The throughput results on Ubuntu 1 are roughly 1.5 to 2 times slower than
the architecture used in the primary paper. However, general trends translate
well into the new setting. Figure 6 and Figure 7 compare Figure 7 in [1] to themeasurements on the machine used for reproduction. While absolute performancedecreases, performance trends are comparable. We added two versions of [1]using the original results and the results from the reproducibility work to research
artifacts discussed in Section 3.2.
We noticed the following differences between the reproduced plots and [1].
1. Performance of NND. The implementation of PyNNDescent [8] performed
worse (in relation to others) on the new setup. We tried other (old) versions,
15

GIST

GLOVE

0.25

0.5 0.75
RecallGLOVE (k = 100)

NYTimes

Rand-Euclidean

SIFT

105

QPS (1/s)

104
103
102
101

0

1

0.25

0.5
0.75
Recall10

0.25

0.5 0.75
Recall1

Figure 6: Original: Recall-QPS (1/s) tradeoff - up and to the right is better, 10-nearest
neighbors unless otherwise stated, left: Annoy, middle: FAISS-IVF, right: HNSW. Recall measures
the fraction of actual nearest neighbors among the returned 10 points of the implementation,
averaged over 10 000 queries; QPS (queries per second) measures the time it took to answer
these queries.

GIST

GLOVE

0.25

0.5 0.75
RecallGLOVE (k = 100)

NYTimes

Rand-Euclidean

SIFT

105

QPS (1/s)

104
103
102
101

0

1

0.25

0.5
0.75
Recall10

0.25

0.5 0.75
RecallFigure 7: Reproduced: Recall-QPS (1/s) tradeoff - up and to the right is better, 10-nearest
neighbors unless otherwise stated, left: Annoy, middle: FAISS-IVF, right: HNSW.

16

1

332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364

365

366
367
368

369
370
371

372
373
374

but the results were the same. More recent versions perform much better(being on par with HNSW in many cases), but we decided to report using
an old version that is closer to the original performance.
2. Omitted data points. To improve the readability of the plots, we
manually removed some data points in the original paper. For example,
Figure 6 contained many data points with recall close to 1 which were
removed. The reproduced version does not clean such data points.
3. Differences in Figure 9. PANNG is much faster in the reproducibility
setup than in the original paper. This is because PANNG and ONNG arepart of one library, and we had to use a more recent version to include
ONNG. In the original paper, PANNG experiments where carried out in spring
2017, whereas the ONNG runs were done in autumn 2018. Furthermore, theline for Annoy (eucl.) on the plot to the left was wrong in the original
paper. The performance is much better, as reported in the reproducibility
experiment. One can see the mistake by a careful comparison between
Figure 4 (bottom, left) and Figure 9 in [1].
4. Longer build times. We were not able to build indices that would allow
for the same recall of HNSW on the reproducibility architecture. We
increased the timeout to 12 hours (from 6 in the original paper) for anindividual experiment.
5. Differences in Figure 12. The reproducibility machine has more coresand thus batch runs on the CPU are faster. On the other hand, its GPU
is worse, so the GPU runs are slower. This means that the differences
between CPU and GPU runs in Figure 12 are not as pronounced as in theoriginal paper.
6. Improvements in Performance in Reproducibility Setup. Despite
the performance differences inherent in the different CPU architectures, we
also noticed that a few data point had improved on the slower architecture.
This is because we set the timeout of individual experiments much higher,
allowing for all indices to finish building. In the original paper, some ofthese runs timed out. However, this does not affect the conclusions drawn
from the results. These differences can be seen in the Jupyter notebook
eval.ipynb that is part of the Github repository.
References[1] M. Aumüller, E. Bernhardsson, A. J. Faithfull, Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms, Inf. Syst. 87(2020).
[2] F. Chirigati, R. Capone, R. Rampin, J. Freire, D. Shasha, A collaborative
approach to computational reproducibility, Information Systems 59 (C)(2016) 95–97.
[3] M. Aumüller, M. Ceccarello, The role of local intrinsic dimensionality inbenchmarking nearest neighbor search, in: SISAP, Vol. 11807 of Lecture
Notes in Computer Science, Springer, 2019, pp. 113–127.
17

375
376

377
378
379

380
381

382
383
384

385
386

387
388

389
390
391

392
393

394
395

396
397

398
399
400
401
402

403
404
405

406
407

408
409

[4] W. Dong, KGraph.
URL https://github.com/aaalgo/kgraph[5] Y. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov, Approximate nearest
neighbor algorithm based on navigable small world graphs, Inf. Syst. 45(2014) 61–68.
[6] L. Boytsov, B. Naidan, Engineering efficient and effective non-metric space
library, in: SISAP’13, pp. 280–293.
[7] Y. A. Malkov, D. A. Yashunin, Efficient and robust approximate nearest
neighbor search using Hierarchical Navigable Small World graphs, ArXiv
e-prints (Mar. 2016). arXiv:1603.09320.
[8] L. McInnes, PyNNDescent.
URL https://github.com/lmcinnes/pynndescent[9] Y. J. Corporation, NGT: PANNG.
URL https://github.com/yahoojapan/NGT[10] M. Iwasaki, D. Miyazaki, Optimization of Indexing Based on k-Nearest
Neighbor Graph for Proximity Search in High-dimensional Data, ArXiv
e-prints (Oct. 2018). arXiv:1810.07355.
[11] M. Muja, D. G. Lowe, Fast approximate nearest neighbors with automaticalgorithm configuration, in: VISSAPP’09, INSTICC Press, pp. 331–340.
[12] E. Bernhardsson, Annoy.
URL https://github.com/spotify/annoy[13] Lyst Engineering, Rpforest.
URL https://github.com/lyst/rpforest[14] V. Hyvönen, T. Pitkänen, S. Tasoulis, E. Jääsaari, R. Tuomainen, L. Wang,
J. Corander, T. Roos, Fast nearest neighbor search through sparse random
projections and voting, in: Big Data (Big Data), 2016 IEEE International
Conference on, IEEE, 2016, pp. 881–888.
URL https://github.com/teemupitkanen/mrpt[15] W. Dong, Z. Wang, W. Josephson, M. Charikar, K. Li, Modeling LSH for
performance tuning, in: CIKM’08, ACM, pp. 669–678.
URL http://lshkit.sourceforge.net/[16] M. Norouzi, A. Punjani, D. J. Fleet, Fast search in hamming space withmulti-index hashing, in: CVPR’12, IEEE, pp. 3108–3115.
[17] J. Johnson, M. Douze, H. Jégou, Billion-scale similarity search with gpus,
CoRR abs/1702.08734 (2017).

18

dataset

count

batch

#experiments#experiments left

10
10
10
10
10
100
100
10
100
10
10
10

false
false
false
false
false
false
false
false
false
false
false
true

57
63
63
1
51
57
63
63
63
35
35
39

533
470
407
406
355
298
235
172
109
74
39
0

glove-100-angular
sift-128-euclidean
random-10nn-euclidean
glove-100-angularnytimes-256-angular
glove-100-angular
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
sift-256-hamming
word2bits-800-hamming
sift-128-euclidean

Table A.11: Experiments carried out by running reproducibility/run experiments.sh.

413[18] M. Aumüller, E. Bernhardsson, A. Faithfull, Research Artifacts for Reproducibility Paper ”ANN- Benchmarks: A benchmarking tool for approximate
nearest neighbor search”.
URL https://doi.org/10.5281/zenodo.4607761

414

Appendix A. Detailed running times

410
411
412

415
416
417
418
419
420

421
422

423
424

425
426
427
428

Table A.11 collects the number of experiments carried out by running theCPU-based experiments. Table A.12 summarizes the running times for carryingout individual parts of the reproducibility protocol on a single thread. Eachindividual experiment can be re-run by invoking python3 run.py with the- -dataset argument pointing to the dataset, and - -algorithm pointing to thealgorithm as labeled in the table. For example, running$ python3 run . py -- algorithm faiss - ivf -- dataset gist
-960 - euclidean -- count 10
will repeat the experiment in the row table below that tests faiss-ivf on the
GIST dataset with 10-NN queries, and take roughly 3 hours to finish.
Note. The current size cannot be trusted because indices were built in parallel
and the index size is estimated from the memory usage before and after building.
(For example, notice some of the negative values.) We are currently re-runningall experiments in a single thread. We will add these numbers to the next version.
algorithm

datasetBallTree(nmslib)

gist-960-euclidean

count

batch

Size (GB )build (h)total (h)

10

False

3.77

7.93

7.95

Continued on next page19

algorithm

datasetBallTree(nmslib)
BallTree(nmslib)
BallTree(nmslib)
BallTree(nmslib)
BallTree(nmslib)
BallTree(nmslib)
BallTree(nmslib)
NGT-onng
NGT-onng
NGT-onng
NGT-onng
NGT-onng
NGT-onng
NGT-onng
NGT-onng
NGT-panng
NGT-panng
SW-graph(nmslib)
SW-graph(nmslib)
SW-graph(nmslib)
SW-graph(nmslib)
SW-graph(nmslib)
SW-graph(nmslib)
SW-graph(nmslib)
SW-graph(nmslib)
annoy
annoy
annoy
annoy
annoy
annoy
annoy
annoy
annoy
annoy
annoy-euclidean
annoy-euclidean
bruteforce-blas
faiss-gpu-bf
faiss-ivf
faiss-ivf
faiss-ivf

gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
sift-256-hamming
word2bits-800-hamming
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
sift-256-hamming
word2bits-800-hamming
sift-256-hamming
word2bits-800-hamming
glove-100-angular
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular

count

batch

Size (GB )build (h)total (h)

100
10
100
10
10
10
100
10
100
10
100
10
10
10
100
10
10
10
100
10
100
10
10
10
100
10
100
10
100
10
10
10
100
10
10
10
10
10
10
10
100
10

False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
True
False
False
False

7.96
1.36
1.37
0.82
1.98
1.39
1.39
-1.97
5.60
2.31
1.96
1.16
2.96
1.85
0.80
1.99
1.73
3.14
4.11
1.54
1.54
0.56
1.55
1.27
1.27
2.67
5.24
7.60
7.63
1.54
6.83
5.77
5.77
6.61
2.15
6.70
3.31
0.00
0.63
4.80
5.00
0.65

5.67
2.32
2.52
5.81
4.72
1.16
1.11
5.06
5.08
1.46
9.98
6.21
6.08
0.74
1.29
0.38
1.86
5.00
3.86
1.53
1.57
0.38
6.29
0.62
0.58
2.20
1.65
0.92
0.93
0.36
1.63
0.68
0.58
0.25
0.10
0.69
0.43
0.00
0.00
3.14
1.73
0.26

5.87
2.35
2.53
5.83
4.77
1.37
1.13
5.23
5.19
1.50
9.99
6.23
6.10
0.77
1.38
0.46
1.87
5.06
4.01
1.54
1.58
0.39
6.30
0.63
0.58
2.76
1.67
1.26
0.98
0.37
1.79
0.69
0.58
0.36
0.22
0.70
0.43
0.00
0.01
3.14
1.89
0.38

Continued on next page20

algorithm

datasetfaiss-ivf
faiss-ivf
faiss-ivf
faiss-ivf
faiss-ivf
faiss-ivf
faiss-ivf
faiss-ivf
faiss-ivf-gpu
flann
flann
flann
flann
flann
flann
flann
flann
hnsw(faiss)hnsw(faiss)hnsw(faiss)hnsw(faiss)hnsw(faiss)hnsw(faiss)hnsw(faiss)hnsw(faiss)hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
hnsw(nmslib)
kgraphkgraphkgraphkgraphkgraphkgraphkgraphkgraphglove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
sift-128-euclidean
sift-256-hamming
word2bits-800-hamming
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
sift-128-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean

count

batch

Size (GB )build (h)total (h)

100
10
10
10
10
100
10
10
10
10
100
10
100
10
10
10
100
10
100
10
100
10
10
10
100
10
100
10
100
10
10
10
10
100
10
100
10
100
10
10
10
100

False
False
False
False
True
False
False
False
True
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
True
False
False
False
False
False
False
False
False
False

0.66
0.41
1.22
0.71
0.71
0.72
1.40
1.68
0.69
4.18
5.20
0.78
0.78
0.40
2.03
1.02
1.02
1.89
4.15
1.39
1.39
0.47
1.09
1.26
1.28
4.35
5.49
4.64
1.93
0.83
3.26
2.79
2.79
2.79
1.57
5.77
13.22
13.22
3.80
2.13
2.41
2.41

0.26
0.23
0.45
0.30
0.30
0.26
0.43
0.54
0.05
9.01
8.07
7.73
7.80
0.14
11.86
1.63
1.68
25.91
26.24
17.04
16.43
14.28
13.36
8.13
7.24
5.77
4.29
22.41
5.76
6.84
8.95
5.22
0.53
5.33
1.24
0.86
3.35
3.25
1.49
0.59
0.26
0.24

0.26
0.26
0.45
0.31
0.41
0.34
0.45
0.55
0.06
9.07
8.07
7.86
7.81
0.14
11.86
1.64
1.68
26.14
26.24
17.04
16.44
14.37
13.39
8.24
7.26
5.85
4.30
22.41
5.76
6.84
9.18
5.22
0.53
5.33
1.40
0.98
3.35
3.25
1.50
0.60
0.37
0.24

Continued on next page21

algorithm

dataset

mih
mih
mrpt
pynndescent
pynndescent
pynndescent
pynndescent
pynndescent
pynndescent
pynndescent
pynndescent
pynndescent
pynndescent
rpforest
rpforest
rpforest

sift-256-hamming
word2bits-800-hamming
gist-960-euclidean
gist-960-euclidean
gist-960-euclidean
glove-100-angular
glove-100-angularnytimes-256-angularrandom-10nn-euclidean
sift-128-euclidean
sift-128-euclidean
sift-256-hamming
word2bits-800-hamming
glove-100-angular
glove-100-angularnytimes-256-angularbuild (h)total (h)

0.42
0.34
0.88
12.04
8.68
3.60
3.48
2.76
14.80
4.71
4.29
3.21
1.88
9.76
9.64
4.21
Total:
Table A.12: Summary of individual running time and memory
requirements to carry out individual parts of the reproducibility
framework.

0.50
0.44
0.88
12.06
8.68
3.60
3.49
2.84
14.80
5.54
4.95
3.23
1.89
10.11
9.66
5.03
452h

22

count

batch

Size (GB )

10
10
100
10
100
10
100
10
10
10
100
10
10
10
100
10

False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False

1.47
6.54
7.82
1.31
6.69
5.05
6.24
1.01
6.31
4.69
5.13
6.14
3.98
19.90
19.31
5.37