Please use this identifier to cite or link to this item:
Title: Efficient processing of k nearest neighbor joins using mapreduce
Authors: Lu, W.
Shen, Y.
Chen, S. 
Ooi, B.C. 
Issue Date: 2012
Citation: Lu, W.,Shen, Y.,Chen, S.,Ooi, B.C. (2012). Efficient processing of k nearest neighbor joins using mapreduce. Proceedings of the VLDB Endowment 5 (10) : 1016-1027. ScholarBank@NUS Repository.
Abstract: 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.
Source Title: Proceedings of the VLDB Endowment
ISSN: 21508097
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on May 25, 2023

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.