1

2

3

The Role of Local Dimensionality Measures in
Benchmarking Nearest Neighbor SearchMartin Aumüller

5

IT University of Copenhagen, Denmark
maau@itu.dk

6

Matteo Ceccarello

47
8Free University of Bozen-Bolzano, Italy
matteo.ceccarello@unibz.it

Abstract

9
10
11
12
13
14
15
16
17
18
19

This paper reconsiders common benchmarking approaches to nearest neighbor search. It is shownthat the concepts of local intrinsic dimensionality (LID), local relative contrast (RC), and query
expansion allow to choose query sets of a wide range of difficulty for real-world datasets. Moreover,the effect of the distribution of these dimensionality measures on the running time performance of
implementations is empirically studied. To this end, different visualization concepts are introduced
that allow to get a more fine-grained overview of the inner workings of nearest neighbor searchprinciples. Interactive visualizations are available on the companion website1 . The paper closes withremarks about the diversity of datasets commonly used for nearest neighbor search benchmarking.
It is shown that such real-world datasets are not diverse: results on a single dataset predict resultson all other datasets well.

21

2012 ACM Subject Classification Theory of computation → Nearest neighbor algorithms; Computing methodologies → Simulation evaluation; Theory of computation → Computational geometry

22

Keywords and phrases Nearest neighbor search; Benchmarking

20

1

23

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

Introduction

Nearest neighbor (NN) search is a key primitive in many computer science applications, suchas data mining, machine learning and image processing. For example, Spring and Shrivastava
very recently showed in [30] how nearest neighbor search methods can yield large speed-ups
when training neural network models. In this paper, we study the classical k-NN problem.
Given a dataset S ⊆ Rd , the task is to build an index on S to support the following typeof query: For a query point x ∈ Rd , return the k closest points in S under some distancemeasure D.
In many practical settings, a dataset consists of points represented as high-dimensional
vectors. For example, word representations generated by the glove algorithm [28] associatewith each word in a corpus a d-dimensional real-valued vector. Common choices for d are
between 50 and 300 dimensions. Finding the true nearest neighbors in such a high-dimensional
space is difficult, a phenomenon often referred to as the “curse of dimensionality” [11]. In
practice, it means that finding the true nearest neighbors, in general, cannot be solved much
more efficiently than by a linear scan through the dataset (requiring time O(n) for n data
points) or in space that is exponential in the dimensionality d, which is impractical for large
values of d.
While we cannot avoid these general hardness results [2], most datasets that are used inapplications are not truly high-dimensional. This means that the dataset can be embedded
onto a lower-dimensional space without too much distortion. Intuitively, the intrinsic

1

https://cecca.github.io/role-of-dimensionality-site/

2

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
89
90

dimensionality (ID) of the dataset is the minimum number of dimensions that allows forsuch a representation [16]. There exist many explicit ways of finding good embeddings fora given dataset. For example, the Johnson-Lindenstrauss transformation [21] allows us toembed n data points in Rd into Θ((log n)/ε2 ) dimensions such that all pairwise distances arepreserved up to a (1 + ε) factor with high probability. Another classical embedding often
employed in practice is given by principal component analysis (PCA), see [22].
In this paper, we put our focus on local measures of dimensionality. In particular, weconsider “local intrinsic dimensionality” (LID), a measure introduced by Houle in [16], an
adapted version of “query expansion”, a measure introduced by Ahle et al. in [1], and a local
version of the “relative contrast” of the dataset introduced by He et al. in [15]. We defer adetailed discussion of these measures to Section 2. Intuitively, the LID of a data point x at a
distance threshold r > 0 measures how difficult it is to distinguish between points at distancer and distance (1 + ε)r in a dataset. The Expansion of a data point x and a parameter k > 0
is the ratio of the distance of its 2k-th nearest neighbor and its k-th nearest neighbor. The
relative contrast (RC) of a data point x is the ratio between the mean distance of x to thepoints in the dataset and the distance to its nearest neighbor. The relative contrast of adataset is then the average RC over all data points. Most importantly, all three measures
are local measures that can be associated with a single query. It was stated in [17] that the
LID might serve as a characterization of the difficulty of k-NN queries. One purpose of thispaper is to shed light on this statement, as well as to compare it with the other measures.
A focus of this paper is an empirical study of how these local measures influence theperformance of NN algorithms. To be precise, we will benchmark five different implementations [23] which employ different approaches to NN search. Four of them (HNSW [26], IVF [20],Annoy [8]), and ONNG [18] stood out as most performant in the empirical study conducted by
Aumüller et al. in [5]. Finally, we included the very recent LSH-based approach (PUFFINN)
from Aumüller et al. [7] that promises to give recall guarantees with an adaptive queryalgorithm.
Our experiments are based on the ann-benchmarks system from [5]. We describe theirbenchmarking approach and the changes we made to their system in Section 3. We analyze
the distribution of local dimensionality measures of real-world datasets in Section 4. For all
measures, we will see that there is a substantial difference between these distributions amongdatasets. We will then conduct two sets of experiments: First, we fix a dataset and choose
as query set the set of points with smallest, medium, and largest estimated dimensionality
measure, for each one of LID, RC, and query expansion. In addition, we choose a set of“diverse” query points w.r.t. their estimated dimensionality measure. As we will see, there isa clear tendency such that the larger the LID (resp. the smaller the RC and Expansion),
the more difficult the query for all implementations. Among the three measures, the LID
is the one for which this effect is most pronounced. Next, we will study how the different
dimensionality distributions between datasets influence the running time distribution. In anutshell, it cannot be concluded that any of the three dimensionality measures by itself is agood indicator for the relative performance of a fixed implementation over datasets.
In the first part of our evaluation, we work in the “classical evaluation setting of nearest
neighbor search”. This means that we relate a performance measure (such as the achieved
throughput measured in queries per second) to a quality measure (such as the average fractionof true nearest neighbors found over all queries). While this is the most commonly employedevaluation method, we reason that this way of representing results in fact hides interestingdetails about the inner workings of an implementation. Using non-traditional visualization
techniques provide new insights into their query behavior on real-world datasets. As one

M. Aumüller and M. Ceccarello99

example, we see that reporting average recall on the graph-based approaches from [26, 18]
hides an important detail: For a given query, they either find all true nearest neighbors or
not a single one. This behavior is not shared by the three other approaches that we consider;
all yield a continuous transition from “finding no nearest neighbors” to “finding all of them”.
As a final point, we want, ideally, to benchmark on a collection of “interesting” datasetsthat show the strengths and weaknesses of individual approaches [29]. We will conclude
that there is little diversity among the considered real-world datasets: While the individual
performance observations change from dataset to dataset, the relative performance between
implementations stays the same.

