L2Knng: Fast K-Nearest Neighbor Graph Construction with L2-Norm Pruning
L2Knng is a program that provides high-performance implementations of several methods for constructing the K-nearest neighbor graph of a set of vectors based on cosine similarity. These vectors are often sparse and high-dimensional, e.g., document-term vectors, user-item ratings, etc. The methods that are implemented include approaches developed by our group that prune the search space using L2 norm bounds (L2Knng, L2KnngApprox, and kL2AP) and various other state-of-the-art approaches such as Greedy Filtering, Maxscore, BMM, and kIdxJoin.
L2Knng can be downloaded from here.