Package {annsearchR}

annsearchR: Fast Approximate Nearest Neighbour Search

Description

R interface to the Rust crate 'ann-search-rs'. Build an exact or approximate nearest neighbour index once (HNSW, Annoy, IVF, NNDescent, Vamana and more), keep it in memory behind an R6 object and query it as often as you like. Multi-threaded via 'Rayon', with f32 or f64 storage. Methods include hierarchical navigable small world graphs (Malkov and Yashunin, 2020) doi:10.1109/TPAMI.2018.2889473 and NN-Descent (Dong, Charikar and Li, 2011) doi:10.1145/1963405.1963487.

Author(s)

Maintainer: Gregor Lueg gregorlueg@me.com

Authors:

• Gregor Lueg gregorlueg@me.com

Other contributors:

• Authors of the dependency Rust crates (see inst/AUTHORS file) [contributor, copyright holder]

See Also

Useful links:

• https://gregorlueg.github.io/annsearchR/

• https://github.com/GregorLueg/annsearchR

• Report bugs at https://github.com/GregorLueg/annsearchR/issues

Index classes by algorithm name

Description

Index classes by algorithm name

Usage

.ann_classes()

Value

Named list of R6 generators, keyed by the algorithm name the Rust side reports.

Metric names and how they map onto the Rust core

Description

The core works in squared Euclidean, so "euclidean" carries a flag to square root the distances on the way out. The core also silently falls back to squared Euclidean on a string it does not know, which is why every metric is validated here before it gets anywhere near Rust.

Usage

.ann_metrics()

Value

A named list. Each element has core (string passed to Rust) and sqrt (boolean).

Coerce and validate a data matrix for the Rust side

Description

Coerce and validate a data matrix for the Rust side

Usage

.as_ann_matrix(x, dim = NULL, .var.name = "data")

Arguments

Value

A double matrix.

Validate a search-time knob

Description

Validate a search-time knob

Usage

.as_knob(value, null_ok = TRUE, .var.name = "value")

Arguments

Value

value as integer, or NULL.

Is this an external pointer, alive or dead

Description

Is this an external pointer, alive or dead

Usage

.is_ptr(x)

Arguments

Value

Boolean.

Base class for all nearest neighbour indices

Description

Holds a pointer to an index living in Rust memory, plus the bits R needs to talk to it (metric, precision, shape). Never instantiated directly: use one of the algorithm classes such as HnswIndex, AnnoyIndex or ExhaustiveIndex.

The index itself is not serialised by base::saveRDS(). A restored object holds a dead pointer and every method errors. Use ⁠$save()⁠ and load_ann_index() instead.

Active bindings

Methods

Public methods

• AnnIndex$predict()

• AnnIndex$query_self()

• AnnIndex$save()

• AnnIndex$print()

• AnnIndex$clone()

AnnIndex$predict()

Find the k nearest indexed samples for each row of newdata.

Usage

AnnIndex$predict(newdata, k = 15L, return_dist = TRUE, .verbose = FALSE)

Arguments

Returns

A list with:

• idx - Integer matrix, queries x k. 1-based row indices into the indexed data. NA where fewer than k neighbours were found.

• dist - Numeric matrix, queries x k, or NULL if return_dist = FALSE. Inf where idx is NA.

AnnIndex$query_self()

kNN graph over the indexed data itself. Uses each index's own self-query path, which is faster than ⁠$predict()⁠ on the training data.

Usage

AnnIndex$query_self(k = 15L, return_dist = TRUE, .verbose = FALSE)

Arguments

Returns

A list with idx and dist, as for ⁠$predict()⁠, with one row per indexed sample.

AnnIndex$save()

Write the index to a directory. Read it back with load_ann_index().

Usage

AnnIndex$save(dir)

Arguments

Returns

The object, invisibly.

AnnIndex$print()

Print a one-line summary.

Usage

AnnIndex$print(...)

Arguments

Returns

The object, invisibly.