100

Our Contributions. The main contributions of this paper are

91
92
93
94
95
96
97
98

a detailed evaluation of the distribution of local dimensionality measures of many realworld datasets used in benchmarking frameworks,a systematic way to create query workloads of a wide range of difficulty for nearest
neighbor search,an evaluation of the influence of these different dimensionality measures on the performanceof NN search implementations,considerations about the result diversity, andan exploration of different visualization techniques that shed light on individual propertiesof certain implementation principles.

101
102
103
104
105
106
107
108
109

110
111
112

113
114
115
116

117
118
119
120
121
122

123
124
125
126
127

We hope that our approach and the tools developed will find use in future benchmarking
studies. In particular, the way to choose query workloads with varying difficulties results ininteresting testbeds to benchmark implementations.
Related Work on Benchmarking Frameworks for NN. We use the benchmarking systemdescribed in [5] as the starting point for our study. Different approaches to benchmarking
nearest neighbor search are described in [12, 13, 25]. We refer to [5] for a detailed comparison
between the frameworks.
Related Work on the Meaningfulness of Nearest Neighbor Search. Beyer et al. [9] andFrancois et al. [14] showed that under certain randomness assumptions and in the limit
d → ∞, nearest neighbor search queries become “meaningless”, an effect usually referred toas the “concentration of distances”. This means that the nearest and furthest neighbor of adata point become nearly indistinguishable. As mentioned in [15], these observations hold
only asymptotically and usually do not occur in real-world datasets.
Relation to Conference Version. This paper is an extended version of the SISAP 2019
paper [6], which focused mainly on LID as a measure of local dimensionality. To have a better
understanding of how much our observations generalized, this version includes two othermeasures (query expansion and relative contrast) and features a new NN implementation
based on LSH (PUFFINN).

128

2

Local Dimensionality Measures

129

2.1

Local Intrinsic Dimensionality

130
131

We consider a distance-space (Rd , D) with a distance function D : Rd × Rd → R. As describedin [3], we consider the distribution of distances within this space with respect to a reference3

4

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

132
133
134

135
136

137

138

139
140
141
142
143

144
145
146

point x. Such a distribution is induced by sampling n points from the space Rd under acertain probability distribution. We let F : R → [0, 1] be the cumulative distribution functionof distances to the reference point x.
I Definition 1 ([16]). The local continuous intrinsic dimension of F at distance r is givenbyln(F ((1 + ε)r)/F (r)),ε→0ln((1 + ε)r/r)

IDF (r) = lim

whenever this limit exists.
The measure relates the increase in distance to the increase in probability mass (the fractionof points that are within the ball of radius r and (1 + ε)r around the query point). Intuitively,
the larger the LID, the more difficult it is to distinguish true nearest neighbors at distance r
from the rest of the dataset. As described in [17], in the context of k-NN search we set r as
the distance of the k-th nearest neighbor to the reference point x.
Estimating LID We use the Maximum-Likelihood estimator (MLE) described in [24, 3] toestimate the LID of x at distance r. Let r1 ≤ . . . ≤ rk be the sequence of distances of theˆ x is thenk-NN of x. The MLE ID
k

147

ˆx=−
ID

1 X rilnk i=1 rk

!−1
.

(1)

150

Amsaleg et al. showed in [3] that MLE estimates the LID well. We remark that in very
recent work, Amsaleg et al. proposed in [4] a new MLE-based estimator that works withsmaller k values than (1).

151

2.2

148
149

152
153
154
155
156
157
158

Query Expansion

The concept of the Expansion around a query point at a distance threshold r > 0 was
introduced by Ahle et al. in [1]. In their work, the query expansion c∗x is the largest c∗x > 0such that the number of points within distance c∗x r is at most twice the number of points at
distance r. They use this concept to show that an LSH approach can adapt to the query
expansion. More precisely, the larger the query expansion, the less work is conducted bytheir adaptive query algorithm in expectation.
For our use case in k-NN search, we adapt the notion of query expansion as follows.

160

I Definition 2. Given a data set S, an integer k > 0, and a data point x, the Expansion of x
at k is dist(x, x2k )/dist(x, xk ), where xi is the i-th nearest neighbor of x in S for 1 ≤ i ≤ |S|.

161

2.3

159

162
163

164
165
166

Relative Contrast

The concept of relative contrast (RC) was introduced by He et al. in [15]. Here, we concentrateon the following local variant.
I Definition 3. Given a data set S, an integer k > 0, and a data point x, let dmean be
the average distance of x to the points in S. The local relative contrast of x in S is thendmean /dist(x, x∗k ), where x∗k is the k-th nearest neighbor of x in S.

M. Aumüller and M. Ceccarello

167
168
169
170
171
172
173

The relative contrast of the dataset S is the average local relative contrast over all
points in a query set. It was shown in [15] that—if the relative contrast of the dataset is
known—there is a way to choose LSH parameters to adapt to the RC. In the same way as
query expansion, higher contrast means lower running time.
While both Expansion and RC relate the distance of a nearest neighbor to distances ofother data points, RC has a much more global view on the dataset while Expansion considers
distances between close points.

3

174

175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

Overview over the Benchmarking Framework

We use the ann-benchmarks system described in [5] to conduct our experimental study.
Ann-benchmarks is a framework for benchmarking NN search algorithms. It covers dataset
creation, performing the actual experiment, and storing the results of these experiments in atransparent and easy-to-share way. Moreover, results can be explored through various plotting
functionalities, e.g., by creating a website containing interactive plots for all experimental
runs.
Ann-benchmarks interfaces with a NN search implementation by calling its preprocess(index building) and search (query) methods with certain parameter choices. Implementations
are tested on a large set of parameters usually provided by the original authors of an
implementation. The answers to queries are recorded as the indices of the points returned.
Ann-benchmarks stores these parameters together with further statistics such as individual
query times, index size, and auxiliary information provided by the implementation. See [5]for more details.
Compared to the system described in [5], we added tools to estimate the LID based on
Equation (1), to estimate the query Expansion based on Definition 2, to estimate the RC
based on Definition 3, pick “challenging query sets” according to the LID, query expansion,and RC of individual points, and added new datasets and implementations. Moreover, we
implemented a mechanism that allows an implementation to provide further query statistics
after answering a query. To showcase this feature, all implementations in this study report
the number of distance computations performed to answer a query.2

