RcppHNSW

An R interface to hnswlib, a C++ library for approximate nearest neighbor search using hierarchical navigable small-world graphs (Malkov and Yashunin, 2020). It supports Euclidean, squared Euclidean, cosine, and inner-product distances.

Installation

From CRAN:

install.packages("RcppHNSW")

Or, for the development version, use pak:

pak::pak("jlmelville/rcpphnsw")

Find nearest neighbors

To find neighbors within a dataset, use hnsw_knn(). Here we'll ask for four neighbors for each item in iris, leaving out the species column:

library(RcppHNSW)

irism <- as.matrix(iris[, -5])
neighbors <- hnsw_knn(irism, k = 4)
neighbors$idx[1:5, ]
neighbors$dist[1:5, ]

The result is a list containing two matrices: idx gives the neighbors' row numbers, and dist gives their Euclidean distances. Each row corresponds to an item in irism, with one column per neighbor.

If you want to find neighbors for new data, you can keep the index around and query it with hnsw_search(). Here we'll use the first 100 items to build the index, then find neighbors for the remaining 50:

ann <- hnsw_build(irism[1:100, ])
neighbors <- hnsw_search(irism[101:150, ], ann, k = 4)

If the results are a bit too approximate, try increasing the search parameter ef. This gives the search more work to do, so it also takes longer. See the parameter guide for tuning, distance choices, and column-oriented data.

Documentation

• Function reference
• Parameters, metrics, and data layout
• Module API and index lifecycle: add items, delete items, resize, and save an index.
• NEWS

Project

The inspiration for this package is RcppAnnoy, an R interface to Annoy. Source code and issue tracking are on GitHub.

Licensed under GPL-3 or later.