knn: K Nearest Neighbors

Description

Adapted K nearest neighbors based on RcppHNSW

Usage

knn(
  query,
  ref,
  k,
  distance = "euclidean",
  same = FALSE,
  threads = 1L,
  verbose = FALSE,
  progress = FALSE,
  ...
)

Value

A data.table with three columns describing the indices of the query, ref, and k neighbors and the distances.

Arguments

query: A data.table containing the set of query points where each row represent a point and each column a given coordinate.
ref: A numeric containing the set of reference points where each row represent a point and each column a given coordinate.
k: An integer describing the number of nearest neighbors to search for.
distance: Type of distance to calculate. "euclidean" as default. Look hnsw_knn for more options.
same: Logic. If TRUE, it delete neighbors with distance of 0, useful when the k search is based on the same query.
threads: An integer specifying the number of threads to use for parallel processing. Experiment to see what works best for your data on your hardware.
verbose: If TRUE, log messages to the console.
progress: If TRUE, log a progress bar when verbose = TRUE. Tracking progress could cause a small overhead.
...: Arguments passed to hnsw_build and hnsw_search.

Author

J. Antonio Guzmán Q.

Details

This function is based on hnswlib C++ library (Malkov & Yashunin 2016) and its bindings for R (RcppHNSW; Melville 2020) for a fast estimation of neighbors points. It is adapted to simplify the workflow within rTLS. If you use this function, please consider cite the C++ library and RcppHNSW package.

References

Malkov, Y. A., & Yashunin, D. A. (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv preprint arXiv:1603.09320.

Examples

Run this code


#Point cloud
data("pc_tree")

#knn search using k = 3
knn(pc_tree, pc_tree, k = 3, same = TRUE)

Run the code above in your browser using DataLab