Package smile.neighbor
The simplest solution to the NNS problem is to compute the distance from the query point to every other point in the database, keeping track of the "best so far". This algorithm, sometimes referred to as the naive approach, has a running time of O(Nd) where N is the cardinality of S and d is the dimensionality of M. There are no search data structures to maintain, so linear search has no space complexity beyond the storage of the database. Surprisingly, naive search outperforms space partitioning approaches on higher dimensional spaces.
Space partitioning, a branch and bound methodology, has been applied to the problem. The simplest is the kd tree, which iteratively bisects the search space into two regions containing half of the points of the parent region. Queries are performed via traversal of the tree from the root to a leaf by evaluating the query point at each split. Depending on the distance specified in the query, neighboring branches that might contain hits may also need to be evaluated. For constant dimension query time, average complexity is O(log N) in the case of randomly distributed points. Alternatively the Rtree data structure was designed to support nearest neighbor search in dynamic context, as it has efficient algorithms for insertions and deletions.
In case of general metric space branch and bound approach is known under the name of metric trees. Particular examples include vptree and BKtree.
Locality sensitive hashing (LSH) is a technique for grouping points in space into 'buckets' based on some distance metric operating on the points. Points that are close to each other under the chosen metric are mapped to the same bucket with high probability.
The cover tree has a theoretical bound that is based on the dataset's doubling constant. The bound on search time is O(c12 log n) where c is the expansion constant of the dataset.

ClassDescriptionBKTree<K,
V> A BKtree is a metric tree specifically adapted to discrete metric spaces.CoverTree<K,V> Cover tree is a data structure for generic nearest neighbor search, which is especially efficient in spaces with small intrinsic dimension.KDTree<E>A KDtree (short for kdimensional tree) is a spacepartitioning dataset structure for organizing points in a kdimensional space.KNNSearch<K,V> Retrieves the top k nearest neighbors to the query.LinearSearch<K,V> Brute force linear nearest neighbor search.LSH<E>LocalitySensitive Hashing.MPLSH<E>MultiProbe LocalitySensitive Hashing.MutableLSH<E>Mutable LSH.Neighbor<K,V> The immutable object encapsulates the results of nearest neighbor search.RNNSearch<K,V> Retrieves the nearest neighbors to a query in a radius.SNLSH<K,V> LocalitySensitive Hashing for Signatures.