# 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  
There are few known drawbacks of the Map-Reduce framework [4; 38] that can harm the performance of any algorithm. We will concentrate on the overhead of establishing a new computational job, creation of a physical process for the Mapper and the Reducer, on each of the distributed machines, and I/O consumption when it needs to read or write data from/to a remote location, e.g., read input from HDFS. Our performance evaluation (see Section 4.3) of the General Scheme, even with the early pruning optimization, showed that the CPU time of the algorithms is lower compared to the full process of \begin{table}
\begin{tabular}{c c c} \hline \hline  & \(\mathbf{Split_{1}}\) & \(\mathbf{Split_{2}}\) \\ \hline Transaction count & \(|Split_{1}|\) = 501 & \(|Split_{1}|\) = 500 \\ Min support level & \(501*0.2=\) 101 & \(500*0.2=\) 100 \\ A Count in the Split as found by & & \\ the relevant mapper & 101 & Unknown (not locally frequent) \\ _mincount_ of A & 101 & 0 (may not appear at all) \\ _mxxcount_ of A & 101 & \(100\,-\,1\,=\,99\) \\ Total _mincount_ of A & 101 & \\ Total _maxcount_ of A & 200 & Less than \(\mathcal{D}\) min support level \\  & & (201). Pruned away. \\ B Count in the Split as found by & & \\ the relevant mapper & 101 & 100 \\ _mincount_ of B & 101 & 100 \\ _maxcount_ of B & 101 & 100 \\ Total _mitcount_ of B & 201 & Frequent in \(\mathcal{D}\) \\ Total _maxcount_ of B & 201 & \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Early pruning example values for \(\mathcal{D}\). \begin{table}
\begin{tabular}{c c c} \hline \hline  & \(\Delta\) & \(\mathcal{D}\) \\ \hline
**A Count** & 5 & Unknown (was pruned) \\ _mitcount_ A & 5 & 0 \\ _maxcount_ A & 5 & \(201-1=200\) \\ Total _mincount_ of A & 5 & \\ Total _maxcount_ of A & 205 & Could be frequent in \(\mathcal{D}^{+}\) \\ \hline
**B Count** & 0 & 201 (was frequent in \(\mathcal{D}\)) \\ _mitcount_ B & 0 & 201 \\ _maxcount_ B & 0 & 201 \\ Total _mitcount_ of B & 201 & Less than minimum support level of \(\mathcal{D}^{+}\). Pruned away. \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Early pruning example values for incremental D and \(\Delta\). from scratch, but parallel run time could be the same. It happens for databases that are small, and that their delta is also small. The first reason for this is that the Incremental Scheme has many more MR jobs compared to non-incremental FIM. The overhead of job creation time for each of the jobs is summed, and if it is of the same degree as the total algorithm time (happens for small databases/deltas), there could be no benefit for the incremental algorithm run time (although each machine in the cluster runs faster and consumes less energy). Another reason is that the general scheme needs to read the \(\Delta\) several times from a remote location as it is required as the input for different jobs. In the non-incremental FIM algorithm, the number of I/O reads of whole \(\mathcal{D}^{+}\) (\(\mathcal{D}\) and \(\Delta\)) is dependent on the underlying FIM algorithm, and the later output of \(\text{FI}(\mathcal{D}^{+})\). In the General Scheme, the same FIM is executed only on \(\Delta\) with an output of \(\text{FI}(\Delta)\), but there is also the requirement to read all \(\text{FI}(\Delta)\) back from the network disk to join it with \(\text{FI}(\mathcal{D})\). Moreover, it is required to read the whole \(\Delta\) again for the recounting step. To work around these limitations of the Incremental Scheme, we suggest reducing the number of jobs that are used in the General Scheme. It will allow us to reduce start times, and will imply less I/O communication. We will start with the observation that the Join job (Steps 7-8 of Algorithm 5) is required to read the output of the previous FIM job (Step 4) immediately. We suggest merging the FIM output of Step 4 with the Join job. It should receive an additional input (\(\text{FI}(\mathcal{D})\)), and instead of writing \(\text{FI}(\Delta)\), it will \"join\" the results. It will still have three outputs like the original Join job.