195

4Algorithms and Datasets

196

4.1

Algorithms

197
198
199
200
201
202
203
204
205
206

Nearest neighbor search algorithms for high dimensions are usually graph-, tree-, or hashingbased. We refer the reader to [5] for an overview over these principles and available
implementations. In this study, we concentrate on the three implementations consideredmost performant in [5], namely HNSW [26], Annoy [8] and FAISS-IVF [20] (IVF from now on).
We consider the very recent graph-based approach ONNG [18], and the recent LSH-based
approach PUFFINN [7] in this study as well.
HNSW and ONNG are graph-based approaches. This means that they build a k-NN graphduring the preprocessing step. In this graph, each vertex is a data point and a directed edge(u, v) means that the data point associated with v is “close” to the data point associatedwith u in the dataset. At query time, the graph is traversed to generate candidate points.

2

We thank the authors of the implementations for their help and responsiveness in adding this feature to
their library.

5

6

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

DatasetData Points Dim.

SIFT [19]1 000 000
MNIST
65 000Fashion-MNIST [31]65 000GLOVE [28]1 183 514
GLOVE-2M [28]
2 196 018
GNEWS [27]3 000 000

128
784
784
100
300
300

LID

EXP

RC

avg median

avg median

avg median

Metric

19.4
13.9
15.4
17.9
25.8
20.9

1.042
1.057
1.052
1.054
1.055
1.044

2.6
2.2
2.8
2.3
2.2
2.6

Euclidean
Euclidean
Euclidean
CosineCosineCosine

19.0
13.1
13.8
17.6
23.2
19.9

1.035
1.053
1.046
1.041
1.032
1.034

2.4
2.0
2.7
2.1
1.7
2.3

Table 1 Datasets under consideration with their average local intrinsic dimensionality (LID),
their query expansion (EXP), and their local relative contrast (RC). LID is computed by MLE [3]from the 100-NN of all the data points, EXP is computed by the fraction of distances to the 10-th
NN and 20-th NN, and RC is computed relating the distance of the 10-th NN to the average distancecomputed from a random sample of 10 000 data points.

224

Algorithms differ in details of the graph construction, how they build a navigation structure
on top of the graph, and how the graph is traversed.
Annoy is an implementation of a random projection forest, which is a collection of random
projection trees. Each node in a tree is associated with a set of data points. It splits thesepoints into two subsets according to a chosen hyperplane. If the dataset in a node is smallenough, it is stored directly and the node is a leaf. Annoy employs a data-dependent splitting
mechanism in which a splitting hyperplane is chosen as the one splitting two “average points”
by repeatedly sampling dataset points. In the query phase, trees are traversed using a priority
queue until a predefined number of points is found.
IVF builds an inverted file based on clustering the dataset around a predefined number ofcentroids. It splits the dataset based on these centroids by associating each point with its
closest centroid. During query it finds the closest centroids and checks points in the dataset
associated with those.
PUFFINN uses an adaptive trie-like multi-layer LSH data structure to guide the search.
Using the probabilistic nature of LSH, it exploits adaptive termination criteria to give
guaranteed recall [7] without the need of parameter tuning as in the other approaches. We
note that PUFFINN does not support Euclidean distance and is thus missing in some plots.
We remark we used both IVF and HNSW implementations from FAISS3 .

225

4.2

207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

226
227
228
229
230
231
232
233
234
235

Datasets

Table 1 presents an overview over the datasets that we consider in this study. We restrict ourattention to datasets that are usually employed in connection with Euclidean distance andAngular/Cosine distance. For each dataset, we compute the LID distribution with respect tothe 100-NN as discussed in Section 2, in order to get a stable estimate. Furthermore, we
compute the Expansion using, for each point, the distance of its 10-th nearest neighbor as a
threshold, as discussed in Section 2. The RC is estimated by computing the distance of eachpoint to a sample of 3000 points. SIFT, MNIST, and GLOVE are among the most-widely used
datasets for benchmarking nearest neighbor search algorithms. Fashion-MNIST is considered
as a replacement for MNIST, which is usually considered too easy for machine learning
tasks [31].

3https://github.com/facebookresearch/faiss

M. Aumüller and M. Ceccarello

0

25

50

75

7

GLOVE-2M

GLOVE-2M

GNEWS

GNEWS

SIFT

SIFT

GLOVE

GLOVE

Fashion-MNIST

Fashion-MNIST

MNIST

MNIST

100

125

Local Intrinsic Dimensionality

GNEWS

MNIST

GLOVE

SIFT

Fashion-MNIST

10

Relative contrast

236
237
238
239
240
241
242
243
244
245

246

247
248
249
250
251
252

1.1

1.3

1.5

Expansion

GLOVE-2M

1

1.0

100

Figure 1 Dimensionality measures for eachdataset. Lines within each distribution curve
correspond to the 25, 50 and 75 percentiles.
The red line marks the 10 000 largest estimated LID and the 10 000 smallest RC/Expansion, which we use as a threshold value
to define hard query sets. To compensate theskew of values and improve the readability,
the Expansion plot reports in log scale, omitting the few values larger than 1.5. Datasets
are sorted by median LID (decreasing), RC(increasing), and Expansion (increasing), respectively.

Figure 1 provides a visual representation of the estimated distributions of LID, RC,
and Expansion of each dataset, for k = 100. While the datasets differ widely in their
original dimensionality, the median LID ranges from around 13 for MNIST to about 23 for
GLOVE-2M. The distribution of LID values is asymmetric and shows a long tail behavior.
MNIST, Fashion-MNIST, SIFT, and GNEWS are much more concentrated around the mediancompared to the two GLOVE-based datasets. Considering the RC measure, also its distribution
is asymmetric and long tailed, with mean and median values pretty close to each other.
Nonetheless, the distributions differ in their shape and the length of the tail. As for the
Expansion, the values are very concentrated towards 1 (the minimum value), with extremely
long tails which have been cut out of the figure for the sake of readability.

5

Evaluation

This section reports on the results of our experiments. Due to space constraints, weonly present some selected results. More results can be explored via interactive plots at
https://cecca.github.io/role-of-dimensionality-site/, which also contains a linkto the source code repository. For a fixed implementation, the plots presented here consider
the Pareto frontier over all parameter choices [5]. Tested parameter choices and the associatedplots are available on the website.

