document: Efficient k-nearest neighbor graph construction for generic similarity measures K-Nearest Neighbor Graph ( K-NNG ) construction is an important operation with many web related applications , including collaborative filtering , similarity search , and many others in data mining and machine learning . Existing methods for K-NNG construction either do not scale , or are specific to certain similarity measures . We present NN-Descent , a simple yet efficient algorithm for approximate K-NNG construction with arbitrary similarity 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 .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O