This program implements several methods for solving the cosine similarity based K-Nearest Neighbor Graph construction problem, including serial and shared-memory parallel implementations for Greedy Filtering [5], kIdxJoin [1], L2Knng [1], and L2KnngApprox [1]. Details for the methods can be found in [1,3].
paper
tarball
README
Contact me via email if you need additional information or find any bugs: danastasiu [atSign] scu [period2] edu.

Please cite the following paper(s) if you make use of this program or any of its components in your research.

David C. Anastasiu & George Karypis. Fast Parallel Cosine K-Nearest Neighbor Graph Construction. In 2016 6th Workshop on Irregular Applications: Architecture and Algorithms (IA3) (IA3 2016), pages 50-53, 2016. 

@inproceedings{anastasiu-sc2016,
   author    = {David C. Anastasiu and George Karypis},
   title     = {Fast Parallel Cosine K-Nearest Neighbor Graph Construction},
   month     = {Nov},
   booktitle = {2016 6th Workshop on Irregular Applications: Architecture and Algorithms (IA3)},
   series    = {IA3 2016},
   year      = {2016},
   pages     = {50-53},
}
David C. Anastasiu and George Karypis. L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning. In 24th ACM International Conference on Information and Knowledge Management, CIKM '15, 2015. 

@inproceedings{anastasiu2015b,
    author = {Anastasiu, David C. and Karypis, George},
    title = {L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning},
    booktitle = {24th ACM International Conference on Information and Knowledge Management},
    series = {CIKM '15},
    year = {2015},
    location = {Melbourne, Australia},
    numpages = {10},
    doi = {http://dx.doi.org/10.1145/2806416.2806534}
}

References:

[1] David C. Anastasiu and George Karypis. L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning. In 24th ACM International Conference on Information and Knowledge Management, CIKM '15, 2015.
[2] David C. Anastasiu and George Karypis. L2ap: Fast cosine similarity search with prefix l-2 norm bounds. In 30th IEEE International Conference on Data Engineering, ICDE '14, 2014.
[3] David C. Anastasiu & George Karypis. Fast Parallel Cosine K-Nearest Neighbor Graph Construction. In Proceedings of the 6th Workshop on Irregular Applications: Architectures and Algorithms, in conjunction with SC'16 (IA3 2016), ACM, 2016.
[4] Roberto J. Bayardo, Yiming Ma, and Ramakrishnan Srikant. 2007. Scaling up all pairs similarity search. In Proceedings of the 16th international conference on World Wide Web (WWW '07). ACM, New York, NY, USA, 131-140.
[5] Youngki Park, Sungchan Park, Sang-goo Lee, and Woosung Jung. Greedy filtering: A scalable algorithm for k-nearest neighbor graph construction. In Database Systems for Advanced Applications, volume 8421 of Lecture Notes in Computer Science, pages 327-341. Springer-Verlag, 2014.
[6] Venu Satuluri and Srinivasan Parthasarathy. 2012. Bayesian locality sensitive hashing for fast similarity search. Proc. VLDB Endow. 5, 5 (January 2012), 430-441.