NN-DP: Handling Data Skewness inJoins Using MapReduce

Xujun Zhao, Jifu Zhang, Xiao QinIEEE TPDS 2018 · OpenReview

Abstract

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.
BibTeX
@article{zhao2018nn,
  author = {Xujun Zhao and Jifu Zhang and Xiao Qin},
  title = {{NN-DP: Handling Data Skewness inJoins Using MapReduce}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2018},
  url = {https://openreview.net/forum?id=1qNt4BCDPt},
}

Loading related content...

Figure