Efficient Parallel kNN Joins for Large Data in MapReduce
by Chi Zhang, Feifei Li, Jeffrey Jestes.
This paper was published in EDBT 2012. It will be presented in the Test-of-time award session on Thursday, March 31.
This paper proposes MapReduce-based algorithms for kNN join query processing, as well as an approximate algorithm with theoretical guarantees. The impact of this paper goes far beyond the original MapReduce context, and has influenced algorithms and systems work in the data management community, and has also impacted data mining, distributed processing, communications and control. This paper is also frequently used in teaching, and it has attracted the highest number of citations among the papers published in EDBT 2012, by a wide margin.