Academic
Publications
Efficient k-nearest neighbor graph construction for generic similarity measures

Efficient k-nearest neighbor graph construction for generic similarity measures,10.1145/1963405.1963487,Wei Dong,Charikar Moses,Kai Li

Efficient k-nearest neighbor graph construction for generic similarity measures  
BibTex | RIS | RefWorks Download
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.
Conference: World Wide Web Conference Series - WWW , pp. 577-586, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.