AnnIndex$clone()

The objects of this class are cloneable with this method.

Usage

AnnIndex$clone(deep = FALSE)

Arguments

Annoy index

Description

Random projection forest, as in Spotify's Annoy. More trees means better recall, a larger index and a slower build. Raise search_budget for recall at query time. No Manhattan.

Super class

AnnIndex -> AnnoyIndex

Active bindings

Methods

Public methods

• AnnoyIndex$new()

• AnnoyIndex$clone()

AnnoyIndex$new()

Build the index.

Usage

AnnoyIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine"),
  n_trees = 25L,
  search_budget = NULL,
  seed = 42L,
  precision = c("float", "double")
)

Arguments

AnnoyIndex$clone()

The objects of this class are cloneable with this method.

Usage

AnnoyIndex$clone(deep = FALSE)

Arguments

References

Bernhardsson E. Annoy (Approximate Nearest Neighbors Oh Yeah). https://github.com/spotify/annoy

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- AnnoyIndex$new(x, n_trees = 25L)
res <- idx$predict(x[1:5, ], k = 10L)

Ball tree index

Description

Metric tree of nested hyperspheres, pruned by the triangle inequality. Pays off on data with real cluster structure at moderate dimensionality. The default search budget (5% of the indexed points) makes it approximate; raise it for recall. Past about 10% recall plateaus and query time does not fall. No Manhattan.

Super class

AnnIndex -> BallTreeIndex

Active bindings

Methods

Public methods

• BallTreeIndex$new()

• BallTreeIndex$clone()

BallTreeIndex$new()

Build the index.

Usage

BallTreeIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine"),
  search_budget = NULL,
  seed = 42L,
  precision = c("float", "double")
)

Arguments

BallTreeIndex$clone()

The objects of this class are cloneable with this method.

Usage

BallTreeIndex$clone(deep = FALSE)

Arguments

References

Omohundro SM (1989). Five balltree construction algorithms. Technical Report TR-89-063, International Computer Science Institute, Berkeley.

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- BallTreeIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

Exhaustive (brute-force) index

Description

Exact search: every query is compared to every indexed sample, SIMD accelerated and multi-threaded. The ground truth to measure the approximate indices against, and faster than you might think up to a few hundred thousand samples. Large query batches go through a blocked GEMM path, which on macOS runs on Apple Accelerate, so it can outrun the thread count set by ann_set_threads().

Super class

AnnIndex -> ExhaustiveIndex

Methods

Public methods

• ExhaustiveIndex$new()

• ExhaustiveIndex$clone()

ExhaustiveIndex$new()

Build the index.

Usage

ExhaustiveIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  precision = c("float", "double")
)

Arguments

ExhaustiveIndex$clone()

The objects of this class are cloneable with this method.

Usage

ExhaustiveIndex$clone(deep = FALSE)

Arguments

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- ExhaustiveIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

HNSW index

Description

Hierarchical navigable small world graph. The usual first choice: high recall at low query latency. Raise ef_search for recall at query time, ef_construction for a better graph at build time.

Nodes are inserted in parallel, so two builds with the same seed give slightly different graphs. Need bit-identical results? Build with ann_set_threads(1L).

Super class

AnnIndex -> HnswIndex

Active bindings

Methods

Public methods

• HnswIndex$new()

• HnswIndex$clone()

HnswIndex$new()

Build the index.

Usage

HnswIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  m = 16L,
  ef_construction = 200L,
  ef_search = 50L,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

HnswIndex$clone()

The objects of this class are cloneable with this method.

Usage

HnswIndex$clone(deep = FALSE)

Arguments

References

