# 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.2 Early Pruning Optimizations  
In the scheme described above, only one step requires accessing the old \(\mathcal{D}\), whose size may be huge compared to \(\Delta\). This is the step of recounting local frequent itemsets from \(\Delta\), which did not appear to be in FI(\(\mathcal{D}\)). To minimize access to the old \(\mathcal{D}\), we suggest using early pruning techniques which consider the relation between the old \(\mathcal{D}\) size and the \(\Delta\) size. These techniques are additions to the early pruning of the IMRApriori technique but are not unique for Map-Reduce algorithms, and could be used in every incremental FIM algorithm. All of the following lemmas are trying to numerically determine the potential of a candidate itemset to be frequent as soon as possible. Let \(inc\) be the size of \(\Delta\) relative to the size of \(\mathcal{D}\). Let \(n\) be the size of \(\mathcal{D}\) (n =\(|\mathcal{D}|\)); then, the size of \(\Delta\) is \(inc*n\) or \(inc*|\mathcal{D}|\). Observation 1:  
\[xeFI\big{(}\mathcal{D}^{+},minSup\big{)}\to sup_{\mathcal{D}^{+}}(x)\geq minSup* (|\mathcal{D}|+inc*|\mathcal{D}|)\]  
**Proof. **  
\[ \begin{array}{l}sup_{\mathcal{D}}(x)+sup_{\Delta}(x)=sup_{\mathcal{D}^{+}}( x)\geq minSup*|\mathcal{D}^{+}|=minSup*(|\mathcal{D}|+|\Delta|)\\ \hskip 142.26378 pt=minSup*(|\mathcal{D}|+inc*|\mathcal{D}|)\text{;}\end{array} \]  
\(\square\)  
**Lemma 1**. : _(Absolute Count):_  
\[ \begin{array}{l}\textbf{xeFI}(\mathcal{D},\textbf{minSup}*(\textbf{1}+inc)) \rightarrow\textbf{xeFI}\big{(}\mathcal{D}^{+},\textbf{minSup}\big{)}\text{;} \end{array} \]  
**Proof of Lemma 1. **  
\[ \begin{array}{l}x\in FI(\mathcal{D},minSup*(\textbf{1}+inc))\rightarrow\\ sup_{\mathcal{D}^{+}}(x)=sup_{\mathcal{D}}(x)+sup_{\Delta}(x)\geq sup_{ \mathcal{D}}(x)\geq minSup*(\textbf{1}+inc)*|\mathcal{D}|\\ \hskip 142.26378 pt=minSup*(|\mathcal{D}|+inc*|\mathcal{D}|)=minSup*(|\mathcal{D }|+|\Delta|)\\ \hskip 142.26378 pt=minSup*|\mathcal{D}^{+}|\text{;}\end{array} \]  
i.e., \(sup_{\mathcal{D}}(x)\geq minSup(1+inc)n\to leFI(\mathcal{D}^{+},minSup)\);  
Lemma 1 ensures that if \(\mathbf{x}\) is \"very\" frequent in the old \(\mathcal{D}\) (support of at least \(minSup*(1+inc)\)), then it will be frequent in \(\mathcal{D}^{+}\) even if it does not appear in \(\Delta\) at all. \(\square\)  
**Lemma 2**. : _(Minimum Count):_  
\[\textbf{xeFI}\big{(}\mathcal{D}^{+},\textbf{minSup}\big{)}\rightarrow\textbf{ sup}_{\mathcal{D}}(x)\geq\textbf{n}*(\textbf{minsup}+\textbf{minsup}*\textbf{inc}- \textbf{inc})\text{;}\]  
**Proof. **  
\[sup_{\Delta}(x)\leq|\Delta|=inc*n\text{;}\]\[\left|\Delta\right|+sup_{\mathcal{D}}(x)\geq sup_{\Delta}(x)+sup_{\mathcal{D}}(x)\]  
\[\geq minSup*\left|\mathcal{D}^{+}\right|=minSup*(1+inc)*n;\]  
\[sup_{\mathcal{D}}(x)\geq minSup*(1+inc)*n-\left|\Delta\right|\]  
\[=minSup*(1+inc)*n-inc*n\]  
\[=n*(minSup+minSup*inc-inc);\]  
For answering if \(x\) can be in \(FI(\mathcal{D}^{+},minSup)\) without even looking at \(\Delta\), we need to know if \(xe\text{FI}(\mathcal{D},minSup+minSup*inc-inc)\). Of course, \(minSup+minSup*inc-inc\) may be less than zero (or \(minSup\geq inc(inc+1)\)), there is no minimum level. Lemma 2 puts a lower bound of occurrences of itemset \(x\) in old \(\mathcal{D}\) for it to have a possibility to appear in FI of \(\mathcal{D}^{+}\) (even if \(x\) appears in 100% of transactions in \(\Delta\), it must obey this criterion and therefore it is a pruning condition). See below for its use for non-frequent itemsets. \(\square\)  
Lemma 3: \[sup_{\Delta}(x)\geq minSup*(1+inc)*n\rightarrow\ x\in FI\big{(}\mathcal{D}^{+}, minsup\big{)};\]  
Proof: Similar to Lemma 1 conclusion:  
\[sup_{\mathcal{D}^{+}}(x)=sup_{\Delta}(x)+sup_{\mathcal{D}}(x)\geq sup_{\Delta} (x)\geq minSup*(1+inc)*n=minSup*\left|\mathcal{D}^{+}\right|;\]  
Lemma 3 tells us that if \(x\) is \"very\" frequent in \(\Delta\) and \(\Delta\) is large enough or \(minSup\) is small enough, then \(x\) will appear in FI of \(\mathcal{D}^{+}\) (even if it never appeared in old \(\mathcal{D}\)).