Nearest-Neighbor Descent (NN-Descent)
is a simple yet efficient algorithm for approximate K-Nearest Neighbor Graph (K-NNG) construction with arbitrary similarity measures or distance measures. Our method is based on local search, has minimal space overhead, and does not rely on any shared global index. Hence, it is especially suitable for large-scale applications where data structures need to be distributed over the network. We have shown with a variety of datasets and similarity measures that the proposed method typically converges to above 90% recall with each point comparing only to several percent of the whole dataset on average