Malkov YA, Yashunin DA (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42, 824-836. doi:10.1109/TPAMI.2018.2889473

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- HnswIndex$new(x, metric = "cosine")
idx$ef_search <- 100L
res <- idx$predict(x[1:5, ], k = 10L)

IVF index

Description

Inverted file over k-means Voronoi cells. Cheap to build and easy to tune: nlist sets how finely the space is cut, nprobe how many cells a query visits. The smallest of the unquantised approximate indices. No Manhattan.

Super class

AnnIndex -> IvfIndex

Active bindings

Methods

Public methods

• IvfIndex$new()

• IvfIndex$clone()

IvfIndex$new()

Build the index.

Usage

IvfIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine"),
  nlist = NULL,
  nprobe = NULL,
  kmeans_iters = NULL,
  kmeans_balanced = FALSE,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

IvfIndex$clone()

The objects of this class are cloneable with this method.

Usage

IvfIndex$clone(deep = FALSE)

Arguments

References

Sivic J, Zisserman A (2003). Video Google: a text retrieval approach to object matching in videos. Proceedings Ninth IEEE International Conference on Computer Vision, 1470-1477. doi:10.1109/ICCV.2003.1238663

Jégou H, Douze M, Schmid C (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33, 117-128. doi:10.1109/TPAMI.2010.57

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- IvfIndex$new(x)
idx$nprobe <- 10L
res <- idx$predict(x[1:5, ], k = 10L)

kd forest index

Description

Forest of randomised kd spill-trees. Same trade as AnnoyIndex with axis-aligned splits instead of random hyperplanes: more trees means better recall and a larger index. Points near a split land in both children, which lets one descent recover neighbours a hard split would separate. The one tree index here that supports Manhattan.

Super class

AnnIndex -> KdTreeIndex

Active bindings

Methods

Public methods

• KdTreeIndex$new()

• KdTreeIndex$clone()

KdTreeIndex$new()

Build the index.

Usage

KdTreeIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  n_trees = 25L,
  search_budget = NULL,
  seed = 42L,
  precision = c("float", "double")
)

Arguments

KdTreeIndex$clone()

The objects of this class are cloneable with this method.

Usage

KdTreeIndex$clone(deep = FALSE)

Arguments

References

Silpa-Anan C, Hartley R (2008). Optimised KD-trees for fast image descriptor matching. 2008 IEEE Conference on Computer Vision and Pattern Recognition, 1-8. doi:10.1109/CVPR.2008.4587638

Muja M, Lowe DG (2014). Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 2227-2240. doi:10.1109/TPAMI.2014.2321376

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- KdTreeIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

kMkNN index

Description

Exact search over a k-means partition, pruning whole clusters by the triangle inequality. Same answers as ExhaustiveIndex; whether it is faster depends on how well the data clusters, so time both. No Manhattan.

Super class

AnnIndex -> KmknnIndex

Methods

Public methods

• KmknnIndex$new()

• KmknnIndex$clone()

KmknnIndex$new()

Build the index.

Usage

KmknnIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine"),
  nlist = NULL,
  kmeans_iters = NULL,
  kmeans_balanced = FALSE,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

KmknnIndex$clone()

The objects of this class are cloneable with this method.

Usage

KmknnIndex$clone(deep = FALSE)

Arguments

References

Wang X (2011). A fast exact k-nearest neighbors algorithm for high dimensional search using k-means clustering and triangle inequality. The 2011 International Joint Conference on Neural Networks, 1293-1299. doi:10.1109/IJCNN.2011.6033373

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- KmknnIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

LSH index

Description

Multi-probe locality-sensitive hashing over random projections. By far the cheapest index to build here, and the weakest on recall for the query time it costs; the one index whose query can come out slower than brute force. Fewer bits_per_hash widens the buckets, more num_tables trades memory for recall. No Manhattan.

Super class

AnnIndex -> LshIndex

Active bindings

Methods

Public methods

• LshIndex$new()

• LshIndex$clone()

LshIndex$new()

Build the index.

Usage

LshIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine"),
  num_tables = 8L,
  bits_per_hash = 12L,
  slot_bits = NULL,
  n_probe = NULL,
  max_candidates = NULL,
  seed = 42L,
  precision = c("float", "double")
)

