# New and Efficient Algorithms for Producing Frequent Itemsets with the Map-Reduce Framework
## Mining Closed Frequent Itemsets with Map-Reduce  
### Problem Definition  
Let \(I=\{i_{1},i_{2},\ldots,i_{m}\}\) be a set of items with lexicographic order. An itemset \(x\) is a set of items such that \(x\subseteq I\). A transactional database \(\mathcal{D}=\{t_{1},t_{2},\ldots,t_{n}\}\) is a set of itemsets, each called a transaction. Each transaction in \(\mathcal{D}\) is uniquely identified with a transaction identifier (TID) and assumed to be sorted lexicographically. The difference between a transaction and an itemset is that an itemset is an arbitrary subset of \(I\), while a transaction is a subset of \(I\) that exists in \(\mathcal{D}\) and identified by its TID, \(tid\). The support of an itemset \(x\) in \(\mathcal{D}\), denoted \(sup_{\mathcal{D}}(x)\), or simply \(sup(x)\) when \(\mathcal{D}\) is clear from the context, is the number of transactions in \(\mathcal{D}\) that contain \(x\) (sometimes it is the percentage of transactions).  
Given a user-defined minimum support denoted \(minSup\), an itemset \(x\) is called frequent if \(sup(x)\geq minSup\times|\mathcal{D}|\).  
Let \(T\subseteq\mathcal{D}\) be a subset of transactions from \(\mathcal{D}\) and let \(x\) be an itemset. We define the following two functions \(f\) and \(g\):  
\[f(T)=\{i\in I|\forall t\in T,i\in t\}\]  
\[g(x)=\{t\in\mathcal{D}|\forall i\in x,i\in t\}\]  
Function \(f\) returns the intersection of all the transactions in \(T\), and function \(g\) returns the set of all the transactions in \(\mathcal{D}\) that contain \(x\). Notice that \(g\) is antitone, meaning that for two itemsets \(x_{1}\) and \(x_{2}\): \(x_{1}\subseteq x_{2}\to g(x_{2})\subseteq g(x_{1})\). It is trivial to see that \(sup(x)=|g(x)|\). The function \(h=f\circ g\) is called the Galois operator or closure operator.  
An itemset \(x\) is closed in \(\mathcal{D}\) if \(h(x)=x\). It is equivalent to say that an itemset \(x\) is closed in \(\mathcal{D}\) if no itemset, that is a proper superset of \(x\) has the same support in \(\mathcal{D}\), exists.  
Given a database \(\mathcal{D}\) and a minimum support \(minSup\), the mining closed frequent itemsets problem is finding all frequent and closed itemsets in \(\mathcal{D}\).  
Let \(I=\{a,b,c,d,e,f\}\), let \(minSup=3\) (\(minSup=60\%\)) and let \(\mathcal{D}\) be the transaction database presented in Table 2. Consider itemset \(\{c\}\). It is a subset of transactions \(t_{1}\), \(t_{3}\), \(t_{4}\) and \(t_{5}\), meaning that \(sup(\{c\})=4\), which is greater than \(minSup\times|\mathcal{D}|\). However, \(\{c,f\}\), which is a proper superset of \(\{c\}\), is also a subset of the same transactions. \(\{c\}\) is not a closed itemset since \(sup(\{c,f\})=sup(\{c\})\). The list of all closed frequent itemsets is: \(\{a\}\), \(\{c,f\}\), \(\{e\}\) and \(\{c,e,f\}\).  
We now present an algorithm for mining frequent closed itemsets in a distributed setting, using the Map-Reduce paradigm. It uses the generator idea mentioned in Section 2.2.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**TID** & **Transaction** \\ \hline \(t_{1}\) & \(\{a,c,d,e,f\}\) \\ \(t_{2}\) & \(\{a,b,e\}\) \\ \(t_{3}\) & \(\{c,e,f\}\) \\ \(t_{4}\) & \(\{a,c,d,f\}\) \\ \(t_{5}\) & \(\{c,e,f\}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: \(\mathcal{D}\) Example. TID = transaction identifier.