Efficient Parallel kNN Joins for Large Data in MapReduce
[Overview] [Papers and Talks] [Source Code]
[Dataset] [Contacts]
In data mining applications and spatial and multimedia databases, a
useful tool is the kNN join, which is to produce the k nearest
neighbors (NN), from a dataset S, of every point in a dataset
R. Since it involves both the join and the NN search, performing
kNN joins efficiently is a challenging task. Meanwhile,
applications continue to witness a quick (exponential in some cases)
increase in the amount of data to be processed. A popular model
nowadays for large-scale data processing is the shared-nothing
cluster on a number of commodity machines using MapReduce
. Hence, how to execute kNN joins efficiently
on large data that are stored in a MapReduce cluster is an
intriguing problem that meets many practical needs. This work
proposes novel (exact and approximate) algorithms in MapReduce to
perform efficient parallel kNN joins on large data. We demonstrate
our ideas using Hadoop. Extensive experiments in large real and
synthetic datasets, with tens or hundreds of millions of records in
both R and S and up to 30 dimensions, have demonstrated the
efficiency, effectiveness, and scalability of our methods.
1. Efficient Parallel kNN Joins for Large Data in MapReduce
Full version:
Talk:
Important Notice
If you use this library for your work, please kindly cite our paper. Thanks!
If you find any bugs or any suggestions/comments,
we are very happy to hear from you!
Library Description
The library is developed in Java for use with Hadoop 0.20.2. The code is self-explanatory. Makefiles are included to compile the library into jar files. The classpath in the makefile should be updated to refer to the Hadoop 0.20.2 jar file and the Apache Commons Logging jar file.
Our library requires third party libraries please refer to readme.txt contained in the source code tarball file for detailed information.
Download
kNN Joins MapReduce Library [tar.bz2]
Quick Install
Hadoop 0.20.2 may be obtained from here and Apache
Commons Logging may be obtained from here. After obtaining both, update
the makefiles as mentioned above in order to compile. As an example, the library may be invoked by specifying the command:
hadoop jar knn.jar test.BPhase1
A detailed description of command line arguments is displayed.
The dataset used in this paper is not available right now.
Chi Zhang Jeffrey Jestes Feifei Li