Arguments

LshIndex$clone()

The objects of this class are cloneable with this method.

Usage

LshIndex$clone(deep = FALSE)

Arguments

References

Charikar MS (2002). Similarity estimation techniques from rounding algorithms. Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 380-388. doi:10.1145/509907.509965

Datar M, Immorlica N, Indyk P, Mirrokni VS (2004). Locality-sensitive hashing scheme based on p-stable distributions. Proceedings of the 20th Annual Symposium on Computational Geometry, 253-262. doi:10.1145/997817.997857

Lv Q, Josephson W, Wang Z, Charikar M, Li K (2007). Multi-probe LSH: efficient indexing for high-dimensional similarity search. Proceedings of the 33rd International Conference on Very Large Data Bases, 950-961. https://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- LshIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

NN-Descent index

Description

Builds the kNN graph directly by iterative local join. Want the kNN graph of the data itself (UMAP, clustering)? ⁠$extract_knn()⁠ hands back the converged graph without any search, far cheaper than ⁠$query_self()⁠. It reads the post-pruning graph, so leave diversify_prob at 0 if extraction is the point.

Super class

AnnIndex -> NNDescentIndex

Active bindings

Methods

Public methods

• NNDescentIndex$new()

• NNDescentIndex$extract_knn()

• NNDescentIndex$clone()

NNDescentIndex$new()

Build the index.

Usage

NNDescentIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  k_graph = 15L,
  delta = 0.001,
  diversify_prob = 0,
  max_iter = NULL,
  max_candidates = NULL,
  n_trees = NULL,
  ef_search = NULL,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

NNDescentIndex$extract_knn()

The converged kNN graph over the indexed data, read straight off the index. No search involved.

Usage

NNDescentIndex$extract_knn(k = NULL, include_self = TRUE, return_dist = TRUE)

Arguments

Returns

A list with idx and dist, as for ⁠$predict()⁠, with one row per indexed sample. Rows the graph cannot fill are NA padded.

NNDescentIndex$clone()

The objects of this class are cloneable with this method.

Usage

NNDescentIndex$clone(deep = FALSE)

Arguments

References

Dong W, Charikar M, Li K (2011). Efficient k-nearest neighbor graph construction for generic similarity measures. Proceedings of the 20th International Conference on World Wide Web, 577-586. doi:10.1145/1963405.1963487

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- NNDescentIndex$new(x, k_graph = 15L)
knn <- idx$extract_knn()

NSG index

Description

Navigating spreading-out graph. Builds an NN-Descent kNN graph of degree knn_k first, then refines it into a sparse monotonic graph. Smallest of the graph indices; pays for it with a double build.

Super class

AnnIndex -> NsgIndex

Active bindings

Methods

Public methods

• NsgIndex$new()

• NsgIndex$clone()

NsgIndex$new()

Build the index.

Usage

NsgIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  r = 32L,
  l_build = 100L,
  c = 500L,
  knn_k = 64L,
  ef_search = NULL,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

NsgIndex$clone()

The objects of this class are cloneable with this method.

Usage

NsgIndex$clone(deep = FALSE)

Arguments

References

Fu C, Xiang C, Wang C, Cai D (2019). Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12, 461-474. doi:10.14778/3303753.3303754

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- NsgIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

Relative NN-Descent index

Description

Builds and prunes a navigable graph in one pass, skipping the separate refinement step NsgIndex pays for. r caps the out-degree, ef_search is the recall knob. On Gaussian benchmark data it tops out around 0.97 recall, so check it reaches what you need.

Super class

AnnIndex -> RnnDescentIndex

Active bindings

Methods

Public methods

• RnnDescentIndex$new()

• RnnDescentIndex$clone()

RnnDescentIndex$new()

Build the index.

Usage

RnnDescentIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  s = 20L,
  r = 96L,
  t1 = 4L,
  t2 = 15L,
  n_trees = NULL,
  ef_search = NULL,
  k_search = NULL,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

