An Efficient Algorithm of Frequent Itemsets Mining Based on MapReduce

Le WangJournal of Information and Computational Science 2014 · DOI

TL;DR

This paper introduces FIMMR, a novel MapReduce-based algorithm for efficiently mining frequent itemsets in large datasets. By first identifying local frequent itemsets as candidates and then applying aggressive pruning strategies, FIMMR significantly outperforms existing parallel algorithms like PFP and SPC, especially for smaller minimum support thresholds.

What Problem Does This Paper Address?

The paper tackles the challenge of efficiently mining frequent itemsets from massive datasets, a fundamental task in data mining. Traditional algorithms like Apriori and FP-Growth, while effective on smaller datasets, struggle with the scalability demands of "big data." To address this, parallel algorithms leveraging the MapReduce framework have been developed. However, existing MapReduce implementations of FP-Growth suffer from uneven data distribution, and Apriori-based approaches generate an excessive number of intermediate key-value pairs, both leading to performance bottlenecks. This paper aims to bridge this gap by proposing a more efficient and scalable MapReduce algorithm.

Methods

FIMMR employs a two-round MapReduce approach.

  • Round 1: Candidate Mining: This round focuses on identifying potential frequent itemsets. The dataset is divided into chunks, and local frequent itemsets are mined from each chunk using either FP-Growth or Apriori. These local frequent itemsets serve as candidates for global frequent itemsets. A key aspect here is the use of a lower local minimum support threshold (e.g., 0.9 * global minSup) to ensure that no global frequent itemsets are missed.
  • Pruning Strategies: Before the second round, FIMMR applies several pruning strategies to reduce the number of candidates. These strategies leverage lemmas and theorems related to itemset support and subset properties to eliminate non-frequent itemsets early on. This is a crucial innovation that distinguishes FIMMR.
  • Round 2: Global Frequent Itemset Identification: The remaining candidates are then processed in a second MapReduce round to accurately calculate their global support across the entire dataset and identify the true frequent itemsets.

Datasets

The paper evaluates FIMMR on two synthetic datasets generated by the IBM data generator:

  • T20.110.D10000K
  • T40.I20.D5000K

The parameters indicate:

  • T: Average length of transaction itemsets.
  • I: Average length of maximal potentially large itemsets.
  • D: Total number of transactions.

The datasets were cut into 24 pieces with equal sizes to utilize the 24 data nodes in their experimental cluster.

Key Insights and Ideas

  • Local Candidates + Global Pruning = Efficiency: The core idea of mining local frequent itemsets as candidates and then aggressively pruning them before a global count is highly effective. This avoids the overhead of generating and processing a massive number of candidates.
  • Lower Local Support is Key: Using a local minimum support threshold that is slightly lower than the global threshold is essential to guarantee that no true frequent itemsets are missed during the initial local mining phase.
  • Pruning is a Game Changer: The paper emphasizes that the pruning strategies are critical. In many cases, these strategies can reduce the candidate set to null, making the second MapReduce round unnecessary, leading to significant performance gains.
  • Stability Under Varying Support: FIMMR shows more stable performance compared to PFP and SPC, especially as the minimum support threshold decreases, a common scenario in big data mining.

Key Results

  • Significant Speedup: FIMMR consistently outperforms PFP and SPC in terms of running time across different minimum support thresholds and dataset sizes.
  • Order of Magnitude Improvement: Under small minimum support thresholds, FIMMR achieves an improvement of "one order of magnitude" (i.e., 10x faster) compared to the other algorithms.
  • Satisfactory Speedup: The algorithm demonstrates satisfactory speedup when scaling to larger clusters, approaching ideal linear speedup, though not perfectly due to communication overhead.
  • Reduced Candidate Set: The pruning strategies effectively reduce the number of candidates, often to the point where the second MapReduce round is skipped.

Limitations and Future Work

  • Not Discussed in the Paper: The paper does not explicitly detail limitations or future work beyond the general statement that FIMMR's speedup is satisfactory. However, one could infer that further optimization of the pruning strategies or exploration of different local mining algorithms within FIMMR could be avenues for future research. The reliance on existing FP-Growth or Apriori for local mining means its performance is indirectly tied to those algorithms' strengths and weaknesses.

Summary updated

Abstract

Mainstream parallel algorithms for mining frequent itemsets (patterns) were designed by implementing FP-Growth or Apriori algorithms on MapReduce (MR) framework. Existing MR FP-Growth algorithms can not distribute data equally among nodes, and MR Apriori algorithms utilize multiple map/reduce procedures and generate too many key-value pairs with value of 1; these disadvantages hinder their performance. This paper proposes an algorithm FIMMR: it firstly mines local frequent itemsets for each data chunk as candidates, applies prune strategies to the candidates, and then identifies global frequent itemsets from candidates. Experimental results show that the time efficiency of FIMMR outperforms PFP and SPC significantly; and under small minimum support threshold, FIMMR can achieve one order of magnitude improvement than the other two algorithms; meanwhile, the speedup of FIMMR is also satisfactory.
BibTeX
@article{wang2014efficient,
  author = {Le Wang},
  title = {{An Efficient Algorithm of Frequent Itemsets Mining Based on MapReduce}},
  journal = {Journal of Information and Computational Science},
  year = {2014},
  doi = {10.12733/jics20103619},
}
Figure