8

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

Table 2 Pearson correlation of between the three different measures for each dataset. The
correlations, although mild, are all statistically significant.

datasetFashion-MNISTGLOVEGLOVE-2M
GNEWS
MNIST
SIFT

LID/Expansion

LID/RC

Expansion/RC-0.621-0.571-0.363-0.452-0.569-0.550-0.645-0.527-0.253-0.321-0.583-0.527

0.530
0.551
0.325
0.312
0.518
0.400

Figure 2 Scatterplots relating LID, Expansion, and RC for the GLOVE dataset for a sample of
10 000 data points. All the scales are logarithmic.

253
254
255

256
257
258
259
260
261

262
263

Experimental Setup Experiments were run on 2x 14-core Intel Xeon E5-2690v4 (2.60GHz)
with 512GB RAM using Ubuntu 16.10 (kernel 4.4.0). Index building was multi-threaded,
queries where answered in a single thread.
Quality and Performance Metrics As quality metric we measure the individual recall ofeach query, i.e., the fraction of points reported by the implementation that are among thetrue k-NN. As performance metric, we record individual query times and the total numberof distance computations needed to answer all queries. We usually report on the throughput,
i.e. the average number of queries that can be answered in one second, in the plots denoted
as QPS for queries per second.
Objectives of the Experiments
questions:

Our experiments are tailored to answer the following(Q1) How do LID, Expansion, and RC correlate with each other? (Section 5.1)
265(Q2) How do the LID, Expansion, and RC of a query set influence performance of an imple266
mentation? (Section 5.2 and 5.3)
267(Q3) How well does the number of distance computations reflect the relative running time268
performance of the tested implementations? (Section 5.4)269(Q4) How diverse are measurements obtained on datasets? Do relative differences between
270
the performance of different implementations stay the same over multiple datasets?
271(Section 5.4)272(Q5) How concentrated are quality and performance measures around their mean for the tested
273
implementations? (Section 5.5)264

M. Aumüller and M. Ceccarello

Algorithm

9

Annoy

HNSW

easy

IVF

ONNG

PUFFINN

middle

hard

10000
GLOVE

1000
100
10
1

qps

GLOVE-2M

10000
1000
100
10
1
10000

SIFT

1000
100
10
1
0 0.25 0.5

0.75

1

0 0.25 0.5

0.75

1

0 0.25 0.5

0.75

1

recallFigure 3 Recall-QPS (1/s) tradeoff – up and to the right is better – for queries selected according
to LID, solved using different algorithms. Three datasets are considered here: GLOVE, GLOVE-2M
and SIFT. The scale is logarithmic on the y axis and exponential on the x axis, to take into accountthe scale of the data.

274

Choosing Query Sets For each dataset, we select eight different query sets:

284

easy the 10 000 points with the lowest estimated LID (resp. the highest Expansion/RC)
medium the 10 000 points around the data point with median estimated LID (resp. Expansion/RC)
hard the 10 000 points with the highest estimated LID (resp. lowest Expansion/RC)
diverse 5 000 points chosen so to span the entire range of LID values (resp. Expansion/RC
values). For the LID, we split all data points up into buckets, according to their rank by
LID. For each query, we pick a non-empty bucket uniformly at random, and inside thebucket we pick a random point (with repetition). For Expansion and RC, we pick the
1 500 points with smallest and largest values, and add 2 000 points picked uniformly at
random from the remaining points (with repetition).

285

Figure 1 marks with a red line the LID used as a threshold to build the hard queryset.

275
276
277
278
279
280
281
282
283

292

Main takeaways The following experimental evaluation presents a lot of results, giving
the following main insights. First, we can use local dimensionality measures to build
benchmark query sets of varying difficulty. Second, among these measures, the Local Intrinsic
Dimensionality is the single most effective one at selecting queries of the desired accuracy.
Then, the diverse query set is a good general benchmark, in that it includes queries of a wide
range of difficulties. Finally, average performance measures are convenient but often hide
interesting behaviour, which is best studied by looking at their distribution.

293

5.1

286
287
288
289
290
291

294
295

How Well do the Local Dimensionality Measures Correlate?

Figure 2 visualizes the correlation between the three different local dimensionality measures.
As our working hypothesis, a higher LID score is associated with a higher difficulty for a

10

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

Dimensionality measureeasy

expansion

lid

lrc

middle

hard

10000
GLOVE

1000
100
10

GLOVE-2M

qps

10000
1000
100
10
10000
SIFT

1000
100
10
0 0.25

0.5

0.75

1

0 0.25

0.5

0.75

1

0 0.25

0.5

0.75

1

recallFigure 4 Recall-QPS (1/s) tradeoff – up and to the right is better – for algorithm Annoy solving
queries selected according to LID, RC, and Expansion. Three datasets are considered here: GLOVE,GLOVE-2M and SIFT. The scale is logarithmic on the y axis and exponential on the x axis, totake into account the scale of the data.

306

query, as is a low Expansion or RC score. The plot shows some correlation between thescores: points with a high LID also have a low Expansion and RC, and vice versa. The effectis particularly marked for very easy points: points with a LID ≤ 5 also have a markedly
high Expansion and RC, which are otherwise very concentrated around the mean. If wecompute the Pearson correlation between the different measures (reported in Table 2) we
can see that they are mildly correlated. We notice that for both Expansion and RC there
exist some outliers: that is points with low LID, i.e., that are classified as easy queries, whichhave very small Expansion/RC, i.e., are categorized as a difficult query. Similarly, for the
relation of Expansion and RC, we see a general correlation with a few unstructured outliers.
It will be interesting to see how these correlations are reflected in the performance of an
implementation.

307

5.2

296
297
298
299
300
301
302
303
304
305

308
309
310
311
312
313
314
315
316
317
318

Influence of Dimensionality Measures on Performance

Figure 3 reports the performance of different configurations of all the algorithms we consider
on the GLOVE, GLOVE-2M, and SIFT datasets, drawing queries according to the LID.
In these plots, the best performance is attained in the upper right corner: high recall andhigh throughput.
We observe a clear influence of the LID of the query set on the performance: the moredifficult the query set, i.e., the larger the LID, the more down and to the left the graphs
move, for all algorithms. This means that for higher LID it is more expensive, in terms oftime, to answer queries with good recall.
For all datasets except GLOVE-2M (and GNEWS with the difficult query set), almost
all implementations were still able to achieve close to perfect recall with the parameters set.
This means that even for queries with large LID there are points in the dataset that can beM. Aumüller and M. Ceccarello