RnnDescentIndex$clone()

The objects of this class are cloneable with this method.

Usage

RnnDescentIndex$clone(deep = FALSE)

Arguments

References

Ono N, Matsui Y (2023). Relative NN-Descent: a fast index construction for graph-based approximate nearest neighbor search. Proceedings of the 31st ACM International Conference on Multimedia, 1659-1667. doi:10.1145/3581783.3612290

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- RnnDescentIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

SOAR index

Description

IVF with spilling: every point also lands in a second cell, picked by a rule that accounts for the residual it carries in its first. Buys recall at a given nprobe over IvfIndex, but scans about twice the candidates per probe, so compare the two on query time, not on nprobe. No Manhattan.

Super class

AnnIndex -> SoarIndex

Active bindings

Methods

Public methods

• SoarIndex$new()

• SoarIndex$clone()

SoarIndex$new()

Build the index.

Usage

SoarIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine"),
  nlist = NULL,
  nprobe = NULL,
  rule = NULL,
  rule_param = NULL,
  kmeans_iters = NULL,
  kmeans_balanced = FALSE,
  seed = 42L,
  precision = c("float", "double"),
  .verbose = FALSE
)

Arguments

SoarIndex$clone()

The objects of this class are cloneable with this method.

Usage

SoarIndex$clone(deep = FALSE)

Arguments

References

Sun P, Simcha D, Dopson D, Guo R, Kumar S (2023). SOAR: improved indexing for approximate nearest neighbor search. Advances in Neural Information Processing Systems, 36, 3189-3204. https://arxiv.org/abs/2404.00774

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- SoarIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

Vamana index

Description

The flat graph from DiskANN: out-degree r, pruned in two passes with the relaxed-neighbour rule. Builds slower than HnswIndex at its cheapest setting, though the gap closes once you match on recall, and the index is a few per cent smaller.

Super class

AnnIndex -> VamanaIndex

Active bindings

Methods

Public methods

• VamanaIndex$new()

• VamanaIndex$clone()

VamanaIndex$new()

Build the index.

Usage

VamanaIndex$new(
  data,
  metric = c("euclidean", "sqeuclidean", "cosine", "manhattan"),
  r = 48L,
  l_build = 100L,
  alpha_pass1 = 1,
  alpha_pass2 = 1.2,
  ef_search = NULL,
  seed = 42L,
  precision = c("float", "double")
)

Arguments

VamanaIndex$clone()

The objects of this class are cloneable with this method.

Usage

VamanaIndex$clone(deep = FALSE)

Arguments

References

Jayaram Subramanya S, et al. (2019). DiskANN: fast accurate billion-point nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32. https://papers.nips.cc/paper/2019/hash/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Abstract.html

Examples

x <- generate_clustered_data(1000L, 16L)$data
idx <- VamanaIndex$new(x)
res <- idx$predict(x[1:5, ], k = 10L)

Number of threads used for index builds and queries

Description

Number of threads used for index builds and queries

Usage

ann_get_threads()

Value

Integer.

Set the number of threads for index builds and queries

Description

Installs a dedicated thread pool for all subsequent builds and queries. Can be called as often as you like.

Usage

ann_set_threads(n)

Arguments

Value

The previous thread count, invisibly.

Generate synthetic cell embeddings

Description

Foundation-model cell embeddings in the style of Geneformer or scGPT. A large shared mean offset puts every cell inside an anisotropy cone, a few axis-aligned rogue dimensions dominate dot products, each cell type varies in its own low-rank subspace, and a per-cell scale stands in for library size. The nastiest of the four generators.

Usage

generate_cell_embeddings(n, dim, n_clusters = 25L, seed = 42L)

Arguments

Value

A list with:

• data - Numeric matrix, n x dim.

• labels - Integer vector of 1-based cluster labels.

Examples

dat <- generate_cell_embeddings(1000L, 64L, n_clusters = 8L)

