are $\nu$-null sets, then there exists $a>0$ such that :

  * •

one has $\mathrm{rot}_{f}(\nu)=a[T^{\prime}]$;

  * •

for every $p/q\in[0,a)\cap\mathbb{Q}$, written in an irreducible way, there
exists $\tilde{z}$ such that
$\tilde{f}^{q}(\tilde{z})=T^{\prime}{}^{p}(\tilde{z})$.

###### Proof.

Recall that $T=T^{\prime}{}^{m}$, where $m\geq 1$. Let us begin by proving
that $\tilde{B}$ is invariant by $T^{\prime}$. It is sufficient to prove that
for every $n>0$ we have $\overline{L(T^{\prime}{}^{n}\tilde{\phi}})\subset
L(\tilde{\phi})$. If $L(\tilde{\phi})\subset L(T^{\prime}{}^{n}\tilde{\phi})$,
then for every $k\geq 1$ we have $L(T^{\prime}{}^{nk}\tilde{\phi})\subset
L(T^{\prime}{}^{n(k+1)}\tilde{\phi})$ and so we deduce that
$L(\tilde{\phi})\subset L(T^{\prime}{}^{nm}\tilde{\phi})$, which contradicts
the inclusion $\overline{L(T^{\prime}{}^{nm}\tilde{\phi})}\subset
L(\tilde{\phi})$. If $L(\tilde{\phi})\cap
L(T^{\prime}{}^{n}\tilde{\phi})=\emptyset$, then $L(\tilde{\phi})$ is disjoint
from its image by $T^{\prime}{}^{n}$. The map $T^{\prime}{}^{n}$ being fixed
point free, Brouwer Translation Theorem [Br] tells us that $L(\tilde{\phi})$
is disjoint from its image by $T^{\prime}{}^{nm}$, which contradicts the
inclusion $\overline{L(T^{\prime}{}^{nm}\tilde{\phi})}\subset
L(\tilde{\phi})$. Similarly, if $R(\tilde{\phi})\cap
R(T^{\prime}{}^{n}\tilde{\phi})=\emptyset$, then $R(\tilde{\phi})$ is disjoint
from its image by $T^{\prime}{}^{nm}$, which contradicts the inclusion
$\overline{R(\tilde{\phi})}\subset R(T^{\prime}{}^{nm}\tilde{\phi})$. The only
remaing case is the case where
$\overline{L(T^{\prime}{}^{n}\tilde{\phi}})\subset L(\tilde{\phi})$.

In the following instead of seeing $\tilde{B}$ as a $\tilde{T}$-strip, we will
see it as a $T^{\prime}$-strip: one can choose $\tilde{\gamma}_{*}$ to be
invariant by $T^{\prime}$ and suppose that
$\tilde{\gamma}_{*}(t)=T^{\prime}\gamma_{*}(t)$ for every $t\in\mathbb{R}$.

By construction of $\tilde{B}$ we know that $\nu(W^{D})=1$. So, $\nu$-almost
every point $z\in\mathrm{dom}(I)$ is recurrent and has a lift
$\tilde{z}\in\widetilde{\mathrm{dom}}(I)$ such that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ is equivalent to
$\tilde{\gamma}_{*}$ at $+\infty$ or $-\infty$. Indeed if $z\in W^{D}$ is
recurrent and if $\tilde{z}$ was a lift of $z$ such that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ accumulates on
$\tilde{\gamma}_{*}$, then there would exist $k\in\mathbb{Z}$ such that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ accumulates on
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(T^{\prime}{}^{k}(\tilde{z}))$.
It is impossible because $z$ is recurrent and so has no self-accumulation by
Corollary 3.9. Hence,
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ does not accumulate
on $\tilde{\gamma}_{*}$, and by the hypothesis of the proposition it cannot go
out of $\tilde{B}$ both before and after it draws $\tilde{B}$. This implies
that it has to be equivalent to $\tilde{\gamma}_{*}$ at $+\infty$ or
$-\infty$.

In fact we can be more precise: if there are $a<a^{\prime}$ and
$b\in\mathbb{R}$ such that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[a,a^{\prime}]}$ is
equivalent to $\tilde{\gamma}_{*}|_{[b,b+1]}$, then either
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[a,+\infty)}$ is
equivalent to a subpath of $\tilde{\gamma}_{*}$ (and equivalent to
$\tilde{\gamma}_{*}$ at $+\infty$ but we will not use this property) or
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{(-\infty,a^{\prime}]}$
is equivalent to a subpath of $\tilde{\gamma}_{*}$. From this we will deduce
the following lemma.

######  Lemma 5.3.

The transverse path $\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$
is equivalent to $\tilde{\gamma}_{*}$. Moreover there is neighborhood
$\tilde{U}$ of $\tilde{z}$ such that if the orbit of $\tilde{z}$ meets
$R\tilde{U}$ for some $R\in\mathcal{G}$, then $R$ is a power of $T^{\prime}$.

###### Proof.

Let us treat the case where
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[a,+\infty)}$ is
equivalent to a subpath of $\tilde{\gamma}_{*}$, the other case being
identical.

Suppose that $\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ is not
equivalent to $\tilde{\gamma}_{*}$. Then, as we have already seen that it
cannot accumulate in $\tilde{\gamma}_{*}$, this means that there exists $b<a$,
$b\in\mathbb{Z}$, such that
$\tilde{I}_{\tilde{\mathcal{F}}}^{b}(\tilde{z})\notin\tilde{B}$.

By recurrence of the point $z$, there exists a sequence of integers
$n_{k}\to-\infty$, and a sequence of deck transformations
$(R_{k})_{k\in\mathbb{N}}\in\mathcal{G}$ such that
$R_{k}\tilde{f}^{n_{k}}(\tilde{z})$ tends to $z$; in particular for any $k$
large enough:

  * •

$\tilde{\gamma}_{*}|_{[b,b+1]}$ is equivalent to a subpath of
$R_{k}\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[n_{k}+a-1,+\infty)}$
(and in particular this path draws $\tilde{B}$);

  * •

$R_{k}\tilde{I}_{\tilde{\mathcal{F}}}^{n_{k}+b}(\tilde{z})\notin\tilde{B}$.

By the same reasoning as before the lemma, we deduce that either the
trajectory
$R_{k}\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[n_{k}+a+1,+\infty)}$
is equivalent to a subpath of $\tilde{\gamma}_{*}$, or
$R_{k}\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{(-\infty,n_{k}+a^{\prime}-1]}$
is equivalent to a subpath of $\tilde{\gamma}_{*}$. By the second point above,
the second situation is impossible. Hence,
$R_{k}\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[n_{k}+a+1,+\infty)}$
is equivalent to a subpath of $\tilde{\gamma}_{*}$.

In particular, this implies that $R_{k}\tilde{\gamma}_{*}$ is equivalent at
$+\infty$ to $\tilde{\gamma}_{*}$. By Lemma 3.3, this implies that
$R_{k}\tilde{\gamma}_{*}\cap\tilde{\gamma}_{*}\neq\emptyset$; more precisely
it implies that for any $n$ large enough,
$R_{k}\tilde{\gamma}_{*}\cap\tilde{\gamma}_{*}|_{[b+n,b+n+1)}\neq\emptyset$,
hence that $R_{k}\tilde{\gamma}_{*}\cap\tilde{\gamma}_{*}$ is infinite. This
implies that $R_{k}\tilde{\gamma}_{*}=\tilde{\gamma}_{*}$, in other words
$R_{k}=T^{\prime}{}^{i_{k}}$ for some $i_{k}\in\mathbb{Z}$.

We deduce that
$T^{\prime}{}^{i_{k}}\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[n_{k}+a+1,+\infty)}$
is equivalent to a subpath of $\tilde{\gamma}_{*}$, equivalently (as
$\tilde{\gamma}_{*}$ is $T^{\prime}$-invariant), for any $k\in\mathbb{N}$, the
path
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})|_{[n_{k}+a+1,+\infty)}$
is equivalent to a subpath of $\tilde{\gamma}_{*}$.

This proves that $\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ is
equivalent to a subpath of $\tilde{\gamma}_{*}$. As it cannot accumulate in
$\tilde{\gamma}_{*}$, this proves that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ is equivalent to
$\tilde{\gamma}_{*}$.

To get the second part of the lemma, consider a neighborhood $\tilde{U}$ of
$\tilde{z}$ such that for every $\tilde{z}^{\prime}\in\tilde{U}$, the path
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z}^{\prime})$ draws
$\tilde{\gamma}_{*}$. If $\tilde{f}^{k}(\tilde{z})\in R\tilde{U}$,
$R\in\mathcal{G}$, then
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ draws
$R(\tilde{\gamma}_{*})$. We deduce that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ is equivalent to
$R\tilde{\gamma}_{*}$. What was done above tells us that $R\in\langle
T^{\prime}\rangle$. ∎

Now, let us consider

  * •

the connected component $\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ of
$\widetilde{\mathrm{dom}}(I)$ that contains $\tilde{\gamma}_{*}$,

  * •

the quotient space $\widehat{\mathrm{dom}}(I)=\widetilde{\mathrm{dom}}(I)/T$,

  * •

