Multicore framework for finding frequent item-sets using tds

Abstract

Mining of frequent items from a dataset is a prime problem in the field of data mining. It plays a pivotal role in many of the data mining applications. In recent years, technological improvements have provided us with cheaper storage spaces capable of handling gigantic amount of digital data of human activities. This humongous data becomes a bottleneck for data analysts as mining algorithms often suffer from performance issues while running larger datasets or where number of items become very large. In this paper, we propose a novel tree based data structure (TDS) for saving itemsets as candidates for time effective application of Apriori property for pruning. The TD structure shows significant improvement in timing as compared to traditional structure. Furthermore, we propose a multicore framework for the processing of TDS based Apriori Algorithm. The framework is based on divide and conquer approach, where all cores work in parallel on their allocated subset of data. Each core shares their local results with other cores to get the global results leading to a collaborative working environment. The proposed framework is highly scalable which requires no change in the overall working of the algorithm. In order to thoroughly test the proposed framework, experimentation is performed using 4 benchmark datasets and its evaluation is carried out on the bases of number of cycles, execution time and comparative speedup. The results indicate that TDS is significantly faster and while working with multicore framework a direct relationship exists in speedup for all datsets with the number of working cores.

Keywords Data mining, Apriori, Parallel processing, Multiple core, Accelerator