Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39244
Title: Efficient processing of k nearest neighbor joins using mapreduce
Authors: Lu, W.
Shen, Y.
Chen, S. 
Ooi, B.C. 
Issue Date: 2012
Source: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/39244
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)

63
checked on Dec 15, 2017

Google ScholarTM

Check


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