HNSW

GNEWS

Annoy

SIFT

1x

1x

10x

3x

2x

2x

2x

2x

4x

4x

2x

1x

1x

1x

3x

2x

2x

12x

2x

3x

2x

53x

2x

1x

2x

19x
9x
76x

3x

1x

1x

8x

3x

2x

26x
160x
127x

sy
ea

id

e
dl

sy

id

sy
id
dl
e
ha
rd

ea

m

dl
e
ha
rd

sy

id

ea

m

dl

rd

ha

id

ea

m

sy

e

1057x

dl

174x

rd

26x
49x

id

47x

374x

ha

103x

ea
sy

9x

10000
1000
100
10
1

m

5521x

e

2370x

m

600x

rd

4098x

4774x

ha

428x

77x

dl
e
ha
rd

2x

3x

Expansion

4x

RC

2x

7x

19x

51x

Fashion-MNIST
2x

29x

8x

MNIST
3x

212x

10000
1000
100
10
1

PUFFINN

LID

qps

GLOVE-2M

IVF

ea

GLOVE
10000
1000
100
10
1

ONNG

m

Algorithm

11

difficulty

Figure 5 Change of performance of the fastest configuration achieving at least 0.9 recall as thedifficulty of the dataset changes. The colored labels report the slowdown factor of the hard querysetcompared with the easy one.

335

efficiently separated from the others.
We now turn our focus on the relationship of the three dimensionality measures withthe performance of the algorithm. Figure 4 considers the same setup as before showing theresults for Annoy for LID, Expansion, and RC. First of all, we observe that easy, middle, andhard query sets show the same behaviour we observed in Figure 3: selecting queries withlower Expansion/RC (or higher LID) makes them more difficult to solve for the algorithm.
Furthermore, we note that, among the three dimensionality measures, the Expansion yields
easier query sets with respect to the other two (i.e. the red line is always more up and to theright). At the same time, LID and RC yield query sets of comparable difficulty.
To better investigate the influence that dimensionality measures have for all datasets
and implementations, consider Figure 5, which reports the change in performance of thefastest configuration attaining recall at least 0.9, for each algorithm. Clearly, all measures
allow to select query sets which are progressively more difficulty to solve accurately for all
algorithms. However, as shown by the labels in each plot, the LID allows to select easy andhard querysets that have a wider performance gap than the ones selected by Expansion orRC, also for the datasets in which all implementations achieve high recall on the hard query
set.

336

5.3

319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334

337
338
339
340
341
342

Predictive Quality of Dimensionality Measures

In the previous two subsections, we found evidence that all dimensionality measures allow topick query sets of various difficulties. Fixing the implementation and considering all datasets,
how well does a dimensionality measure work between two different datasets? Figure 6
reports the queries per second of Annoy for a certain choice of datasets, with queries chosenfrom the middle, hard, and diverse query set.
Comparing results to the dimensionality measurements depicted in Figure 1, we first

12

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

Dataset

GLOVE

Dataset

SIFT

Fashion-MNIST

MNIST

3000
3000

1000

qps

qps

1000
300

300
100

100

30

30
0

0.5

0.75

recall1

0.75

1recallFigure 6 Recall-QPS (1/s) tradeoff – up and to the right is better – for Annoy on GLOVE,
SIFT, Fashion-MNIST, and MNIST with queries selected according to LID. Dashed lines are hardquery sets, solid lines are diverse query sets, dotted lines are middle query sets.

368

observe that the estimated median LID, RC and Expansion all give a good estimate on therelative performance of the algorithms on the data sets: recall that in Figure 1 the datasets
are sorted by median score. (The plot is missing lines for GNEWS and GLOVE-2M, which areconsiderably more challenging according to Table 5.) As an exception, SIFT (middle) is mucheasier than predicted by its LID and Expansion distribution, but the RC measure predicts
this, ranking SIFT lower than GLOVE. In particular, the hard SIFT instance (orange solidline) is as challenging as the medium GLOVE version (green dotted line). On the other hand,
RC classifies MNIST as rather difficult to index, in particular compared to Fashion-MNIST.
The plot on the right in Figure 6 clearly indicates that this is not true, and instead thetwo datasets are basically equivalent. From this, we cannot conclude that the considered
local dimensionality measures as a single indicator explain performance differences of an
implementation across different datasets.
It can also be seen from the plot that the diverse query set is more difficult than themedium query set. In particular, at high recall it generally becomes nearly as difficult as thedifficult dataset. For many implementations, the reason for this behaviour is that they cannot
adapt to the difficulty of a query. They only achieve high average recall when they can solve
sufficiently many queries with high LID or low Expansion. The parameter settings that allow
for such guarantees slow down answering the easy queries by a lot. This manifests in runningtimes that are indistinguishable from those on the hard dataset, while only roughly 30% of
the queries are characterized as difficult ones. As we shall see in Section 5.5, some algorithms
are indeed able to adapt to the difficulty of the query. We believe that the “diverse” querysets thus allow for challenging benchmarking datasets for adaptive query algorithms.
As a side note, we remark that Fashion-MNIST is as difficult to solve as MNIST for all
implementations, and is by far the easiest dataset for all implementations. Thus, while there
is a big difference in the difficulty of solving the classification task [31], there is no measurable
difference between these two datasets in the context of NN search.

369

5.4

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

370
371
372
373

Diversity of Results

Figure 7 gives an overview over how algorithms compare to each other among all “medium
difficulty” querysets, selected according to the LID. Results for Expansion- and RC-based
querysets are similar. We consider two metrics, namely the number of queries per second(top plot), and the number of distance computations (bottom plot). For two different average

M. Aumüller and M. Ceccarello

13

By queries per second
Recall > 0.75

Recall > 0.9

best
1/2 qps
1/4 qps

ONNG
HNSW
IVF
Annoy

1/10 qps

PUFFINN

1/100 qps
GLOVE GLOVE-2M GNEWS

SIFT

MNIST

GLOVE GLOVE-2M GNEWS

SIFT

MNIST

SIFT

MNIST

By distance computations
Recall > 0.75

Recall > 0.9

best
2x dists
4x dists

ONNG
HNSW
PUFFINNAnnoy

10x dists

IVF

100x dists
GLOVE GLOVE-2M GNEWS

SIFT

MNIST

GLOVE GLOVE-2M GNEWS