Generate clustered synthetic data

Description

Separated Gaussian clusters, with a fifth of the points on thin bridges between neighbouring clusters so the boundaries aren't trivially clean. The baseline of the four generators.

All generators are the ones behind the Rust crate's benchmark tables. They draw in f32 like the crate's gridsearch examples and the Python bindings, so the same seed gives the same points in all three.

Usage

generate_clustered_data(n, dim, n_clusters = 25L, seed = 42L)

Arguments

Value

A list with:

• data - Numeric matrix, n x dim.

• labels - Integer vector of 1-based cluster labels.

Examples

dat <- generate_clustered_data(1000L, 16L, n_clusters = 5L)
table(dat$labels)

Generate correlated synthetic data

Description

Well-separated clusters, each an arbitrarily oriented ellipsoid, plus a globally shared off-axis subspace that correlates the features. None of the structured variance lines up with the coordinate axes, and bridges between neighbouring clusters keep the blobs reachable for graph indices.

Usage

generate_correlated_data(
  n,
  dim,
  n_clusters = 25L,
  cor_strength = 0.5,
  seed = 42L
)

Arguments

Value

A list with:

• data - Numeric matrix, n x dim.

• labels - Integer vector of 1-based cluster labels.

Examples

dat <- generate_correlated_data(1000L, 32L, n_clusters = 5L)

Generate low-rank synthetic data

Description

Cell types on an intrinsic_dim-dimensional manifold, isometrically embedded in dim ambient dimensions with a touch of noise. Types are grouped into lineages, with curved differentiation trajectories running between types of the same lineage.

Usage

generate_low_rank_data(
  n,
  dim,
  n_clusters = 25L,
  intrinsic_dim = 16L,
  seed = 42L
)

Arguments

Value

A list with:

• data - Numeric matrix, n x dim.

• labels - Integer vector of 1-based cluster labels.

Examples

dat <- generate_low_rank_data(1000L, 64L, intrinsic_dim = 8L)

Recall of an approximate kNN result

Description

Fraction of the true k nearest neighbours that the approximate search found, averaged over queries. Order within a row does not matter.

Usage

knn_recall(truth, approx, k = NULL)

Arguments

Value

Numeric between 0 and 1.

Load an index written by ⁠$save()⁠

Description

Reads the index bundle and its R-side parameters (metric, search knobs) back into the matching AnnIndex subclass. The float width is read from the bundle. Bundles are tied to the on-disk format version of the underlying Rust crate; a format bump means rebuilding.

Usage

load_ann_index(dir)

Arguments

Value

An AnnIndex subclass, ready to query.

Query an index

Description

S3 wrapper around the ⁠$predict()⁠ method of an AnnIndex.

Usage

## S3 method for class 'AnnIndex'
predict(object, newdata, k = 15L, ...)

Arguments

Value

A list with idx and dist. See AnnIndex.

Describe an index

Description

Reads the algorithm, precision and shape off an index pointer.

Usage

rs_ann_info(ptr)

Arguments

Value

A list with:

• algo - Algorithm name.

• precision - "float" or "double".

• n - Number of indexed samples.

• dim - Number of features.

Load an index from a directory

Description

Reads a bundle written by rs_ann_save(). Use load_ann_index() instead.

Usage

rs_ann_load(dir, algo)

Arguments

Value

External pointer to the index.

Save an index to a directory

Description

Writes index.bin into dir. Use the ⁠$save()⁠ method instead.

Usage

rs_ann_save(ptr, dir)

Arguments

Value

Invisible NULL.

Build an Annoy index

Description

Use AnnoyIndex instead.

Usage

rs_annoy_build(data, metric, n_trees, seed, precision)

Arguments

Value

External pointer to the index.

