A novel KNN join algorithms based on Hilbert R-tree in MapReduce

The kNN join (k nearest neighbor join) is a primitive operation widely adopted by many data mining applications. From a dataset S, it can find k nearest neighbors for every object in another dataset R. It is a combination of the k nearest neighbor query and the join operation. In this paper we perform kNN join in MapReduce. For kNN joins, the block nested loop methodology is the direct method. It is very efficient to load a R-tree and search kNN in R-tree. On the base, we build a Hilbert R-tree index for the local S block in a bucket. It can help us find kNNs in the same bucket. Extensive experiments demonstrate that our proposed methods are efficient.