PARMA: a parallel randomized algorithm for approximate association rules mining in MapReduce," presented at the

Frequent Itemsets and Association Rules Mining (FIM) is a key task in knowledge discovery from data. As the dataset grows, the cost of solving this task is dominated by the component that de-pends on the number of transactions in the dataset. We address this issue by proposing PARMA, a parallel algorithm for the MapRe-duce framework, which scales well with the size of the dataset (as number of transactions) while minimizing data replication and communication cost. PARMA cuts down the dataset-size-dependent part of the cost by using a random sampling approach to FIM. Each machine mines a small random sample of the dataset, of size in-dependent from the dataset size. The results from each machine are then filtered and aggregated to produce a single output collec-tion. The output will be a very close approximation of the collec-tion of Frequent Itemsets (FI’s) or Association Rules (AR’s) with their frequencies and confidence levels. The quality of the output is probabilistically guaranteed by our analysis to be within the user-specified accuracy and error probability parameters. The sizes of the random samples are independent from the size of the dataset, as is the number of samples. They depend on the user-chosen ac-curacy and error probability parameters and on the parallel compu-tational model. We implemented PARMA in Hadoop MapReduce and show experimentally that it runs faster than previously intro-duced FIM algorithms for the same platform, while 1) scaling al-most linearly, and 2) offering even higher accuracy and confidence than what is guaranteed by the analysis