Efficient Processing of k Nearest Neighbor Joins using

k nearest neighbor join (kNN join), designed to find k nearest neighbors from a dataset S for every object in another dataset R, is a primitive operation widely adopted by many data mining ap-plications. As a combination of the k nearest neighbor query and the join operation, kNN join is an expensive operation. Given the increasing volume of data, it is difficult to perform a kNN join on a centralized machine efficiently. In this paper, we investigate how to perform kNN join using MapReduce which is a well-accepted framework for data-intensive applications over clusters of comput-ers. In brief, the mappers cluster objects into groups; the reducers perform the kNN join on each group of objects separately. We design an effective mapping mechanism that exploits pruning rules for distance filtering, and hence reduces both the shuffling and com-putational costs. To reduce the shuffling cost, we propose two ap-proximate algorithms to minimize the number of replicas. Exten-sive experiments on our in-house cluster demonstrate that our pro-posed methods are efficient, robust and scalable. 1