Parameters, metrics, and data layout

The defaults are a reasonable place to start, but you may want to trade a little more search time for better neighbors. This article goes through the parameters involved, then looks at distances, data layout, and getting repeatable results.

Tune speed and recall

The first parameter to try is search ef: increasing it lets the search explore more candidates, which usually means finding more of the true nearest neighbors. The price is a slower search. To see whether the extra time is buying you anything, compare the results with an exact search on a sample of your data. The fraction of true nearest neighbors found is called recall.

You can change search ef without rebuilding the index, which makes it a convenient place to experiment. If that isn’t enough, try rebuilding with a larger construction ef or M. Construction ef controls how thoroughly the graph is built. M controls how many connections each item has in the graph; increasing it also uses more memory.

There are two different parameters called ef, which is a bit unfortunate. In hnsw_build() it controls construction; in hnsw_search() it controls search. hnsw_knn() does both jobs, so it calls the construction parameter ef_construction. Here are the names and defaults together:

Function	Construction controls	Search control
hnsw_knn()	M = 16, ef_construction = 200	ef = 10
hnsw_build()	M = 16, ef = 200	—
hnsw_search()	—	ef = 10

Search uses at least k candidates, even when ef < k. Neither construction nor search ef is capped at the dataset size.

Let’s build an index from the first 100 items in iris, then use a larger search ef to query it with the remaining 50:

library(RcppHNSW)

irism <- as.matrix(iris[, -5])
ann <- hnsw_build(irism[1:100, ], M = 16, ef = 200)
neighbors <- hnsw_search(irism[101:150, ], ann, k = 5, ef = 50)
dim(neighbors$idx)

## [1] 50  5

Each of the 50 query rows gets five neighbors. The returned indices refer to the first 100 rows, because those are the items we put in the index.

Choose a distance

distance	Calculation
"euclidean" (default)	Euclidean distance
"l2"	Squared Euclidean distance
"cosine"	One minus cosine similarity
"ip"	One minus inner product: 1 - sum(a * b)

Cosine distance compares directions, so vectors are normalized to unit length before indexing or searching. Inner-product distance also takes magnitude into account. Despite the name, it can be negative, and an item need not be its own nearest neighbor. That last point matters if you’re expecting to remove self-matches by dropping the first neighbor. With any of these distances, approximate search can miss a self-match too.

Coordinates are stored in single precision. For very large values or zero cosine vectors, see the numeric limits.

Store items by row or column

By default, each row of X is an item, as is usual for data in R. R stores matrices by column, though, so putting each item in a column can reduce copying overhead for high-dimensional vectors. If your data is arranged that way, use byrow = FALSE. The results follow the query orientation:

byrow	Items in X	Dimensions of idx and dist
TRUE	Rows	n × k
FALSE	Columns	k × n

Here n is the number of queries and k is the number of neighbors per query. For example, we can transpose our iris matrix and get four neighbors per item, now in columns:

iris_by_col <- t(irism)
neighbors_by_col <- hnsw_knn(iris_by_col, k = 4, byrow = FALSE)
dim(neighbors_by_col$idx)

## [1]   4 150

Use multiple threads

Set n_threads to the maximum number of threads to use for batch insertion or search. The default is zero, which runs serially, as does one. grain_size sets the minimum number of items per thread. For small batches, a larger grain size avoids spending time starting threads that have very little to do. A grain size of zero is treated as one.

Reproduce an index

For repeatable builds, keep random_seed fixed and use serial construction. R’s set.seed() won’t help here: hnswlib has its own random number generator. A fixed seed also doesn’t fix the order in which parallel threads insert items, so parallel builds can give different results. To reuse an existing graph, save the index.