Skip to contents

NSG index

Source: R/indices_graph.R
NsgIndex.Rd

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.

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

Super class

AnnIndex -> NsgIndex

Active bindings

ef_search

Integer or NULL. Beam width at query time.

Methods

Public methods

Inherited methods

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

data

Numeric matrix or data.frame. Samples x features. An index pointer is also accepted; load_ann_index() uses that path.

metric

String. One of c("euclidean", "sqeuclidean", "cosine", "manhattan").

r

Integer. Maximum out-degree of the refined graph.

l_build

Integer. Candidate list width while refining.

c

Integer. Candidate pool size per node before pruning.

knn_k

Integer. Degree of the NN-Descent graph built first. Wants to be comfortably above r.

ef_search

Integer or NULL. Beam width at query time. NULL uses 100. Can be changed after the build.

seed

Integer. Fixes the initial graph and navigating node.

precision

String. "float" stores the data as f32, "double" as f64.

.verbose

Boolean. Print build progress from Rust.

NsgIndex$clone()

The objects of this class are cloneable with this method.

Usage

NsgIndex$clone(deep = FALSE)

Arguments

deep

Whether to make a deep clone.

Examples

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