Efficient Processing of k Nearest Neighbor Joins using MapReduce
By Wei Lu, Yanyan Shen, Su Chen, Beng Chin Ooi. Proceedings of the VLDB Endowment, 2012
297 citations recorded by the source corpus.
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 applications. 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 computers. 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 computational costs. To reduce the shuffling cost, we propose two approximate algorithms to minimize the number of replicas. Extensive experiments on our in-house cluster demonstrate that our proposed methods are efficient, robust and scalable.
Subfields: Artificial Intelligence, Information Systems, Signal Processing
View Paper: https://www.semanticscholar.org/paper/02837c4b66da1288e30e9f5012fbf7cb68e67ad5
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Information Systems
In Signal Processing
Citations in the corpus
- SpatialHadoop: A MapReduce framework for spatial data (2015, background): “(4) All NN (ANN) query [21], where points are partitioned according to their Z-values to find the answer similar to kNN queries.”