Skip to contents

Find Nearest Neighbors and Distances

Source: R/hnsw.R
hnsw_knn.Rd

A k-nearest neighbor algorithm using the hnswlib library (https://github.com/nmslib/hnswlib).

Usage

hnsw_knn(
  X,
  k = 10,
  distance = "euclidean",
  M = 16,
  ef_construction = 200,
  ef = 10,
  verbose = FALSE,
  progress = "bar",
  n_threads = 0,
  grain_size = 1,
  byrow = TRUE,
  random_seed = 100
)

Arguments

X

A numeric matrix of n items to search for neighbors. If byrow = TRUE (the default) then each row of X stores an item to be searched. Otherwise, each item should be stored in the columns of X.

k

Positive whole number of neighbors to return. It cannot exceed the number of items in X.

distance

Type of distance to calculate. One of:

  • "l2" Squared L2, i.e. squared Euclidean.

  • "euclidean" Euclidean.

  • "cosine" One minus cosine similarity.

  • "ip" One minus inner product: 1 - sum(a * b). Values can be negative and need not satisfy metric properties.

M

Controls the number of bi-directional links created for each element during index construction. Higher values lead to better results at the expense of memory consumption. Typical values are 2 - 100, but for most datasets a range of 12 - 48 is suitable. Can't be smaller than 2.

ef_construction

Size of the dynamic list used during construction. A larger value means a better quality index, but increases build time. Must be a positive whole number. It is raised to at least k and is not bounded by the size of the dataset.

ef

Size of the dynamic list used during search. Higher values lead to improved recall at the expense of longer search time. Must be positive; the effective value is at least k and may be greater or smaller than ef_construction. Typical values are 100 - 2000.

verbose

If TRUE, log messages to the console.

progress

defunct and has no effect.

n_threads

Maximum number of threads to use. Zero and one both select serial execution. For larger values, the exact number is determined by grain_size and the amount of work.

grain_size

Minimum number of items in X to add or search per thread. Zero is treated as one. If the number of items in X isn't sufficient, then fewer than n_threads will be used. This is useful in cases where the overhead of context switching with too many threads outweighs the gains due to parallelism.

byrow

If TRUE (the default), this indicates that the items to be processed in X are stored in each row of X. Otherwise, the items are stored in the columns of X. Storing items in each column reduces the overhead of copying data to a form that can be used by the hnsw library. Note that if byrow = FALSE, any matrices returned from this function will also store the items by column.

random_seed

Seed passed to hnswlib for index construction. The default, 100, is the underlying hnswlib default. This seed belongs to hnswlib: calling set.seed() does not affect index construction.

Value

a list containing:

  • idx a matrix containing the nearest neighbor indices.

  • dist a matrix containing the nearest neighbor distances.

The dimensions of the matrices respect the storage (row or column-based) of X as indicated by the byrow parameter. If byrow = TRUE (the default) each row of idx and dist contain the neighbor information for the item passed in the equivalent row of X, i.e. the dimensions are n x k where n is the number of items in X. If byrow = FALSE, then each column of idx and dist contain the neighbor information for the item passed in the equivalent column of X, i.e. the dimensions are k x n.

Hnswlib Parameters

Some details on the parameters used for index construction and search, based on https://github.com/nmslib/hnswlib/blob/master/ALGO_PARAMS.md:

  • M Controls the number of bi-directional links created for each element during index construction. Higher values lead to better results at the expense of memory consumption, which is around M * 8-10 bytes per stored element. High intrinsic dimensionalities will require higher values of M. A range of 2 - 100 is typical, but 12 - 48 is ok for most use cases.

  • ef_construction Size of the dynamic list used during construction. A larger value means a better quality index, but increases build time. It must be a positive whole number, but is not bounded by the size of the dataset. A typical range is 100 - 2000. Beyond a certain point, increasing ef_construction has no effect. A sufficient value of ef_construction can be determined by searching with ef = ef_construction, and ensuring that the recall is at least 0.9.

  • ef Size of the dynamic list used during index search. Can differ from ef_construction. The effective value is at least k, and it is not bounded by the number of elements in the index.

Numeric data and reproducibility

Coordinates are stored as single-precision floating-point values. The package rejects non-finite or out-of-range coordinates and, for cosine distance, vectors with zero norm after conversion. Parallel index construction may be nondeterministic even for a fixed random_seed. Use serial construction for repeatable reconstruction. Save the constructed index to reuse the exact graph.

HNSW search is approximate. For L2, Euclidean, and cosine distance, an item queried against its source data has distance zero from itself, but it can be omitted when recall is insufficient. Under inner-product distance, an item need not be its own nearest neighbor.

References

Malkov, Y. A., & Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824-836. doi:10.1109/TPAMI.2018.2889473 .

Examples

iris_nn_data <- hnsw_knn(as.matrix(iris[, -5]), k = 10)