Figure 7 Ranking of algorithm on five different datasets, according to recall ≥ 0.75 and ≥ 0.9,
and according to two different performance measures: number of queries per second (top) andnumber of distance computations (bottom). Both plots report the ratio with the best performing
algorithm on each dataset, higher is better. Note that the scale is logarithmic.

374
375
376
377
378
379
380

381
382
383
384
385
386
387
388
389
390
391

recall thresholds (0.75 and 0.9) we then select, for each algorithm, the best performing
parameter configuration that attains at least that recall. For each dataset, the plots report
the ratio with the best performing algorithm on that dataset, therefore the best performer isreported with ratio 1. Considering different dataset, we see that there is little variation in
the ranking of the algorithms. Only the two graph-based approaches trade ranks, all otherrankings are stable. Annoy makes fewer distance computations (hence ranks higher in the
figure) but is consistently outperformed by IVF.4

Comparing the number of distance computations to running time performance, we seethat an increase in the number of distance computations is not reflected in a proportional
decrease in the number of queries per second. This means that the candidate set generation
is in general more expensive for graph-based approaches, but the resulting candidate set isof much higher quality and fewer distance computations have to be carried out. Generally,both graph-based algorithms are within a factor 2 from each other, whereas the other twoneed much larger candidate lists to achieve a certain recall. The relative difference usually
ranges from 5x to 30x more distance computations for the non-graph based approaches, inparticular at high recall. This translates well into the performance differences we see inthis setting: consider for instance Figure 3, where the lines corresponding to HNSW and ONNG
upper bound the lines relative to the other algorithms.

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

ONNG

IVF

HNSW

Annoy

PUFFINN

●

10000

●
●
●

●

●
●
●

●

●

● ●
●
●

●

●●●

●
●● ●
●

●
●

●

●

●

●

●
●

●
●
●

●
●

●

●

●
●

●

●

●
●
●

100
●

●

●

●

●

●

●

●

●

●

●
●

●●

●
●
●
●

●

●

●

QPS (1/s)

middle

1000

●

●

●

10

●
●●

●

●
●
●

●
●

10000

●
●
●
●

●
●

●

●
●

●

●

●●

●

●

●●
●

●
●●

●

●
●
●
●
●

●●
●

●

●●
●●
●
●

●●

●

●

●
●
●
●
●
●
●

●

100

●
●

●
●
●
●

●

diverse

●

1000

●

●
●

●
●

●

●

●

●

●
●

●

●

●

●

10

●

●

●
●
●

●
●
●

0.0

0.4

0.8

1.2

0.0

0.4

0.8

1.2

0.0

0.4

0.8

1.2

0.0

0.4

0.8

1.2

0.0

0.4

0.8

1.2

recall
ONNG
●

IVF

HNSW
● ● ● ●

●
●

●
●

●

●

● ●

●●

●

Annoy

PUFFINN

●
●

●

●

●
●

●

●

●●
●
●

●

●

●

●

●
●

●

●

●

●

0.9

●

●
●

●
●

●
●

●
● ●

●

●

●

●
●

●
●

0.6

●

●

●

●

●

●

●

middle

●

● ●

●
●
●

0.3

●

●

●
●
●
●

recall

●

●

0
●

●
●
●

●

●●

0.9

●●

●
●
●

●

●
● ●●

●
●●

●
●
●

●

●

0.6

● ●
●
●

●

● ●

●

●
●
●

●
●

●
●

●

●

●

●

●

●
●

●

●

●
●

●
●
●

●
●●

●
● ●
●

●

●

diverse

●
●

●
●

●
● ●

●

●

●
●

● ●

●

●
●

0.3

●

●

●

0
1e+01

1e+03

1e+05

100

1000

10000

100

1000 10000

10

100 1000 100001

10

100 1000

QPS (1/s)

Figure 8 Distribution of performance for queries on the GLOVE-2M (medium difficulty) dataset.
Looking just at the average performance can hide interesting behaviour.

1.00

1.00

0.75

0.75

0.75

0.50

recall

1.00

recallrecall

14

0.50
0.25

0.25
0.00

0.25

0.00
0

25

50

lid

75

0.50

1

2

3

lrc

4

5

0.00
1.0001.0251.0501.0751.100

expansion

Figure 9 Distribution of Recall vs. LID, RC, and Expansion plot on the GLOVE-2M dataset,using Annoy. Intensity reflects number of queries that achieve a combination of recall vs. LID (orRC or Expansion). The RC plot reports only queries with RC below 5. The Expansion plot reports
only queries with Expansion below 1.1, which are the majority.

M. Aumüller and M. CeccarelloFigure 10 Average correlation between recall and dimensionality measure (across parameter
configurations) for dataset/algorithm pairs, for each type of dimensionality measure. Note how LID
correlates more strongly with recall. Furthermore, note that some algorithms (Annoy, IVF) are moresensitive than others to the dimensionality of the queries.

392

393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414

5.5

Reporting the Distribution of Performance

In the previous sections, we made extensive use of recall/queries per second plots, where eachconfiguration of each algorithm results in a single point, namely the average recall and theinverse of the average query time. As we shall see in this section, concentrating on averages
can hide interesting information in the context of k-NN queries. In fact, not all queries areequally difficult to answer. Consider the plots in Figure 8, which report the performance ofthe five algorithms on the GLOVE-2M dataset, with medium and diverse difficulty queries
selected according to LID. The top 2x5 plots report the recall versus the number of queries
per second for middle (top) and diverse (bottom) query sets, and black dots correspond to
the averages. Additionally, for each configuration, we report the distribution of the recall
scores: the baseline of each recall curve is positioned at the corresponding queries per second
performance. Similarly, the bottom plots report on the inverse of the individual query times(the average of these is the QPS in the left plot) against the average recall. In both plots,
the best performance is achieved towards the top-right corner.
Plotting the distributions, instead of just reporting the averages, uncovers some interesting
behavior that might otherwise go unnoticed, in particular with respect to the recall. The
average recall gradually shifts towards the right as the effect of more and more queries
achieving good recalls. Perhaps surprisingly, for graph-based algorithms this shift is very
sudden: most queries go from having recall 0 to having recall 1, taking no intermediate
values, even for the query set that have very similar LID values. Taking the average recall asa performance metric is convenient in that it is a single number to compare algorithms with.
However, the same average recall can be attained with very different distributions: looking
at such distributions can provide more insight.

4

We note that IVF counts the initial comparisons to find the closest centroids as distance computations,whereas Annoy did not count the inner product computations during tree traversal.

