Nearest Neighbor Descent (NN-Descent)

Compute k-nearest neighbors exactly or approximate k-nearest neighbors efficiently.

Given a dataset X, a set of query points Y, and a positive integer K, KnnFind.Run finds the closest K neighbors in X for each query point in Y. Type "doc KnnFind" to see explanations of the code and an example of usage.

This submission expands upon the built-in MATLAB function knnsearch.m by adding a new option for 'NSMethod' called 'nn_descent'. This method, known as nearest neighbor descent (NN-descent), allows for a much more rapid computation of the K-nearest neighbors, with the cost that the return value may not be 100% correct (making this an "approximate" neighbor search). The returned result of NN-descent often matches the exact answer with 99% accuracy.

The NN-descent algorithm is the invention of Wei Dong, Moses Charikar, and Kai Li. See their original paper for a detailed description (https://www.cs.princeton.edu/cass/papers/www11.pdf).

Very roughly speaking, NN-descent works by beginning with an initial "guess" of the K nearest neighbors for each point, then improving the guess iteratively by computing the distance from the point to neighbors of its neighbors (instead of the entire dataset!) and updating accordingly. This implementation is also enhanced by initializing the NN-descent guesses with leaves of a random projection forest (see https://cseweb.ucsd.edu/~dasgupta/papers/rptree-stoc.pdf).

This implementation of NN-descent is mostly adapted from a Python implementation authored by Leland McInnes, and many functions and variables share the same name. See his page (https://libraries.io/github/lmcinnes/pynndescent) for the latest version of his code.

This implementation is accelerated by calling the C++ MEX function nn_descent.mex. Due to File Exchange requirements, users must download the MAC or Windows MEX binary file separately (the option to download will appear upon calling KnnFind.Test) or build the MEX file using their own compiler. To get the MEX file for Linux run KnnFind.Build after setting up your C++ compiler. All source code for this MEX file is provided as fully open source.

Provided by the Herzenberg Lab at Stanford University.