kMkNN index

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.

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

Super class

AnnIndex -> KmknnIndex

Methods

Public methods

• KmknnIndex$new()

• KmknnIndex$clone()

Inherited methods

• AnnIndex$predict()
• AnnIndex$print()
• AnnIndex$query_self()
• AnnIndex$save()

---

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

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").

nlist

Integer or NULL. Number of k-means clusters. NULL uses sqrt(n).

kmeans_iters

Integer or NULL. Lloyd iterations. NULL uses 30.

kmeans_balanced

Boolean. Reseed starved centroids each iteration.

seed

Integer. Fixes the k-means initialisation.

precision

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

.verbose

Boolean. Print build progress from Rust.

---

KmknnIndex$clone()

The objects of this class are cloneable with this method.

Usage

KmknnIndex$clone(deep = FALSE)

Arguments

deep

Whether to make a deep clone.

Examples

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