$k$ NN-DP: Handling Data Skewness in $kNN$ Joins Using MapReduce

In this study, we discover that the data skewness problem imposes adverse impacts on MapReduce-based parallel kNN-join operations running clusters. We propose a data partitioning approach-called kNN-DP-to alleviate load imbalance incurred by data skewness. The overarching goal of kNN-DP is to equally divide data objects into a large number of partitions, which are processed by mappers and reducers in parallel. At the heart of kNN-DP is a data partitioning module, which dynamically and judiciously partitions data to optimize kNN-join performance by suppressing data skewness on Hadoop clusters. Data partitioning decisions largely depends on data properties (e.g., distributions), the analysis of which is highly expensive for a massive amount of data. To speed up the data-property analysis, we incorporate a sampling technique to profile the data distribution of a small sample dataset representing big datasets. After building a data-partitioning cost model for parallel kNN-joins, we derive the time-complexity upper and lower bounds of parallel kNN-join algorithms. The cost model offers us a guidance to systematically investigate kNN-DP's performance. kNN-DP obtains global nearest neighbors using local nearest neighbors. To improve the accuracy of such an approximation solution, we augment each node's local data by a small amount of redundant data. We develop two kNN-DP-based schemes called LSH+ and z-value+, which seamlessly integrate kNN-DP with the existing LSH and z-value algorithms for kNN-join computing. We implement and evaluate LSH+ and z-value+ on a 24-node Hadoop cluster driven by both synthetic and real-world high-dimensional datasets. The experimental results show that kNN-DP significantly improves the performance of LSH and z-value while offering high extensibility and scalability on Hadoop clusters.