# New and Efficient Algorithms for Producing Frequent Itemsets with the Map-Reduce Framework
## 4 Incremental Frequent Itemset Mining with Map-Reduce
### The Algorithms
#### 4.2.4 Map-Reduce Optimized Algorithm
All optimizations discussed in Section 4.2.2 should be also applied in this combined step. The next job that would be removed is the recounting step in \(\Delta\) (Steps 12-13). The only itemsets that could be qualified for this output are itemsets that were not frequent in \(\Delta\), and were frequent in \(\mathcal{D}\). We suggest counting all itemsets from \(\text{FI}(\mathcal{D})\) during Step 3 of FIM in \(\Delta\), as there is already a pass over \(\Delta\) anyway. IMRApriori phase 2 could be enhanced to do the counting not only for new candidates, but also for \(\text{FI}(\mathcal{D})\). The updated algorithm is depicted in Figure 8.  
Our performance evaluation also revealed additional conditions when the incremental algorithm performs worse than the non-incremental one. It happens when the input for a Split is very small, and the minimum support level is also small. Under such conditions, the minimum required occurrences for an itemset to become candidate for frequent itemset is very low--it may be as low as a single transaction, and then almost all combinations of items would become candidates. Such a small job may run longer than mining the whole \(\mathcal{D}^{+}\) with non-incremental FIM. To overcome this problem, we propose few simple but effective techniques:  
1. When the \(\Delta\) is being split by the MR framework to Splits, it is being split to chunks of equal predefined sizes. Only the last chunk may be of different size. We need to make sure that the last chunk is larger than the previous chunk (rather than smaller). Fortunately, MR systems, like Hadoop, do append the last smaller input part to a previous chunk of predefined size. So, the last Split is actually larger than the others. 2. If the total input divided by the minimum Split amounts is still too small, it is preferable to manually control the number of Splits. In most cases, it is better to sacrifice parallel computation for gaining speed with less workers or even using a single worker. Once again, it is possible to control the splitting process in Hadoop's system via the configuration parameters. 3. If \(\Delta\) is still very small for a single worker to process it effectively, it is better to use a non-incremental algorithm for the calculation of \(\mathcal{D}^{+}\). The detection of Split sizes, configuration of Split number, and deciding which algorithm to use could be implemented in the main driver of the MR algorithm. Merging MR jobs into one, allowed us to achieve an algorithm that has only two steps. The first step is the Map-Reduce FIM step for \(\Delta\) only. For comparison, the non-incremental algorithm would have a Map-Reduce FIM calculation for the much bigger \(\mathcal{D}^{+}\). The second step is the optional step of counting candidates in the old \(\mathcal{D}\) (at most one pass over old \(\mathcal{D}\)), and it is triggered only when there is an itemset that must be recounted in the old \(\mathcal{D}\). The price for our algorithm is a slightly more complicated FIM input and output step.