15

16

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449

450

451
452
453
454
455
456
457
458
459
460

For the bottom plots and the middle query set, we observe that individual query timesof all the algorithms are well concentrated around their mean. For the diverse dataset,algorithms might be able to adapt to the query difficulty. We observe that this is not true forAnnoy and IVF. Both of them have a single peak in their query time, which means that they
spend about the same time per query. On the other hand, PUFFINN, HNSW, and ONNG have
two peaks in their performance distribution when they approach high recall. This meansthat they adapt to the presence of easy queries (where both ONNG and PUFFINN report withthe same performance, and HNSW becomes slower for higher recall). It is surprising to seethat all adaptive algorithms have two peaks, while the diverse query set is a mix of threedifferent difficulties.
Figure 9 gives another distributional view on the achieved result quality. The plots showa run of Annoy on the GLOVE-2M dataset with diverse queries. On the top margin we see
the distribution of estimated LID values (left plot), RC values (middle plot), and Expansion
values (right plot) for the diverse query set, on the right margin we see the distribution ofrecall values achieved by the implementation. Each of the queries corresponds to a single
data point in the recall/LID plot and data points are summarized through squares, where
the color intensity of a square indicates the number of data points falling into this region.
The plots show that the higher the LID of a query, there is a clear tendency for the query toachieve lower recall. Expansion and RC, instead, are less predictive in this setting: we canstill observe that low Expansion (i.e. difficult) queries have low recall, but the relationship isless marked.
To further investigate the relationship between the dimensionality measures and therecall, we compute the correlation between each measure and the recall, reporting it in
Figure 10. We observe that, as expected, the LID is is negatively correlated with the recall(i.e. the higher the LID, the harder it is to answer the query accurately), whereas the RC
and Expansion are positively correlated. Looking at the magnitude of the correlation, we
can clearly see that for any pair of dataset and algorithm, the recall correlates more strongly
with the LID. Therefore, if we have to pick queries according to a single local dimensionality
measure, the LID is the best predictor for the difficulty. Obviously, our observation that no
single dimensionality measure is a perfect predictor for the difficulty of queries still holds.
Interestingly, the choice of Expansion as a cost measure to which an LSH query algorithm
may adapt to in [1] seems well-motivated: As the only out of five implementation, LSH-based
PUFFINN shows the strongest correlation to Expansion and not to LID.
For space reasons, we do not report other parameter configurations and datasets, which
nonetheless show similar behaviors. All of them can be accessed at the website.

6

Summary

In this paper we studied the influence of LID, RC, and Expansion to the performance ofnearest neighbor search algorithms. We showed that all three measures allow to choose querysets of a wide range of difficulty from a given dataset. We also showed how different LID,
RC, and Expansion distributions influence the running time performance of the algorithms.
In this respect, we found that LID is a better predictor of performance than the other two.
In any case, we could not conclude that the any of the three scores alone can predict running
time differences well. In particular, SIFT is usually easier than GLOVE for the algorithms:
while GLOVE’s LID distribution would predict the opposite, the RC distribution correctlypredicts this relationship between the datasets. However, the RC distribution does notpredict differences correctly, either.

M. Aumüller and M. Ceccarello

476With regard to challenging query workloads, we described a way to choose diverse querysets. They have the property that for most implementations it is easy to perform wellfor most of the query points, but they contain many more easy and difficult queries thanquery workloads chosen randomly from the dataset. We believe this is a very interesting
benchmarking workload for approaches that try to adapt to the difficulty of an individual
query.
We introduced novel visualization techniques to show the uncertainty within the answer
to a set of queries, which made it possible to show a clear difference between the graph-basedalgorithms and the other approaches. Furthermore, these visualizations allow to see whether
a particular algorithm is able to adapt to the difficulty of the queries.
We hope that this study initiates the search for more diverse datasets, or for theoreticalreasoning why certain algorithmic principles are generally better suited for nearest neighborsearch. On a more practical side, Casanova et al. showed in [10] how dimensionality testing
can be used to speed up reverse k-NN queries. We would be interested in seeing whether the
LID can be used at other places in the design of NN algorithms to guide the search processor the parameter selection.

477

Acknowledgements

461
462
463
464
465
466
467
468
469
470
471
472
473
474
475

478
479
480
481

The authors would like to thank the anonymous reviewers of the conference version of thispaper, who helped to improve the presentation of the paper. The research leading to theseresults has received funding from the European Research Council under the European Union’s
7th Framework Programme (FP7/2007-2013) / ERC grant agreement no. 614331.
References

482

483

1

484
485

2

486
487

3

488
489

4

490
491
492

5

493
494
495

6

496
497
498

7

499
500
501
502

8
9

503
504
505
506

10

Ahle, T.D., Aumüller, M., Pagh, R.: Parameter-free locality sensitive hashing for spherical
range reporting. In: SODA. pp. 239–256. SIAM (2017)
Alman, J., Williams, R.: Probabilistic polynomials and hamming nearest neighbors. In:
FOCS’15. pp. 136–150
Amsaleg, L., Chelly, O., Furon, T., Girard, S., Houle, M.E., Kawarabayashi, K.I., Nett, M.:
Estimating local intrinsic dimensionality. In: KDD’15. pp. 29–38. ACM (2015)
Amsaleg, L., Chelly, O., Houle, M.E., Kawarabayashi, K.i., Radovanović, M., Treeratanajaru,
W.: Intrinsic dimensionality estimation within tight localities. In: Proceedings of the 2019
SIAM International Conference on Data Mining. pp. 181–189. SIAM (2019)
Aumüller, M., Bernhardsson, E., Faithfull, A.J.: Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2020), see
https://arxiv.org/abs/1807.05614 for an open access version.
Aumüller, M., Ceccarello, M.: The role of local intrinsic dimensionality in benchmarking
nearest neighbor search. In: SISAP. Lecture Notes in Computer Science, vol. 11807, pp.
113–127. Springer (2019)
Aumüller, M., Christiani, T., Pagh, R., Vesterli, M.: PUFFINN: parameterless and universally
fast finding of nearest neighbors. In: ESA. LIPIcs, vol. 144, pp. 10:1–10:16. Schloss Dagstuhl Leibniz-Zentrum für Informatik (2019)
Bernhardsson, E.: Annoy, https://github.com/spotify/annoy
Beyer, K.S., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is ”nearest neighbor” meaningful? In: ICDT. Lecture Notes in Computer Science, vol. 1540, pp. 217–235. Springer(1999)
Casanova, G., Englmeier, E., Houle, M.E., Kröger, P., Nett, M., Schubert, E., Zimek, A.:
Dimensional testing for reverse k-nearest neighbor search. PVLDB 10(7), 769–780 (2017)

