The k-nearest neighbor graph is an important structure in many data mining methods for clustering,  advertising, recommender  systems, and outlier detection. Constructing the graph requires computing up to

n2 similarities for a set of n objects. This high complexity has led researchers to seek approximate methods, which find many but not all of the nearest neighbors for each object in the set. In contrast, we  leverage shared memory parallelism and recent advances in computing similarity joins to solve the problem exactly, via a filtering based approach. Our method considers all pairs of potential neighbors but quickly filters pairs that could not be a part of the k-nearest neighbor graph, based on similarity upper bound estimates. The filtering is data dependent and not easily predicted, which poses load  balance challenges in a parallel setting. We evaluated our solution on several real-world datasets and found that, using 16 threads, our method achieves up to 12.9x speedup over our exact baseline and is sometimes faster even than approximate methods. Moreover, an approximate version of our method is up to 21.7x more efficient than the best approximate state-of-the-art baseline at similar high recall. Our method displays linear strong scaling characteristics and filtering incurs less than 1% load imbalance.