Query an Annoy index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_annoy_query(ptr, data, k, search_budget, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an Annoy index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_annoy_self(ptr, k, search_budget, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build a ball tree index

Description

Use BallTreeIndex instead.

Usage

rs_balltree_build(data, metric, seed, precision)

Arguments

Value

External pointer to the index.

Query a ball tree index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_balltree_query(ptr, data, k, search_budget, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query a ball tree index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_balltree_self(ptr, k, search_budget, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Generate synthetic cell embeddings

Description

Foundation-model style cell embeddings: anisotropy cone, rogue dimensions and heavy-tailed spectrum. Use generate_cell_embeddings() instead.

Usage

rs_data_cell_embeddings(n, dim, n_clusters, seed)

Arguments

Value

A list with data (n x dim numeric matrix) and labels (1-based integer cluster labels).

Generate clustered synthetic data

Description

Separated Gaussian clusters joined by inter-cluster bridges. Use generate_clustered_data() instead.

Usage

rs_data_clustered(n, dim, n_clusters, seed)

Arguments

Value

A list with data (n x dim numeric matrix) and labels (1-based integer cluster labels).

Generate correlated synthetic data

Description

Clusters with local anisotropy plus a globally shared off-axis subspace. Use generate_correlated_data() instead.

Usage

rs_data_correlated(n, dim, n_clusters, cor_strength, seed)

Arguments

Value

A list with data (n x dim numeric matrix) and labels (1-based integer cluster labels).

Generate low-rank synthetic data

Description

Cell types on a low-dimensional manifold inside a higher-dimensional space, with trajectories between them. Use generate_low_rank_data() instead.

Usage

rs_data_low_rank(n, dim, intrinsic_dim, n_clusters, seed)

Arguments

Value

A list with data (n x dim numeric matrix) and labels (1-based integer cluster labels).

Build an exhaustive index

Description

Use ExhaustiveIndex instead.

Usage

rs_exhaustive_build(data, metric, precision)

Arguments

Value

External pointer to the index.

Query an exhaustive index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_exhaustive_query(ptr, data, k, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an exhaustive index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_exhaustive_self(ptr, k, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Number of threads used for builds and queries

Description

Use ann_get_threads() instead.

Usage

rs_get_threads()

Value

Integer. The configured pool's size, or Rayon's global pool size.

Build an HNSW index

Description

Use HnswIndex instead.

Usage

rs_hnsw_build(data, metric, m, ef_construction, seed, precision, verbose)

Arguments

Value

External pointer to the index.

Query an HNSW index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_hnsw_query(ptr, data, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an HNSW index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_hnsw_self(ptr, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build an IVF index

Description

Use IvfIndex instead.

Usage

rs_ivf_build(
  data,
  metric,
  nlist,
  kmeans_iters,
  kmeans_balanced,
  seed,
  precision,
  verbose
)

Arguments

Value

External pointer to the index.

Query an IVF index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_ivf_query(ptr, data, k, nprobe, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an IVF index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_ivf_self(ptr, k, nprobe, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build a kd forest index

Description

Use KdTreeIndex instead.

Usage

rs_kdtree_build(data, metric, n_trees, seed, precision)

Arguments

Value

External pointer to the index.

Query a kd forest index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_kdtree_query(ptr, data, k, search_budget, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query a kd forest index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_kdtree_self(ptr, k, search_budget, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build a kMkNN index

Description

Use KmknnIndex instead.

Usage

rs_kmknn_build(
  data,
  metric,
  nlist,
  kmeans_iters,
  kmeans_balanced,
  seed,
  precision,
  verbose
)

Arguments

Value

External pointer to the index.

Query a kMkNN index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_kmknn_query(ptr, data, k, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query a kMkNN index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_kmknn_self(ptr, k, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Recall of an approximate kNN result against ground truth

Description

Use knn_recall() instead.

Usage

rs_knn_recall(truth, approx)

Arguments

Value

Numeric. Mean over queries of the overlap between truth and approx, divided by k. NA entries in approx never count as hits.

Build an LSH index

Description

Use LshIndex instead.

Usage

rs_lsh_build(
  data,
  metric,
  num_tables,
  bits_per_hash,
  slot_bits,
  seed,
  precision
)

Arguments

Value

External pointer to the index.

Query an LSH index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_lsh_query(ptr, data, k, n_probe, max_candidates, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an LSH index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_lsh_self(ptr, k, n_probe, max_candidates, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build an NN-Descent index

Description

Use NNDescentIndex instead.

Usage

rs_nndescent_build(
  data,
  metric,
  k_graph,
  delta,
  diversify_prob,
  max_iter,
  max_candidates,
  n_trees,
  seed,
  precision,
  verbose
)

Arguments

Value

External pointer to the index.

Extract the converged NN-Descent graph

Description

Use the ⁠$extract_knn()⁠ method instead.

Usage

rs_nndescent_extract(ptr, k, include_self, sqrt, return_dist)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Query an NN-Descent index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_nndescent_query(ptr, data, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an NN-Descent index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_nndescent_self(ptr, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build an NSG index

Description

Use NsgIndex instead.

Usage

rs_nsg_build(data, metric, r, l_build, c, knn_k, seed, precision, verbose)

Arguments

Value

External pointer to the index.

Query an NSG index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_nsg_query(ptr, data, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query an NSG index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_nsg_self(ptr, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Build a relative NN-Descent index

Description

Use RnnDescentIndex instead.

Usage

rs_rnndescent_build(
  data,
  metric,
  s,
  r,
  t1,
  t2,
  n_trees,
  seed,
  precision,
  verbose
)

Arguments

Value

External pointer to the index.

Query a relative NN-Descent index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_rnndescent_query(
  ptr,
  data,
  k,
  ef_search,
  k_search,
  sqrt,
  return_dist,
  verbose
)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query a relative NN-Descent index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_rnndescent_self(ptr, k, ef_search, k_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Set the number of threads used for builds and queries

Description

Installs a dedicated Rayon pool. Use ann_set_threads() instead.

Usage

rs_set_threads(n)

Arguments

Value

Invisible NULL.

Build a SOAR index

Description

Use SoarIndex instead.

Usage

rs_soar_build(
  data,
  metric,
  nlist,
  rule,
  rule_param,
  kmeans_iters,
  kmeans_balanced,
  seed,
  precision,
  verbose
)

Arguments

Value

External pointer to the index.

Query a SOAR index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_soar_query(ptr, data, k, nprobe, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query a SOAR index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_soar_self(ptr, k, nprobe, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Subsample queries with noise

Description

Draws rows from x and adds light Gaussian noise. Use subsample_queries() instead.

Usage

rs_subsample_queries(x, n, seed)

Arguments

Value

A numeric matrix with min(n, nrow(x)) rows.

Build a Vamana index

Description

Use VamanaIndex instead.

Usage

rs_vamana_build(
  data,
  metric,
  r,
  l_build,
  alpha_pass1,
  alpha_pass2,
  seed,
  precision
)

Arguments

Value

External pointer to the index.

Query a Vamana index

Description

Use the ⁠$predict()⁠ method instead.

Usage

rs_vamana_query(ptr, data, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Self-query a Vamana index

Description

Use the ⁠$query_self()⁠ method instead.

Usage

rs_vamana_self(ptr, k, ef_search, sqrt, return_dist, verbose)

Arguments

Value

A list with idx (1-based integer matrix) and dist (double matrix or NULL).

Subsample queries from a dataset

Description

Draws rows from x and adds light Gaussian noise (sd 0.05). Querying an index with the rows it was built from flatters it: every query has an exact hit at distance zero. This puts the queries near the data instead of on it. The data is cast to f32 first, as in the Python bindings.

Usage

subsample_queries(x, n, seed = 42L)

Arguments

Value

Numeric matrix with min(n, nrow(x)) rows and ncol(x) columns.

Examples

dat <- generate_clustered_data(1000L, 16L)$data
query <- subsample_queries(dat, 100L)