A novel KNN join algorithms based on Hilbert R-tree in MapReduce
Authors:
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 417-420
Abstract
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.Keywords
This publication has 6 references indexed in Scilit:
- Efficient processing of k nearest neighbor joins using MapReduceProceedings of the VLDB Endowment, 2012
- Efficient parallel kNN joins for large data in MapReduce2012
- MapReduceCommunications of the ACM, 2008
- GORDER2004
- Supporting KDD Applications by the k-Nearest Neighbor Join2003
- Algorithm AS 136: A K-Means Clustering AlgorithmJournal of the Royal Statistical Society Series C: Applied Statistics, 1979