the foliation $\hat{\mathcal{F}}$ of $\widehat{\mathrm{dom}}(I)$ lifted by
$\tilde{\mathcal{F}}$,

  * •

the covering projection
$\hat{\pi}:\widehat{\mathrm{dom}}(I)\to\mathrm{dom}(I)$,

  * •

the annulus
$\widehat{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}=\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}/T^{\prime}$,

  * •

the universal covering projection
$\pi:\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}\to\widehat{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$.

######  Lemma 5.4.

It holds that $\nu$-almost every point $z$ has a lift in
$\widehat{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ that is positively recurrent
and has a rotation number $a>0$ (in the annulus). Moreover we have
$\mathrm{rot}_{f}(\nu)=a[T^{\prime}]$.

###### Proof.

We know that $\nu$-almost every point $z$ is positively recurrent and has a
lift $\tilde{z}$ in $\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ that
draws $\tilde{B}$. We have seen in Lemma 5.3 that
$\tilde{I}_{\tilde{\mathcal{F}}}^{\mathbb{Z}}(\tilde{z})$ is equivalent to
$\tilde{\gamma}_{*}$ and that there exists a neighborhood $\tilde{U}$ of
$\tilde{z}$ such that if the orbit of $\tilde{z}$ meets $R\tilde{U}$, for some
$R\in\mathcal{G}$, then $R$ is a power of $T^{\prime}$. Using the fact that
$z$ is recurrent, we deduce that $\widehat{z}=\pi(\widetilde{z})$ is
positively recurrent. By the argument given in the proof of Lemma 4.18, we
deduce that $z$ has rotation number $a>0$. Moreover we have
$\mathrm{rot}_{f}(\nu)=a[T]$. ∎

Now there are two cases to consider. The first case is the case where the
stabilizer of $\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ is generated
by $T^{\prime}$ and the second case is when it is larger. In the first case,
$\hat{\pi}$ sends homeomorphically
$\widehat{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ onto a connected component of
$\mathrm{dom}(I)$. Moreover, the frontier of this annulus is made of
contractible fixed points of $f$. In the second case, $\hat{\pi}$ sends
$\widehat{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ onto a hyperbolic surface
whose universal covering space is
$\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ and the group of covering
automorphisms is the stabilizer of
$\widetilde{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ in $\mathcal{G}$. In both
cases, there exists an extension
$\overline{\widehat{\mathrm{dom}}}(I)_{\tilde{\gamma}_{*}}$ of
$\widehat{\mathrm{dom}}(I)_{\tilde{\gamma}_{*}}$ obtained by blowing at least
one end $e$ with a circle $\hat{\Gamma}_{e}$ and $\hat{f}$ extends to a
homeomorphism $\overline{\hat{f}}$ of
$\overline{\widehat{\mathrm{dom}}}(I)_{\tilde{\gamma}_{*}}$ (see Paragraph
2.4). Furthermore, the rotation number(s) induced on the added circle(s) by
the lift of $\overline{\hat{f}}$ that extends $\tilde{f}$ are equal to $0$.

By Lemma 5.4, there exist positively recurrent points with rotation number
$a>0$ where $\mathrm{rot}_{f}(\nu)=a[T^{\prime}]$. Consequently, according to
Theorem 2.1 that can be applied thanks to Lemma 4.12, for every rational
number $p/q\in(0,a)$, written in an irreducible way, there exists a point
$\tilde{z}$ such that $\tilde{f}^{q}(\tilde{z})=T^{p}(\tilde{z})$. As
$\tilde{f}$ also has a fixed point by Lefschetz index theorem, this means that
$f$ has a homotopical interval of rotation of type $(\kappa,r)$ such that
$[\kappa]/r\in\mathcal{U}$. ∎

## References

  * [Ad] S. Addas Zanata: On properties of the vertical rotation interval for twist mappings. II.  Qual. Theory Dyn. Syst. 4 (2003), no. 2, 125–137.
  * [AdT] S. Addas-Zanata, F.A. Tal: On periodic points of area preserving torus homeomorphisms.  Far East J. Dyn. Syst. 9 (2007), no. 3, 371–378.
  * [At] G. Atkinson: Recurrence of co-cycles and random walks.  J. London Math. Soc. (2) 13 (1976), 486–488.
  * [BeCLer] F. Béguin, S. Crovisier, F. Le Roux: Fixed point sets of isotopies on surfaces.  J. Eur. Math. Soc. (JEMS) 22 (2020), no. 6, 197–2046.
  * [Bi] G.-D. Birkhoff: An extension of Poincaré’s last geometric theorem.  _Acta Math._ 47 (1926), no. 4 297–311.
  * [Br] L. E. J. Brouwer : Beweis des ebenen Translationssatzes,  Math. Ann., 72 (1912), 37-54.
  * [CPoPrZ] D. Cristofaro-Gardiner, D. Pomerleano, R. Prasad, B. Zhang A note in $U$-cyclic elements in monopole Floer homology,  arXiv 2110.13844v2 (2022).
  * [CPrZ] D. Cristofaro-Gardiner, R. Prasad, B. Zhang Periodic Floer homology and the smooth closing lemma for area-preserving surface diffeomorphisms,  arXiv 2110.02925 (2022).
  * [D] E. Doeff: Rotation measures for homeomorphisms of the torus homotopic to a Dehn twist.  Ergodic Theory Dynam. Systems 17 (1997), no. 3, 575–591.
  * [EH] O. Edtmair, M. Hutchings PFH spectral invariants and $C^{\infty}$-closing lemmas,  arXiv 2110.02463v4 (2022).
  * [F] J. Franks: Generalizations of the Poincaré-Birkhoff theorem.  Ann. of Math.(2) 128 (1988), no. 1, 139–151.
  * [FH] J. Franks, M. Handel: Periodic points of Hamiltonian surface diffeomorphisms.  Geometry and Topology 7 (2003), 713–756.
  * [G] V. Ginzburg: The Conley conjecture.  Annals of Math. (2) 172 (2010), no. 2, 1127–1180.
  * [H] M.-E. Hamstrom.  Homotopy groups of the space of homeomorphisms on a 2-manifold,  Illinois J. Math., 10 (1966), 563-573.
  * [J] O. Jaulent: Existence d’un feuilletage positivement transverse à un homéomorphisme de surface.  Ann. Inst. Fourier (Grenoble) 64 (2014), no. 4, 1441–1476.
  * [K] M. Kac: On the notion of recurrence in discrete stochastic processes  Bull. Amer. Math. Soc 53 (1947), no. 10, 1002–1010.
  * [Lec1] P. Le Calvez: Une version feuilletée équivariante du théorème de translation de Brouwer.  Publ. Math. Inst. Hautes Études Sci. 102, (2005) 1-98.
  * [Lec2] P. Le Calvez: Periodic orbits of Hamiltonian homeomorphisms of surfaces.  Duke Math. J.  133, (2006) no. 1, 125–184.
  * [Lec3] P. Le Calvez: Conservative surface homeomorphisms with finitely many periodic points.  J. Fixed Point Theory Appl. 24, (2022) no. 2, 36 pp.
  * [LecSa] P. Le Calvez, M. Sambarino: Homoclinic orbits for area preserving diffeomorphisms of surfaces.  Ergodic Theory Dynam. Systems 42, (2022), no. 3, 1122–1165.
  * [LecT1] P. Le Calvez, F. Tal: Forcing theory for transverse trajectories of surface homeomorphisms.  Invent. Math. 212, (2018), no. 2, 619–729.
  * [LecT2] P. Le Calvez, F. Tal: Topological horseshoes for surface homeomorphisms.  Duke Math. J. 171 (2022), no. 12, 2519–2626.
  * [Lel] G. Lellouch: Sur les ensembles de rotation des homéomorphismes de surface en genre $\geq 2$.  Mém. Soc. Math. Fr. (N.S), to appear.
  * [Math] J. Mather: Topological proofs of some purely topological consequences of Caratheodory’s Theory of prime ends. in Selected Studies, TH. M. Rassias, G. M. Rassias, eds,  North Holland, 168 (1982), 225-255.
  * [Mats1] S. Matsumoto: Rotation sets of surface homeomorphisms.  Bol. Soc. Brasil. Mat. (N.S.), 28 (1997), no. 1, 225–255.
  * [Mats2] S. Matsumoto: Arnold conjecture for surface homeomorphisms. Proceedings of the French-Japanese Conference ”Hyperspace Topologies and Applications” (La Bussière, 1997).  Topology Appl., 104 (2000), no. 1-3, 191–214.
  * [Ol1] F. Oliveira: On the generic existence of homoclinic points.  Ergodic Theory Dynam. Systems 7 (1987), no. 4, 567–595.
  * [Ol2] F. Oliveira: On the $C^{\infty}$ genericity of homoclinic orbits.  Nonlinearity  13 (2000), no. 3, 653–662.
  * [OxU] J. C. Oxtoby, S. M. Ulam Measure-preserving homeomorphisms and metrical transitivity. Ann. of Math. (2) 42 (1941), 874–920.
  * [PaPotSa] A. Passeggi, R. Potrie, M. Sambarino: Rotation intervals and entropy on attracting annular continua. Geom. Topol. 22 (2018), no. 4, 2145–2186.
  * [Pi] D. Pixton: Planar homoclinic point.  J. Differential Equations 44 (1982), no. 3, 365–382.
  * [Pol] M. Pollicott: Rotation sets for homeomorphisms and homology.  Trans. Amer. Math. Soc., 331 (1992), no. 2, 881-894.
  * [Pr] R. Prasad: Periodoc points of rational area-preserving homeomorphisms.  Manuscript, (2023).
  * [R] C. Robinson: Closing stable and unstable manifolds on the two sphere.  Proc. Amer. Math. Soc. 41 (1973), 299–303.
  * [Sc] S. Schwartzman: Asymptotic cycles.  Ann. of Math. 66 (1957), no. 2, 270–284.
  * [W] H. Weiss: A remark on papers by Pixton and Oliveira: Genericity of symplectic diffeomorphisms of $S^{2}$ with positive topological entropy.  J. Stat. Phys. 80 (1995), no. 1-2, 481–485.


Martin Aumüller, Erik Bernhardsson, Alexander Faithfull

# ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor
Algorithms111The research of the first and third authors has received funding
from the European Research Council under the European Union’s 7th Framework
Programme (FP7/2007-2013) / ERC grant agreement no. 614331. A conference
version of this work was published at SISAP’17 and is available at
http://dx.doi.org/10.1007/978-3-319-68474-1_3.

Martin Aumüller  IT University of Copenhagen, Denmark<EMAIL_ADDRESS>Erik Bernhardsson  Better Inc<EMAIL_ADDRESS>Alexander Faithfull  IT
University of Copenhagen, Denmark<EMAIL_ADDRESS>
###### Abstract.

This paper describes ANN-Benchmarks, a tool for evaluating the performance of
in-memory approximate nearest neighbor algorithms. It provides a standard
interface for measuring the performance and quality achieved by nearest
neighbor algorithms on different standard data sets. It supports several
different ways of integrating $k$-NN algorithms, and its configuration system
automatically tests a range of parameter settings for each algorithm.
Algorithms are compared with respect to many different (approximate) quality
measures, and adding more is easy and fast; the included plotting front-ends
can visualise these as images, LaTeX plots, and websites with interactive
plots. ANN-Benchmarks aims to provide a constantly updated overview of the
current state of the art of $k$-NN algorithms. In the short term, this
overview allows users to choose the correct $k$-NN algorithm and parameters
for their similarity search task; in the longer term, algorithm designers will
be able to use this overview to test and refine automatic parameter tuning.
The paper gives an overview of the system, evaluates the results of the
benchmark, and points out directions for future work. Interestingly, very
different approaches to $k$-NN search yield comparable quality-performance
trade-offs. The system is available at http://ann-benchmarks.com.

###### Key words and phrases:

benchmarking, nearest neighbor search, evaluation

###### 1991 Mathematics Subject Classification:

H.3.3 Information Search and Retrieval

##  1\. Introduction

Nearest neighbor search is one of the most fundamental tools in many areas of
computer science, such as image recognition, machine learning, and
computational linguistics. For example, one can use nearest neighbor search on
image descriptors such as MNIST [25] to recognize handwritten digits, or one
can find semantically similar phrases to a given phrase by applying the
word2vec embedding [31] and finding nearest neighbors. The latter can, for
example, be used to tag articles on a news website and recommend new articles
to readers that have shown an interest in a certain topic. In some cases, a
generic nearest neighbor search under a suitable distance or measure of
similarity offers surprising quality improvements [9].

In many applications, the data points are described by high-dimensional
vectors, usually ranging from 100 to 1000 dimensions. A phenomenon called the
_curse of dimensionality_ , a consequence of several popular algorithmic
hardness conjectures (see [4, 38]), tells us that, to obtain the true nearest
neighbors, we have to use either linear time (in the size of the dataset) or
time/space that is exponential in the dimensionality of the dataset. In the
case of _massive_ high-dimensional datasets, this rules out _efficient_ and
_exact_ nearest neighbor search algorithms.

To obtain efficient algorithms, research has focused on allowing the returned
neighbors to be an _approximation_ of the true nearest neighbors. Usually,
this means that the answer to finding the nearest neighbors to a query point
is judged by how _close_ (in some technical sense) the result set is to the
set of true nearest neighbors.

There exist many different algorithmic techniques for finding approximate
nearest neighbors. Classical algorithms such as $kd$-trees [6] or M-trees [11]
can simulate this by terminating the search early, for example shown by Zezula
et al. [39] for M-trees. Other techniques [28, 29] build a graph from the
dataset, where each vertex is associated with a data point, and a vertex is
adjacent to its true nearest neighbors in the data set. Others involve
projecting data points into a lower-dimensional space using hashing. A lot of
research has been conducted with respect to locality-sensitive hashing (LSH)
[18], but there exist many other techniques that rely on hashing for finding
nearest neighbors; see [36] for a survey on the topic. We note that, in the
realm of LSH-based techniques, algorithms guarantee sublinear query time, but
solve a problem that is only distantly related to finding the $k$ nearest
neighbors of a query point. In practice, this could mean that the algorithm
runs _slower_ than a linear scan through the data, and counter-measures have
to be taken to avoid this behavior [3, 34].

Given the difficulty of the problem of finding nearest neighbors in high-
dimensional spaces and the wide range of different solutions at hand, it is
natural to ask how these algorithms perform in empirical settings.
Fortunately, many of these techniques already have good implementations: see,
e.g., [32, 7, 27] for tree-based, [8, 13] for graph-based, and [5] for LSH-
based solutions. This means that a new (variant of an existing) algorithm can
show its worth by comparing itself to the many previous algorithms on a
collection of standard benchmark datasets with respect to a collection of
quality measures. What often happens, however, is that the evaluation of a new
implementation is based on a small set of competing algorithms and a small
number of selected datasets. This approach poses problems for everyone
involved:

  * (i)

_The implementation’s authors_ , because competing implementations might be
unavailable, they might use other conventions for input data and output of
results, or the original paper might omit certain required parameter settings
(and, even if these are available, exhaustive experimentation can take lots of
CPU time).

  * (ii)

_Their reviewers and readers_ , because experimental results are difficult to
reproduce and the selection of datasets and quality measures might appear
selective.

This paper proposes a way of standardizing benchmarking for nearest neighbor
search algorithms, taking into account their properties and quality measures.
Our benchmarking framework provides a unified approach to experimentation and
comparison with existing work. The framework has already been used for
experimental comparison in other papers [28] (to refer to parameter choice of
algorithms) and algorithms have been contributed by the community, e.g., by
the authors of NMSLib [8] and FALCONN [5]. An earlier version of our framework
is already widely used as a benchmark referred to from other websites, see,
e.g., [8, 5, 7, 27, 13].

Related work. Generating reproducible experimental results is one of the
greatest challenges in many areas of computer science, in particular in the
machine learning community. As an example, openml.org [35] and codalab.org
provide researchers with excellent platforms to share reproducible research
results.

The automatic benchmarking system developed in connection with the mlpack
machine learning library [12, 15] shares many characteristics with our
framework: it automates the process of running algorithms with preset
parameters on certain datasets, and can visualize these results. However, the
underlying approach is very different: it invokes whatever tools the
implementations provide and parses their standard output to extract result
metrics. Consequently, the system relies solely on the correctness of the
algorithms’ own implementations of quality measures, and adding a new quality
measure would require a change in _every single_ algorithm implementation.
Very recently, Li et al. [26] presented a comparison of many approximate
nearest neighbor algorithms, including many algorithms that are considered in
our framework as well. Their approach is to take existing algorithm
implementations and to heavily modify them to fit a common style of query
processing, in the process changing compiler flags (and sometimes even core
parts of the implementation). There is no general framework, and including new
features again requires manual changes in each single algorithm.

Our benchmarking framework does not aim to replace these tools; instead, it
complements them by taking a different approach. We only require that
algorithms expose a simple programmatic interface for building data structures
from training data and running queries. All the timing and quality measure
computation is conducted within our framework, which lets us add new metrics
without rerunning the algorithms, if the metric can be computed from the set
of returned elements. Moreover, we benchmark each implementation as intended
by the author. That means that we benchmark _implementations_ , rather than
_algorithmic ideas_ [22].

Contributions. We describe our system for benchmarking approximate nearest
neighbor algorithms with the general approach described in Section 3. The
system allows for easy experimentation with $k$-NN algorithms, and visualizes
algorithm runs in an approachable way. Moreover, in Section 4 we use our
benchmark suite to overview the performance and quality of current state-of-
the-art $k$-NN algorithms. This allows us to identify areas that already have
competitive algorithms, to compare different methodological approaches to
nearest neighbor search, but also to point out challenging datasets and
metrics, where good implementations are missing or do not take full advantage
of properties of the underlying metric. Having this overview has immediate
practical benefits, as users can select the right combination of algorithm and
parameters for their application. In the longer term, we expect that more
algorithms will become able to tune their own parameters according to the
user’s needs, and our benchmark suite will also serve as a testbed for this
automatic tuning.

##  2\. Problem Definition and Quality Measures

We assume that we want to find nearest neighbors in a space $X$ with a
distance measure $\text{dist}\colon X\times X\rightarrow\mathbb{R}$, for
example the $d$-dimensional Euclidean space $\mathbb{R}^{d}$ under Euclidean
distance ($l_{2}$ norm), or Hamming space $\\{0,1\\}^{d}$ under Hamming
distance.

An algorithm $\mathcal{A}$ for nearest neighbor search builds a data structure
DSA for a data set $S\subset X$ of $n$ points. In a preprocessing phase, it
creates DSA to support the following type of queries: For a query point $q\in
X$ and an integer $k$, return a _result tuple_
$\pi=(p_{1},\ldots,p_{k^{\prime}})$ of $k^{\prime}\leq k$ distinct points from
$S$ that are “close” to the query $q$. Nearest neighbor search algorithms
generate $\pi$ by refining a set $C\subseteq S$ of candidate points w.r.t. $q$
by choosing the $k$ closest points among those using distance computations.
The size of $C$ (and thus the number of distance computations) is denoted by
$N$. We let $\pi^{\ast}=(p^{\ast}_{1},\ldots,p^{\ast}_{k})$ denote the tuple
containing the true $k$ nearest neighbors for $q$ in $S$ (where ties are
broken arbitrarily). We assume in the following that all tuples are sorted
according to their distance to $q$.

###  2.1. Quality Measures

We use different notions of “recall” as a measure of the quality of the result
returned by the algorithm. Intuitively, recall is the ratio of the number of
points in the result tuple that are true nearest neighbors to the number $k$
of true nearest neighbors. However, this intuitive definition is fragile when
distances are not distinct or when we try to add a notion of approximation to
it. To avoid these issues, we use the following distance-based definitions of
recall and $(1+\varepsilon)$-approximative recall, that take the distance of
the $k$-th true nearest neighbor as threshold distance.

$\displaystyle\text{recall}(\pi,\pi^{\ast})$ $\displaystyle=\frac{|\\{p\text{
contained in
$\pi$}\mid\text{dist}(p,q)\leq\text{dist}(p^{\ast}_{k},q)\\}|}{k}$
$\displaystyle\text{recall}_{\varepsilon}(\pi,\pi^{\ast})$
$\displaystyle=\frac{|\\{p\text{ contained in
$\pi$}\mid\text{dist}(p,q)\leq(1+\varepsilon)\text{dist}(p^{\ast}_{k},q)\\}|}{k},\quad\text{for
$\varepsilon>0$.}$

(If all distances are distinct, $\text{recall}(\pi,\pi^{\ast})$ matches the
intuitive notion of recall.)

We note that (approximate) recall in high dimensions is sometimes criticised;
see, for example, [8, Section 2.1]. We investigate the impact of approximation
as part of the evaluation in Section 4, and plan to include other quality
measures such as position-related measures [39] in future work.

Name of Measure | Computation of Measure
---|---
Index size of DS | Size of DS after preprocessing finished (in kB)
Index build time DS | Time it took to build DS (in seconds)
Number of distance computations | $N$
Time of a query | Time it took to run the query and generate result tuple $\pi$
Table 1. Performance measures used in the framework.

###  2.2. Performance Measures

With regard to the performance, we use the performance measures defined in
Table 1, which are divided into measures of the performance of the
preprocessing step, i.e., generation of the data structure, and measures of
the performance of the query algorithm. With respect to the query performance,
different communities are interested in different cost values. Some rely on
actual timings of query times, where others rely on the number of distance
computations. The framework can take both of these measures into account.
However, none of the currently included algorithms report the number of
distance computations.

##  3\. System Design

ANN-Benchmarks is implemented as a Python framework with several different
front-ends: one script for running experiments and a handful of others for
working with and plotting results. It automatically downloads datasets when
they are needed and uses Docker build files to install algorithm
implementations and their dependencies.

This section gives only a high-level overview of the system; see http://ann-
benchmarks.com for more detailed technical information.

###  3.1. Algorithm implementations

Each implementation is installed via a Docker build file. These files specify
how an implementation should be installed on a standard Ubuntu system by
building and installing its dependencies and code. ANN-Benchmarks requires
that this installation process also build Python wrappers for the
implementation to give the framework access to it.

Adding support for a new algorithm implementation to ANN-Benchmarks is as easy
as writing a Docker file to install it and its dependencies, making it
available to Python by writing a wrapper (or by reusing an existing one), and
adding the parameters to be tested to the configuration files. Most of the
installation scripts fetch the latest version of their library from its Git
repository, but there is no requirement to do this; indeed, installing several
different versions of a library would make it possible to use the framework
for regression testing.

We emphasise at this point that we are explicitly comparing algorithm
_implementations_. Implementations make many different decisions that will
affect their performance and two implementations of the same algorithm can
have somewhat different performance characteristics [22]. When implementations
expose other quality measures – such as the number of distance computations,
which are more suited for comparing algorithms on a more abstract level – our
framework will also collect this information.

Local mode. Using Docker is ideal for evaluating the performance of well-tuned
implementations, but ANN-Benchmarks can also be used to help in the
_development_ process. To support this use case, the framework provides a
_local mode_ , which runs processes locally on the host system and not inside
a Docker container. This makes it much easier to build a pipeline solution to,
for example, automatically check how changes in the implementation influence
its performance – in the standard Docker setup, each change would require the
Docker container to be rebuilt.

Algorithm wrappers. To be usable by our system, each of the implementations to
be tested must have some kind of Python interface. Many libraries already
provide their own Python wrappers, either written by hand or automatically
generated using a tool like SWIG; others are implemented partly or entirely in
Python.

To bring implementations that do not provide a Python interface into the
framework, we specify a simple text-based protocol that supports the few
operations we care about: parameter configuration, sending training data, and
running queries. The framework comes with a wrapper that communicates with
external programs using this protocol. In this way, experiments can be run in
external front-end processes implemented in any programming language.

The protocol has been designed to be easy to implement. Every message is a
line of text that will be split into tokens according to the rules of the
POSIX shell, good implementations of which are available for most programming
languages. The protocol is flexible and extensible: front-ends are free to
include extra information in replies, and they can also implement special
configuration options that cause them to diverge from the protocol’s basic
behaviour. As an example, we provide a simple C implementation that supports
an alternative query mode in which parsing and preparing a query data point
and running a query are two different commands. (As the overhead of parsing a
string representation of a data point is introduced by the use of the
protocol, removing it makes the timings more representative.)

The use of a plaintext protocol necessarily adds some overhead, but this is
often not terribly significant – indeed, we have found that a naïve linear
search implemented in Java and invoked using the protocol is _faster_ than a
naïve Python implementation.

###  3.2. Datasets and ground truth

By default, the framework fetches datasets on demand from a remote server.
These dataset files contain, in HDF5 format, the set of data points, the set
of query points, the distance metric that should be used to compare them, a
list of the true nearest $k=100$ neighbours for each query point, and a list
of the distances of each of these neighbours from the query point.

The framework also includes a script for generating dataset files from the
original datasets. Although using the precomputed hosted versions is normally
simpler, the script can be used to, for example, build a dataset file with a
different value of $k$, or to convert a private dataset for the framework’s
use.

Most of the datasets use as their query set a pseudorandomly-selected set of
ten thousand entries separated from the rest of the training data; others have
separate query sets. The dataset file generation script makes this decision.

###  3.3. Creating algorithm instances

⬇

float

euclidean

megasrch

docker-tag ann-benchmarks-megasrch

module ann_benchmarks.algorithms.MEGASRCH

constructor MEGASRCH

base-args ["@metric"]

run-groups

shallow-point-lake

args ["lake", [100, 200]]

query-args [100, [100, 200, 400]]

deep-point-ocean

args ["sea", 1000]

query-args [[1000, 2000], [1000, 2000, 4000]]

Figure 1. An example of a fragment of an algorithm configuration file.

After loading the dataset, the framework moves on to creating the algorithm
instances. It does so based on a YAML configuration file that specifies a
hierarchy of dictionaries: the first level specifies the point type, the
second the distance metric, and the third each algorithm implementation to be
tested. Each implementation gives the name of its wrapper’s Python
constructor; a number of other entries are then expanded to give the arguments
to that constructor. Figure 1 shows an example of this configuration file.

The base-args list consists of those arguments that should be prepended to
every invocation of the constructor. Figure 1 also shows one of the special
keywords, "@metric", that is used to pass one of the framework’s configuration
parameters to the constructor.

Algorithms must specify one or more “run groups“, each of which will be
expanded into one or more lists of constructor arguments. The args entry
completes the argument list, but not directly: instead, the Cartesian product
of all of its entries is used to generate _many_ lists of arguments. Another
entry, query-args, is expanded in the same way as args, but each argument list
generated from it is used to reconfigure the query parameters of an algorithm
instance after its internal data structures have been built. This allows built
data structures to be reused, greatly reducing duplicated work.

As an example, the megasrch entry in Figure 1 expands into three different
algorithm instances: MEGASRCH("euclidean", "lake", 100), MEGASRCH("euclidean",
"lake", 200), and MEGASRCH("euclidean", "sea", 1000). Each of these will be
trained once and then used to run a number of experiments: the first two will
run experiments with each of the query parameter groups [100, 100], [100,
200], and [100, 400] in turn, while the last will run its experiments with the
query parameter groups [1000, 1000], [1000, 2000], [1000, 4000], [2000, 1000],
[2000, 2000], and [2000, 4000].

###  3.4. The experiment loop

Once the framework knows what instances should be run, it moves on to the
experiment loop, shown in Figure 2. The loop consists of two phases. In the
_preprocessing phase_ , an algorithm instance builds an index data structure
for the dataset $X$. The loop then transitions to the _query phase_ , in which
query points are sent one by one to the algorithm instance. For each query
point, the instance returns (at most) $k$ data points; after answering a
query, it can also report any extra information it might have, such as the
number of candidates considered, i.e., the number of exact distances computed.
The instance is then reconfigured with a new set of query parameters, and the
query set is run repeatedly, until no more sets of these parameters remain.

Each algorithm instance is run in an isolated Docker container. This makes it
easy to clean up after each run: simply terminating the container takes care
of everything. Moving experiments out of the main process also gives us a
simple and implementation-agnostic way of computing the memory usage of an
implementation: the subprocess records its total memory consumption before and
after initialising the algorithm instance’s data structures and compares the
two values.

Figure 2. Overview of the interaction between ANN-Benchmarks and an algorithm
instance under test.

The complete results of each run are written to the host by mounting part of
the file system into the Docker container. The main process performs a
blocking, timed wait on the container, and will terminate it if the user-
configurable timeout is exceeded before any results are available.

Dataset size. In its current form, ANN-Benchmarks supports benchmarking _in-
memory_ nearest-neighbor algorithms. In particular, the dataset is kept in
memory by ANN-Benchmarks when running experiments. This has to be taken into
account when choosing datasets to include into the framework. In practice,
this means that the framework can handle datasets with millions of points of
dimensionality up to a few thousand dimensions.

###  3.5. Multi-threading and batched queries

The experiment loop is, by default, run on a single CPU in a single thread.
The single-threaded mode is enforced when the Docker container is started,
using the Linux kernel’s cpusets capabilities to restrict access to the
system’s resources. Running on a single CPU makes the comparison between
implementations fairer, since all implementations run on the same grounds.

However, parallelizing single queries or using parallelism over queries is an
important topic. In fact, in many real-world systems that deploy nearest-
neighbor algorithms, queries can be batched together. This means that the data
structure receives a sequence of queries all at once, and returns results for
all of the queries contained in that sequence. This enables many interesting
approaches to parallelization that would not be possible when running single
queries.

ANN-Benchmarks supports these systems with a _batch mode_ , in which the whole
set of queries is given to the implementation wrapper at once. In this mode,
all resources of the host system are made available to the Docker container.
The behaviour of the experiment loop diverges slightly from Figure 2 in batch
mode. Batch queries do not return a sequence of tuples containing answers to
the individual queries; instead, these results are obtained via an additional
method, akin to Figure 2’s getAdditional() method. This allows an algorithm to
return the result of a batch query as an opaque internal data structure; this
will stop the clock, and the additional call can then transform that data
structure into Python objects without that transformation imposing a
performance penalty.

Batch query mode is particularly useful for running nearest-neighbor
algorithms on a GPU. In this context, transferring a single query point to the
GPU memory and getting the result of the query from the GPU can be a
dominating part of the query time, as we will see in Section 4.

###  3.6. Results and metrics

For each run, we store the full name – including the parameters – of the
algorithm instance, the time it took to build its index data structure, and
the results of every query: the near neighbours returned by the algorithm, the
time it took to find these, and their distances from the query point, along
with any additional information the implementation might have exposed. (To
avoid affecting the timing of algorithms that do not indicate the distance of
a result, the experiment loop independently re-computes distance values after
the query has otherwise finished.)

The results of each run are stored in a separate HDF5 file in a directory
hierarchy that encodes part of the framework’s configuration. Keeping runs in
separate files makes them easy to enumerate and easy to re-run, and individual
results – or sets of results – can easily be shared to make results more
transparent.

Metric functions are passed the ground truth and the results for a particular
run; they can then compute their result however they see fit. Adding a new
quality metric is a matter of writing a short Python function and adding it to
an internal data structure; the plotting scripts query this data structure and
will automatically support the new metric.

###  3.7. Frontend

ANN-Benchmarks provides two options to evaluate the results of the
experiments: a script to generate individual plots using Python’s matplotlib
and a script to generate a website that summarizes the results and provides
interactive plots with the option to export the plot as LaTeX code using
pgfplots. See Figure 3 for an example. Plots depict the Pareto frontier over
all runs of an algorithm; this gives an immediate impression of the
algorithm’s general characteristics, at the cost of concealing some of the
detail. When more detail is desired, the scripts can also produce scatter
plots.

As batch mode goes to greater lengths to reduce overhead than the normal query
mode and exposes more of the system’s resources to the implementation being
tested, results obtained in batch mode are always presented separately by the
evaluation scripts to make the comparisons fairer.

Figure 3. Interactive plot screen from framework’s website (cropped). Plot
shows “Queries per second” ($y$-axis, log-scaled) against “Recall” ($x$-axis,
not shown). Highlighted data point corresponds to a run of Annoy with
parameters as depicted, giving about 1249 queries per second for a recall of
about $0.52$.

##  4\. Evaluation

In this section we present a short evaluation of our findings from running
benchmarks in the benchmarking framework. After discussing the evaluated
implementations and datasets, we will present four questions that we intended
to answer using the framework. Subsequently, we will discuss the answers to
these questions and present some observations regarding the build time of
indexes and their ability to answer batched queries. At the end of this
section, we present a summary of our findings.

Principle | Algorithms
---|---
$k$-NN graph |  KGraph (KG) [13], SWGraph (SWG) [29, 8], HNSW [28, 8], PyNNDescent (NND) [30], PANNG [2, 19]
tree-based |  FLANN [32], BallTree (BT) [8], Annoy (A) [7], RPForest (RPF) [27], MRPT [17, 1]
LSH |  FALCONN (FAL) [5], MPLSH [14, 8]
other |  Multi-Index Hashing (MIH) [33] (exact Hamming search),
|  FAISS-IVF (FAI) [20] (inverted file)
Table 2. Overview of tested algorithms (abbr. in parentheses). Implementations in italics have “recall” as quality measure provided as an input parameter. Dataset | Data/Query Points | Dimensionality | Metric
---|---|---|---
SIFT | 1 000 000 / 10 000 | 128 | Euclidean
GIST | 1 000 000 / 10 000 | 960 | Euclidean
GLOVE | 1 183 514 / 10 000 | 100 | Angular/Cosine
NYTimes | 234 791 / 10 000 | 256 | Euclidean
Rand-Euclidean | 1 000 000 / 10 000 | 128 | Angular/Cosine
SIFT-Hamming | 1 000 000 / 1 000 | 256 | Hamming
Word2Bits | 399 000 / 1 000 | 800 | Hamming
Table 3. Datasets under consideration.

Experimental setup. All experiments were run in Docker containers on _Amazon
EC2_ _c5.4xlarge_ instances that are equipped with Intel Xeon Platinum 8124M
CPU (16 cores available, 3.00 GHz, 25.0MB Cache) and 32GB of RAM running
Amazon Linux. We ran a single experiment multiple times to verify that
performance was reliable, and compared the experiments results with a 4-core
Intel Core i7-4790 clocked at 3.6 GHz with 32GB RAM. While the latter was a
little faster, the relative order of algorithms remained stable. For each
parameter setting and dataset, the algorithm was given five hours to build the
index and answer the queries.

Tested Algorithms. Table 2 summarizes the algorithms that are used in the
evaluation; see the references provided for details. The framework has support
for more implementations and many of these were included in the experiments,
but they turned out to be either non-competitive or too similar to other
implementations.222For example, the framework contains three different
implementations of HNSW: the original one from NMSlib, a standalone variant
inspired by that one, and an implementation in FAISS that is again inspired by
the implementation in NMSlib. The first two implementations perform almost
indistinguishably, while the implementation provided in FAISS was a bit
slower. For the sake of brevity, we also omit the two random projection
forest-based methods RPForest and MRPT since they were always slower than
Annoy.  The scripts that set up the framework automatically fetch the most
current version found in each algorithm’s repository.

In general, the implementations under evaluation can be separated into three
main algorithmic principles: graph-based, tree-based, and hashing-based
algorithms. _Graph-based algorithms_ build a graph in which vertices are the
points in the dataset and edges connect vertices that are true nearest
neighbors of each other, forming the so-called $k$-NN graph. Given the query
point, close neighbors are found by traversing the graph in a greedy fashion,
subject to the actual implementation [13, 29, 28, 30, 19]. _Tree-based
algorithms_ use a collection of trees as their data structure. In these trees,
each node splits the dataset into subsets that are then processed in the
children of the node. If the dataset associated with a node is small enough,
it is directly stored in the node which is then a leaf in the tree. For
example, Annoy [7] and RPForest [27] choose in each node a random hyperplane
to split the dataset. Given the query point, the collection of trees are
traversed to obtain a set of candidate points from which the closest to the
query are returned. _Hashing-based algorithms_ apply hash functions such as
locality-sensitive hashing [18] to map data points to hash values. At query
time, the query point is hashed and keys colliding with it, or not too far
from it using the multi-probe approach [14], are retrieved. Among them, those
closest to the query point are returned. Different implementations are mainly
characterized by the underlying locality-sensitive hash function that is being
used.

Datasets. The datasets used in this evaluation are summarized in Table 3. More
informations on these datasets and results for other datasets are found on the
framework’s website. The NYTimes dataset was generated by building tf-idf
descriptors from the bag-of-words version, and embedding them into a lower
dimensional space using the Johnson-Lindenstrauss Transform [21]. The Hamming
space version of SIFT was generated by applying Spherical Hashing [16] using
the implementation provided by the authors of [16]. The dataset Word2Bits
comes from the quantized word vector approach described in [24] using the
top-400 000 words in the English Wikipedia from 2017.

The dataset Rand-Euclidean is generated as follows: Assume that we want to
generate a dataset with $n$ data points, $n^{\prime}$ query points, and are
interested in finding the $k$ nearest neighbors for each query point. For an
even dimension $d$, we generate $n-k\cdot n^{\prime}$ data points of the form
$(v,\mathbf{0})$, where $v$ is a random unit length vector of dimension $d/2$,
and $\mathbf{0}$ is the vector containing $d/2$ $0$ entries. We call the first
$d/2$ components the _first part_ and the following $d/2$ components the
_second part_ of the vector. From these points, we randomly pick $n^{\prime}$
points $(v_{1},\ldots,v_{n^{\prime}})$. For each point $v_{i}$, we replace its
second part with a random vector of length $1/\sqrt{2}$. The resulting point
is the query point $q_{i}$. For each $q_{i}$, we insert $k$ random points at
varying distance increasing from $0.1$ to $0.5$ to $q_{i}$ into the original
dataset. The idea behind such a dataset is that the vast majority of the
dataset looks like a random dataset with little structure for the algorithm to
exploit, while each query point has $k$ neighbors that are with high
probability well separated from the rest of the data points. This means that
the queries are easy to answer locally, but they should be difficult to answer
if the algorithm wants to exploit a global structure.

Parameters of Algorithms. Most algorithms do not allow the user to explicitly
specify a quality target—in fact, only three implementations from Table 2
provide “recall” as an input parameter. We used our framework to test many
parameter settings at once. The detailed settings tested for each algorithm
can be found on the framework’s website.

Status of FALCONN. While preparing this full version, we noticed that
FALCONN’s performance has drastically decreased in the latest versions. We
communicated this to the authors of [5], who are now working on a fix;
however, they asked us to disregard FALCONN for this submission. We plan to
include it in a revised version.

###  4.1. Objectives of the Experiments

We used the benchmarking framework to find answers to the following questions:

(Q1) Performance. Given a dataset, a quality measure and a number $k$ of
nearest neighbors to return, how do algorithms compare to each other with
respect to different performance measures, such as query time or index size?
(Q2) Robustness. Given an algorithm $\mathcal{A}$, how is its performance and
result quality influenced by the dataset and the number of returned neighbors?
(Q3) Approximation. Given a dataset, a number $k$ of nearest neighbors to
return, and an algorithm $\mathcal{A}$, how does its performance improve when
the returned neighbors can be an approximation? Is the effect comparable for
different algorithms?
(Q4) Embeddings. Equipped with a framework with many different datasets and
distance metrics, we can try interesting combinations. How do algorithms
targeting Euclidean space or Cosine similarity perform in, say, Hamming space?
How does replacing the internals of an algorithm with Hamming space related
techniques improve its performance?

The following discussion is based on a combination of the plots found on the
framework’s website; see the website for more complete and up-to-date results.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$ABTFAI-IVFFLANNHNSWKGPANNGNND
SWG$0$$0.25$$0.5$$0.75$$1$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$RecallQPS
(1/s)$0$$0.25$$0.5$$0.75$$1$Recall Figure 4. Recall-QPS (1/s) tradeoff - up
and to the right is better. Top: GLOVE, bottom: SIFT; left: $10$-NN, right:
$100$-NN.

###  4.2. Discussion

(Q1) Performance. Figure 4 shows the relationship between an algorithm’s
achieved recall and the number of queries it can answer per second (its QPS)
on the two datasets GLOVE (Cosine similarity) and SIFT (Euclidean distance)
for $10$\- and $100$-nearest neighbor queries.

For GLOVE, we observe that the graph-based algorithms clearly outperform the
tree-based approaches. It is noteworthy that all implementations, except
FLANN, achieve close to perfect recall. Over all recall values, HNSW is
fastest. However, at high recall values it is closely matched by KGraph.
FAISS-IVF comes in at third place, only losing to the other graph-based
approaches at very high recall values. For 100 nearest neighbors, the picture
is very similar. We note, however, that the graph-based indexes were not able
to build indexes for nearly perfect recall values within 5 hours.

On SIFT, all tested algorithms can achieve close to perfect recall. Again, the
graph-based algorithms are fastest; they are followed by Annoy and FAISS-IVF.
FLANN and BallTree are at the end. In particular, FLANN was not able to finish
its auto-tuning for high recall values within 5 hours.

Very few of these algorithms can tune themselves to produce a particular
recall value. In particular, almost all of the fastest algorithms on the GLOVE
dataset expose many parameters, leaving the user to find the combination that
works best. The KGraph algorithm, on the other hand, uses only a single
parameter, which—even in its “smallest” choice—still gives high recall on
GLOVE and SIFT. FLANN manages to tune itself for a particular recall value
well. However, at high recall values, the tuning does not complete within the
time limit, especially with 100-NN.

$0$$0.25$$0.5$$0.75$$1$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$RecallIndex
size/QPS$0$$0.25$$0.5$$0.75$$1$RecallABTFAI-IVFFLANNHNSWKGPANNGNNDSWG Figure
5. Recall-Index size (kB)/QPS (s) tradeoff - down and to the right is better.
Left: SIFT ($k$=100), right: GLOVE ($k$=10).

Figure 5 relates an algorithm’s performance to its index size. (Note that here
down and to the right is better.) High recall can be achieved with small
indexes by probing many points; however, this probing is expensive, and so the
QPS drops dramatically. To reflect this performance cost, we scale the size of
the index by the QPS it achieves for a particular run. This reveals that, on
SIFT, most implementations perform similarly under this metric. HNSW is best
(due to the QPS it achieves), but most of the other algorithm achieve similar
cost. In particular, FAISS-IVF and FLANN do well. NND, Annoy, and BallTree
achieve their QPS at the cost of relatively large indexes, reflected in a
rather large gap between them and their competition. On GLOVE, we see a much
wider spread of index size performance. Here, FAISS-IVF and HNSW perform
nearly indistinguishably. Next follow the other graph-based algorithms, with
FLANN among them. Again, Annoy and BallTree perform worst in this measure.

(Q2) Robustness. Figure 7 plots recall against QPS on the dataset Rand-
Euclidean. Recall from our earlier discussion of datasets that this dataset
contains easy queries, but requires an algorithm to exploit the local
structure instead of some global structure of the data structure, cf.
Datasets. We see very different behavior than before: there is a large
difference between different graph-based approaches. While PANNG, KGraph, NND
can solve the task easily with high QPS, both HNSW and SWG fail in this task.
This means that the “small-world” structure of these two methods _hurts_
performance on such a dataset. In particular, no tested parameter setting for
HNSW achives recall beyond .86. Annoy performs best at exploiting the local
structure of the dataset and is the fastest algorithm. The dataset is also
easy for FAISS-IVF, which also has very good performance.

Let us turn our focus to how the algorithms perform on a wide variety of
datasets. Figure 7 plots recall against QPS for Annoy, FAISS-IVF, and HNSW
over a range of datasets. Interestingly, implementations agree on the
“difficulty” of a dataset most of the time, i.e., the relative order of
performance is the same among the algorithms. Notable exceptions are Rand-
Euclidean, which is very easy for Annoy and FAISS-IVF, but difficult for HNSW
(see above), and NYTimes, where FAISS-IVF fails to achieve recall above .7 for
the tested parameter settings. Although all algorithms take a performance hit
for high recall values, HNSW is least affected. On the other hand, HNSW shows
the biggest slowdown in answering 100-NN compared to 10-NN queries among the
different algorithms.

$0.25$$0.5$$0.75$$1$$10^{2}$$10^{3}$$10^{4}$QPS (1/s)AFAI-
IVFHNSWPANNGNNDKGraphSWG

Figure 6. Recall-QPS (1/s) tradeoff - up and to the right is better; Rand-
Euclidean with 10-NN.

$0$$0.25$$0.5$$0.75$$1$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$RecallQPS
(1/s)$0.25$$0.5$$0.75$$1$Recall$0$$0.25$$0.5$$0.75$$1$RecallGISTGLOVEGLOVE (k
= 100)NYTimesRand-EuclideanSIFT

Figure 7. 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.
$0$$0.25$$0.5$$0.75$$1$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$RecallQPS
(1/s)$0$$0.25$$0.5$$0.75$$1$Recall$0$$0.25$$0.5$$0.75$$1$RecallAFAI-
IVFHNSWMRPTNNDSWG Figure 8. (Approximate) Recall-QPS (1/s) tradeoff - up and
to the right is better, GIST dataset, 100-NN; left: $\varepsilon=0$, middle:
$\varepsilon=0.01$, right: $\varepsilon=0.1$.
$0$$0.25$$0.5$$0.75$$1$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$RecallQPS
(1/s)AA (Ham.)FAI-IVFPANNGMIHA
(Eucl.)$0$$0.25$$0.5$$0.75$$1$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$Recall
Figure 9. Recall-QPS (1/s) tradeoff - up and to the right is better,
10-nearest neighbors, left: SIFT-Hamming, right: Word2bits. The following
versions of Annoy are shown in the plot: A, standard Annoy that uses Euclidean
distance as its distance metric; A (Ham.), Annoy with node splitting inspired
by Bitsampling LSH and tuned to Hamming space; and A (Eucl.), the run of Annoy
on SIFT from Figure 4 (bottom left).

(Q3) Approximation. Figure 8 relates achieved QPS to the (approximate) recall
of an algorithm. The plots show results on the GIST dataset with 100-NN for
recall with no approximation and approximation factors of $1.01$ and $1.1$,
respectively. Despite its high dimensionality, all considered algorithms
achieve close to perfect recall (left). For an approximation factor of $1.01$,
i.e., distances to true nearest neighbors are allowed to differ by $1\%$, all
curves move to the right, as expected. Also, the relative difference between
the performance of algorithms does not change. However, we see a clear
difference between the candidate sets that are returned by algorithms at low
recall. For example, the data point for MRPT around .5 recall on the left
achieves roughly .6 recall as a $1.01$ approximation, which means that roughly
10 new candidates are considered true approximate nearest neighbors. On the
other hand, HSNW, FAISS-IVF, and Annoy improve by around 25 candidates being
counted as approximate nearest neighbors. We see that allowing a slack of
$10\%$ in the distance renders the queries too simple: almost all algorithms
achieve near-perfect recall for all of their parameter choices. Interestingly,
Annoy becomes the second-fastest algorithm for $1.1$ approximation. This means
that its candidates at very low recall values were a bit better than the ones
obtained by its competitors.

(Q4) Embeddings. Figure 9 shows a comparison between selected algorithms on
the binary version of SIFT and a version of the Wikipedia dataset generated by
Word2Bits, which is an embedding of word2vec vectors [31] into binary vectors.
The performance plot for Annoy in the original Euclidean-space version of SIFT
is also shown.

On SIFT, algorithms perform much faster in the embedded Hamming space version
compared to the original Euclidean-space version (see Figure 4), which
indicates that the queries are easier to answer in the embedded space. (Note
here that the dimensionality is actually twice as large.) Multi-index hashing
[33], an exact algorithm for Hamming space, shows good performance on SIFT
with around 460 QPS.

We created a Hamming space-aware version of Annoy, using popcount for distance
computations, and sampling single bits (as in Bitsampling LSH [18]) instead of
choosing hyperplanes. This version is two to three times faster on SIFT until
high recall, where the Hamming space version and the Euclidean space version
converge in running time. On the 800-dimensional Word2Bits dataset the
opposite is true and the original version of Annoy is faster than the
dedicated Hamming space approach. This means that the original data-dependent
node splitting in Annoy adapts better to the query structure than the node
splitting by data-independent Bitsampling for this dataset. The dataset seems
to be hard in general: MIH achieves only around 20 QPS on Word2Bits. We remark
that setting the parameters for MIH correctly is crucial; even though the
recall will always be 1, different parameter settings can give wildly
different QPS values.

The embedding into Hamming space does have some consistent benefits that we do
not show here. Hamming space-aware algorithms should always have smaller index
sizes, for example, due to the compactness of bit vectors.

###  4.3. Index build time remarks

Figure 10 compares different implementations with respect to the time it takes
to build the index. We see a huge difference in the index building time among
implementations, ranging from FAISS-IVF (around 2 seconds to build the index)
to HNSW (almost 5 hours). In general, building the nearest neighbor graph and
building a tree data structure takes considerably longer than the inverted
file approach taken by FAISS-IVF. Shorter build times make it much quicker to
search for the best parameter choices for a dataset. Although all indexes
achieve recall of at least 0.9, we did not normalize by the queries per second
as in Figure 5. For example, HNSW also achieves its highest QPS with these
indexes, but FAISS needs a larger index to achieve the performance from Figure
4 (which takes around 13 seconds to build). As an aside, building an HNSW
index using the implementation provided in FAISS made it possible to build an
index that achieved recall .9 in only 1 700 seconds.

FAISS-IVFANNOYBALLTREEPyNNDescentPANNGSW-GraphHNSW(FAISS)RP-
ForestFLANNKGraphHNSW(NMSlib)$0$$0.5$$1$$1.5$$\cdot
10^{4}$$2.2$$262$$287$$765$$802$$1{,}404$$1{,}700$$2{,}667$$5{,}032$$7{,}189$$17{,}000$Build
time (s) Figure 10. Index build time in seconds for dataset GLOVE. The plot
shows the minimum build time for an index that achieved recall of at least 0.9
for 10-NN.

###  4.4. Batched Queries

We turn our focus to batched queries. In this setting, each algorithm is given
the whole set of query points at once and has to return closest neighbors for
each point. This allows for several optimizations: in a GPU setting, for
example, copying query points to, and results from, the GPU’s memory is
expensive, and being able to copy everything at once drastically reduces this
overhead.

The following experiments have been carried out on an Intel Xeon CPU E5-1650
v3 @ 3.50GHz with 6 physical cores, 15MB L3 Cache, 64 GB RAM, and equipped
with an NVIDIA Titan XP GPU.

$0$$0.25$$0.5$$0.75$$1$$10^{3}$$10^{4}$$10^{5}$$10^{6}$QPS (1/s)FAI-IVF-GPU
FAI-GPU-BF FAI-IVF-CPUHNSW (B)HNSW (NB) Figure 11. Recall-QPS (1/s) tradeoff -
up and to the right is better. Algorithms running batched queries on SIFT with
$10$-NN. The plot shows a comparison between FAISS’ IVF index running on a CPU
and a GPU, FAISS’ brute force index on the GPU, and HNSW from NMSlib running
in batched (B) and non-batched mode (NB).

Figure 11 reports on our results with regard to algorithms in batch mode.
FAISS’ inverted file index on the GPU is by far the fastest index, answering
around 655 000 queries per second for .7 recall, and 61 000 queries per second
for recall .99. It is around 20 to 30 times faster than the respective data
structure running on the CPU. Comparing HNSW’s performance with batched
queries against non-batched queries shows a speedup by a factor of roughly 3
at .5 recall, and a factor of nearly 5 at recall .99 in favor of batched
queries. Attention should also be put on the fact that the brute force variant
of FAISS on the GPU answers around 24 000 queries per second.

###  4.5. Summary

Which method to choose? From the evaluation, we see that graph-based
algorithms provide by far the best performance on most of the datasets. HNSW
is often the fastest algorithm, but PANNG is more robust if there is no global
structure in the dataset. The downside of graph-based approaches is the high
preprocessing time needed to build their data structures. This could mean that
they might not be the preferred choice if the dataset changes regularly. When
it comes to small and quick-to-build index data structures, FAISS’ inverted
file index provides a suitable choice that still gives good performance in
answering queries.

How well do these results generalize? In our experiments, we observed that,
for the standard datasets under consideration, algorithms usually agree on

  * (i)

the order in how well they perform on datasets, i.e., if algorithm A answers
queries on dataset X faster than on dataset Y, then so will algorithm B; and

  * (ii)

their relative order to each other, i.e., if algorithm A is faster than B on
dataset X, this will most likely be the order for dataset Y.

There exist exceptions from this rule, e.g., for the dataset Rand-Euclidean
described above.

How robust are parameter choices? With very few exceptions (see Table 2),
users often have to set many parameters themselves. Of course, our framework
allows them to choose the best parameter choice by exploring the interactive
plots that contain the parameter choices that achieve certain quality
guarantees.

In general, the _build parameters_ can be used to estimate the size of the
index333As an example, the developers of FAISS provide a detailed description
of the space usage of their indexes at
https://github.com/facebookresearch/faiss/wiki/Faiss-indexes., while the
_query parameters_ suggest the amount of effort that is put into searching the
index.

We will concentrate for a moment on Figure 12. This figure presents a scatter
plot of selected algorithms for GLOVE on 10-NN, cf. the Pareto curve in Figure
4 (in the top left). Each algorithm has a very distinctive parameter space
plot.

For HNSW, almost all data points lie on the Pareto curve. This means that the
different build parameters blend seamlessly into each other. For Annoy, we see
that data points are grouped into clusters of three points each, which
represent exactly the three different index choices that are built by the
algorithm. For low recall, there is a big performance penalty for choosing a
too large index; at high recall, the different build parameters blend almost
into each other. For SW-Graph, we see two groups of data points, representing
two different index choices. We see that with the index choice to the left,
only very low recall is achieved on the dataset. Extrapolating from the curve,
choosing query parameters that would explore a large part of the index will
probably lead to low QPS. No clear picture is visible for FAISS-IVF from the
plot. This is chiefly because we test many different build parameters – recall
that the index building time is very low. Each build parameter has its very
own curve with respect to the different query parameters.

As a rule of thumb, when aiming for high recall values, a larger index
performs better than a smaller index and is more robust to the choice of query
parameters.

$0$$0.25$$0.5$$0.75$$1$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$QPS (1/s)A FAI-
IVF HNSWSWG  Figure 12. Scatter plot of Recall-QPS (1/s) tradeoff - up and to
the right is better on GLOVE with 10-NN.

##  5\. Conclusion & Further Work

We introduced ANN-Benchmarks, an automated benchmarking system for approximate
nearest-neighbor algorithms. We described the system and used it to evaluate
existing algorithms. Our evaluation showed that well-enginereed solutions for
Euclidean and Cosine distance exist, and many techniques allow for fast
nearest-neighbor search algorithms. At the moment, graph-based approaches such
as HNSW or KGraph outperform the other approaches for very high recalls,
except for on very few datasets. Index building for graph-based approaches
takes a long time for datasets with difficult queries.

In future, we aim to add support for other metrics and quality measures, such
as positional errors [39]. Preliminary support exists for set similarity under
Jaccard distance, but algorithm implementations are missing. Additionally,
similarity joins are an interesting variation of the problem worth
benchmarking [10]. We remark that the data we store with each algorithm run
allows for more analysis beyond looking at average query times. One could, for
example, already look at the variance of running times between algorithms,
which could yield insights when comparing different approaches. We also intend
to simplify and further automate the process of re-running benchmarks when new
versions of algorithm implementations appear.

As a general direction for future work, we remark that none of the most
performant implementations are easy to use. From a user perspective, the
internal parameters of the data structure would ideally be invisible; an
algorithm should be able to tune itself for the dataset at hand, given just a
handful of quality-related parameters (such as the desired recall or the index
size).

In the future, we plan to include a benchmarking mode for investigating this.
A new tuning step will be added to the framework, letting implementations
examine a small part of the dataset and to tune themselves for some given
quality parameters before training begins. Implementors of algorithms would be
able to test their auto-tuning techniques easily with such a benchmarking
mode.

Another general direction for future work is to get a better understanding
which properties of a dataset make it easy or difficult for a specific
algorithm. As shown in the evaluation, for many of the real-world datasets we
get a homogeneous picture of how well algorithms perform against each other.
On the other hand, we have given an example for a random dataset where
implementations behave very differently. Which properties of a dataset make it
simple or difficult for a specific algorithmic approach? For example, for
graph-based algorithms there has been very little research except [23] on the
theoretical guarantees that they achieve.

Finally, answering batched queries, in particular on the GPU, is an
interesting area for future work. There exist both novel LSH-based
implementations [37] of nearest-neighbor algorithms and ideas on how to
parallelize queries beyond running each query individually [10]. In
particular, for a batch of queries an algorithm should exploit that individual
queries might be close to each other.

Acknowledgements: We thank the anonymous reviewers for their careful comments
that allowed us to improve the paper. The first and third authors thank all
members of the algorithm group at the IT University of Copenhagen for fruitful
discussions. In particular, we thank Rasmus Pagh for the suggestion of the
random dataset. This work was supported by a GPU donation from NVIDIA.

## References

  * [1] MRPT - fast nearest neighbor search with random projection, https://github.com/teemupitkanen/mrpt
  * [2] NGT: PANNG, https://github.com/yahoojapan/NGT
  * [3] Ahle, T.D., Aumüller, M., Pagh, R.: Parameter-free locality sensitive hashing for spherical range reporting. In: SODA’17. pp. 239–256
  * [4] Alman, J., Williams, R.: Probabilistic polynomials and hamming nearest neighbors. In: FOCS’15. pp. 136–150
  * [5] Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I.P., Schmidt, L.: Practical and optimal LSH for angular distance. In: NIPS’15. pp. 1225–1233. https://falconn-lib.org/
  * [6] Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)
  * [7] Bernhardsson, E.: Annoy, https://github.com/spotify/annoy
  * [8] Boytsov, L., Naidan, B.: Engineering efficient and effective non-metric space library. In: SISAP’13. pp. 280–293
  * [9] Boytsov, L., Novak, D., Malkov, Y., Nyberg, E.: Off the beaten path: Let’s replace term-based retrieval with k-nn search. In: CIKM’16. pp. 1099–1108
  * [10] Christiani, T., Pagh, R., Sivertsen, J.: Scalable and robust set similarity join. In: ICDE’2018 (2018)
  * [11] Ciaccia, P., Patella, M., Zezula, P.: M-tree: An efficient access method for similarity search in metric spaces. In: VLDB’97. pp. 426–435 (1997)
  * [12] Curtin, R.R., Cline, J.R., Slagle, N.P., March, W.B., Ram, P., Mehta, N.A., Gray, A.G.: MLPACK: A scalable C++ machine learning library. Journal of Machine Learning Research 14, 801–805 (2013)
  * [13] Dong, W.: KGraph, https://github.com/aaalgo/kgraph
  * [14] Dong, W., Wang, Z., Josephson, W., Charikar, M., Li, K.: Modeling LSH for performance tuning. In: CIKM’08. pp. 669–678. ACM, http://lshkit.sourceforge.net/
  * [15] Edel, M., Soni, A., Curtin, R.R.: An automatic benchmarking system. In: NIPS 2014 Workshop on Software Engineering for Machine Learning (2014)
  * [16] Heo, J.P., Lee, Y., He, J., Chang, S.F., Yoon, S.E.: Spherical hashing: Binary code embedding with hyperspheres. IEEE TPAMI 37(11), 2304–2316 (2015)
  * [17] Hyvönen, V., Pitkänen, T., Tasoulis, S., Jääsaari, E., Tuomainen, R., Wang, L., Corander, J., Roos, T.: Fast nearest neighbor search through sparse random projections and voting. In: Big Data (Big Data), 2016 IEEE International Conference on. pp. 881–888. IEEE (2016)
  * [18] Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC’98. pp. 604–613
  * [19] Iwasaki, M.: Pruned bi-directed k-nearest neighbor graph for proximity search. In: SISAP 2016. pp. 20–33 (2016), https://doi.org/10.1007/978-3-319-46759-7_2
  * [20] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with gpus. CoRR abs/1702.08734 (2017)
  * [21] Johnson, W.B., Lindenstrauss, J., Schechtman, G.: Extensions of lipschitz maps into banach spaces. Israel Journal of Mathematics 54(2), 129–138 (1986)
  * [22] Kriegel, H., Schubert, E., Zimek, A.: The (black) art of runtime evaluation: Are we comparing algorithms or implementations? Knowl. Inf. Syst. 52(2), 341–378 (2017)
  * [23] Laarhoven, T.: Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors. In: Speckmann, B., Tóth, C.D. (eds.) 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 99, pp. 57:1–57:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018), http://drops.dagstuhl.de/opus/volltexte/2018/8770
  * [24] Lam, M.: Word2bits - quantized word vectors. CoRR abs/1803.05651 (2018), http://arxiv.org/abs/1803.05651
  * [25] LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proceedings of the IEEE 86(11), 2278–2324 (1998)
  * [26] Li, W., Zhang, Y., Sun, Y., Wang, W., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data - experiments, analyses, and improvement (v1.0). CoRR abs/1610.02455 (2016), http://arxiv.org/abs/1610.02455
  * [27] Lyst Engineering: Rpforest, https://github.com/lyst/rpforest
  * [28] Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. ArXiv e-prints (Mar 2016)
  * [29] Malkov, Y., Ponomarenko, A., Logvinov, A., Krylov, V.: Approximate nearest neighbor algorithm based on navigable small world graphs. Inf. Syst. 45, 61–68 (2014)
  * [30] McInnes, L.: PyNNDescent, https://github.com/lmcinnes/pynndescent
  * [31] Mikolov, T., Sutskever, I., Chen, K., Corrado, G.S., Dean, J.: Distributed representations of words and phrases and their compositionality. In: NIPS’13. pp. 3111–3119
  * [32] Muja, M., Lowe, D.G.: Fast approximate nearest neighbors with automatic algorithm configuration. In: VISSAPP’09. pp. 331–340. INSTICC Press
  * [33] Norouzi, M., Punjani, A., Fleet, D.J.: Fast search in hamming space with multi-index hashing. In: CVPR’12. pp. 3108–3115. IEEE
  * [34] Pham, N.: Hybrid LSH: faster near neighbors reporting in high-dimensional space. In: EDBT’17. pp. 454–457
  * [35] Van Rijn, J.N., Bischl, B., Torgo, L., Gao, B., Umaashankar, V., Fischer, S., Winter, P., Wiswedel, B., Berthold, M.R., Vanschoren, J.: Openml: A collaborative science platform. In: ECML PKDD. pp. 645–649. Springer (2013)
  * [36] Wang, J., Shen, H.T., Song, J., Ji, J.: Hashing for similarity search: A survey. CoRR abs/1408.2927 (2014), http://arxiv.org/abs/1408.2927
  * [37] Wang, Y., Shrivastava, A., Wang, J., Ryu, J.: Randomized algorithms accelerated over CPU-GPU for ultra-high dimensional similarity search. In: SIGMOD. pp. 889–903 (2018), http://doi.acm.org/10.1145/3183713.3196925
  * [38] Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2-3), 357–365 (2005)
  * [39] Zezula, P., Savino, P., Amato, G., Rabitti, F.: Approximate similarity retrieval with M-Trees. VLDB J. 7(4), 275–293 (1998)