FiDoop-DP: Data Partitioning in Frequent Itemset Mining on Hadoop Clusters
Lists
Only you see this
Abstract
Traditional parallel algorithms for mining frequent itemsets aim to balance load by equally partitioning data among a group of computing nodes. We start this study by discovering a serious performance problem of the existing parallel Frequent Itemset Mining algorithms. Given a large dataset, data partitioning strategies in the existing solutions suffer high communication and mining overhead induced by redundant transactions transmitted among computing nodes. We address this problem by developing a data partitioning approach called FiDoop-DP using the MapReduce programming model. The overarching goal of FiDoop-DP is to boost the performance of parallel Frequent Itemset Mining on Hadoop clusters. At the heart of FiDoop-DP is the Voronoi diagram-based data partitioning technique, which exploits correlations among transactions. Incorporating the similarity metric and the Locality-Sensitive Hashing technique, FiDoop-DP places highly similar transactions into a data partition to improve locality without creating an excessive number of redundant transactions. We implement FiDoop-DP on a 24-node Hadoop cluster, driven by a wide range of datasets created by IBM Quest Market-Basket Synthetic Data Generator. Experimental results reveal that FiDoop-DP is conducive to reducing network and computing loads by the virtue of eliminating redundant transactions on Hadoop nodes. FiDoop-DP significantly improves the performance of the existing parallel frequent-pattern scheme by up to 31 percent with an average of 18 percent.
BibTeX
@article{xun2017fidoop,
author = {Yaling Xun and Jifu Zhang and Xiao Qin and Xujun Zhao},
title = {{FiDoop-DP: Data Partitioning in Frequent Itemset Mining on Hadoop Clusters}},
journal = {IEEE Trans. Parallel Distributed Syst.},
year = {2017},
url = {https://openreview.net/forum?id=61jxz67osA},
}Loading related content...