17

18

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

507

11

508
509

12

510
511
512

13

513
514

14

515
516

15

517
518

16

519
520

17

521
522
523

18

524
525

19

526
527
528

20

529
530

21

531
532
533

22
23

534
535

24

536
537

25

538
539
540

26

541
542

27

543
544

28

545
546

29

547
548

30

549
550

31

551

Chávez, E., Navarro, G., Baeza-Yates, R., Marroquín, J.L.: Searching in metric spaces. ACM
Comput. Surv. 33(3), 273–321 (Sep 2001). https://doi.org/10.1145/502807.502808
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. J. of Machine Learning Research 14,
801–805 (2013)
Edel, M., Soni, A., Curtin, R.R.: An automatic benchmarking system. In: NIPS 2014 Workshop
on Software Engineering for Machine Learning (2014)
François, D., Wertz, V., Verleysen, M.: The concentration of fractional distances. IEEE Trans.
Knowl. Data Eng. 19(7), 873–886 (2007)
He, J., Kumar, S., Chang, S.: On the difficulty of nearest neighbor search. In: ICML. icml.cc/ Omnipress (2012)
Houle, M.E.: Dimensionality, discriminability, density and distance distributions. In: Data
Mining Workshops (ICDMW). pp. 468–473. IEEE (2013)
Houle, M.E., Schubert, E., Zimek, A.: On the correlation between local intrinsic dimensionality
and outlierness. In: SISAP’18. pp. 177–191 (2018). https://doi.org/10.1007/978-3-030-022242_14
Iwasaki, M., Miyazaki, D.: Optimization of Indexing Based on k-Nearest Neighbor Graph for
Proximity Search in High-dimensional Data. ArXiv e-prints (Oct 2018)
Jégou, H., Douze, M., Schmid, C.:
Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117–128 (2011).
https://doi.org/10.1109/TPAMI.2010.57
Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with gpus. CoRR
abs/1702.08734 (2017)
Johnson, W.B., Lindenstrauss, J., Schechtman, G.: Extensions of Lipschitz maps into Banach
spaces. Israel Journal of Mathematics 54(2), 129–138 (1986)
Jolliffe, I.: Principal component analysis. Springer (2011)
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)
Levina, E., Bickel, P.J.: Maximum likelihood estimation of intrinsic dimension. In: NIPS’15.
pp. 777–784 (2005)
Li, W., Zhang, Y., Sun, Y., Wang, W., Zhang, W., Lin, X.: Approximate nearest neighborsearch on high dimensional data - experiments, analyses, and improvement (v1.0). CoRR
abs/1610.02455 (2016)
Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using
Hierarchical Navigable Small World graphs. ArXiv e-prints (Mar 2016)
Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in
vector space. CoRR abs/1301.3781 (2013)
Pennington, J., Socher, R., Manning, C.D.: Glove: Global vectors for word representation. In:
Empirical Methods in Natural Language Processing (EMNLP). pp. 1532–1543 (2014)
Smith-Miles, K., Baatar, D., Wreford, B., Lewis, R.: Towards objective measures of algorithm
performance across instance space. Computers & Operations Research 45, 12 – 24 (2014)
Spring, R., Shrivastava, A.: Scalable and sustainable deep learning via randomized hashing.
In: KDD’17. pp. 445–454 (2017). https://doi.org/10.1145/3097983.3098035
Xiao, H., Rasul, K., Vollgraf, R.: Fashion-MNIST: a novel image dataset for benchmarking
machine learning algorithms. CoRR abs/1708.07747 (2017)

552

A

Additional experiments

553

A.1

How Well is Running Time Reflected in Distance Computations

554
555

Figures 11 and 12 present the same setup as in subsection 5.2, but this time relating recall
to the number of distance computations required to achieve that recall. This cost measureM. Aumüller and M. Ceccarello

Algorithm

19

Annoy

HNSW

ONNG

PUFFINN

middle

hard

1e+06
1e+05
1e+04
1e+03
1e+02

GLOVE

1e+06
1e+05
1e+04
1e+03
1e+02

GLOVE-2M

Distance computations

easy

IVF

SIFT

1e+06
1e+05
1e+04
1e+03
1e+02
0 0.25 0.5

0.75

1

0 0.25 0.5

0.75

1

0 0.25 0.5

0.75

1

recallFigure 11 Recall-Distance computations tradeoff – down and to the right is better – for queries
selected according to their LID. Three datasets are considered here: GLOVE, GLOVE-2M and
SIFT. The scale is logarithmic on the y axis and exponential on the x axis, to take into account thescale of the data.

556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571

is more robust to implementation details and gives a more general view on how well an
approach is able to efficiently index the data set.
Let us consider Figure 11. For the recall vs. distance computations trade-off, we aim
for all curves to be down and to the right, which reflects high recall with a small number of
distance computations. In general, the trend observed in the running time study continues
for distance computations: the easy, middle, and hard query sets are progressively moredifficult to answer. Graph-based approaches compute considerably fewer distances, and there
is little difference in these two approaches. With regard to the other approaches, Annoy
computes fewest distances, but turns out to be the slowest implementation on most of thedata and query sets combinations.
Figure 12 shows the influence of the three different dimensionality measures for Annoy.
First, we notice that there is remarkably little difference between the three different dimensionality measures in terms of distance computations, in particular for SIFT. For the difficult
query set, we see that Expansion provides the easier-to-index queries, whereas RC provides
considerably more difficult queries than the two others considering the easy queryset. LID
provides the best of both worlds.

The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search

Dimensionality measureeasy

expansion

lid

lrc

middle

hard

1e+05
GLOVE

1e+04
1e+03
1e+02
1e+05

GLOVE-2M

distcomps

20

1e+04
1e+03
1e+02
1e+05

SIFT

1e+04
1e+03
1e+02
0 0.25

0.5

0.75

1

0 0.25

0.5

0.75

1

0 0.25

0.5

0.75

1

recallFigure 12 Recall-Distance computations tradeoff – down and to the right is better – for queries
solved with Annoy. Three datasets are considered here: GLOVE, GLOVE-2M and SIFT. The scale
is logarithmic on the y axis and exponential on the x axis, to take into account the scale of the data.