kd forest index — KdTreeIndex • annsearchR

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.

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

Super class

AnnIndex -> KdTreeIndex

Active bindings

search_budget: Integer or NULL. Candidates inspected per query.

Methods

Inherited methods

`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

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").
n_trees: Integer. Number of trees in the forest.
search_budget: Integer or NULL. Candidates inspected per query. NULL uses k * n_trees * 20. Can be changed after the build.
seed: Integer. Fixes the split dimensions.
precision: String. "float" stores the data as f32, "double" as f64.

`KdTreeIndex$clone()`

The objects of this class are cloneable with this method.

Usage

KdTreeIndex$clone(deep = FALSE)

Arguments

deep: Whether to make a deep clone.

Examples

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