# New and Efficient Algorithms for Producing Frequent Itemsets with the Map-Reduce Framework
## Mining Closed Frequent Itemsets with Map-Reduce
### Reduce Step
#### 3.2.4 Run Example  
Consider the example database \(\mathcal{D}\) in Table 2 with a minimum support of two transactions (\(minSup=40\%\)). To simulate a distributed setting, we assume that each transaction \(t_{i}\) resides on a different machine in the network (mapper node), denoted \(m_{i}\).  
**1 st Map Step.** We track node \(m_{1}\). Its input is the transaction \(t_{1}\), and since this is the first iteration then \(C_{i-1}=C_{0}=\phi\). For each item in the input transaction, we emit a message containing the item as a key and the transaction as a value. So, the messages that \(m_{1}\) emits are the following: \(<\{a\},\{a,c,d,e,f\}>,<\{c\},\{a,c,d,e,f\}>,<\{d\},\{a,c,d,e,f\}>\), \(<\{e\},\{a,c,d,e,f\}>\), and \(<\{f\},\{a,c,d,e,f\}>\). A similar mapping process is done on other nodes.  
**1 st Reduce Step.** According to the Map-Reduce paradigm, a reducer task is assigned to every key. We follow the reducer tasks assigned to keys \(\{a\}\), \(\{c\}\) and \(\{f\}\), denoted \(R_{a}\), \(R_{c}\), and \(R_{f}\) respectively.  
First, consider \(R_{a}\). According to the Map-Reduce paradigm, this reduce task receives in addition to the key \(\{a\}\), all the transactions in \(\{D\}\) that contain that key: \(t_{1}\), \(t_{2}\) and \(t_{4}\). First, we must test the frequency: there are three transactions containing the key. Since \(minSup*|\mathcal{D}|=2\), we pass the frequency test and go on. Next, we intersect all the transactions, producing the closure \(\{a\}\). The final check is whether the closure is lexicographically larger than the generator. In our case it is not (because the generator and closure are equal), so we add \(\{a\}\) to \(C_{1}\).  
Next, consider \(R_{c}\). This reduce task receives the key \(\{c\}\), and transactions \(t_{1}\), \(t_{3}\), \(t_{4}\) and \(t_{5}\). Since the number of transactions is four, we pass the frequency test. The intersection of the transactions is the closure \(\{c,f\}\). Finally, \(\{c\}\) is lexicographically smaller than \(\{c,f\}\), so we add \(\{c,f\}\) to \(C_{1}\).  
Finally, consider \(R_{f}\). The transactions that contain the set \(\{f\}\) are \(t_{1}\), \(t_{3}\), \(t_{4}\) and \(t_{5}\). We pass the frequency test, but the intersection is \(\{c,f\}\), just like in reduce task \(R_{c}\), so we have a duplicate result. However, \(\{f\}\) is lexicographically greater than \(\{c,f\}\), so this closure is discarded.  
The final set of all closed frequent itemsets found on the first iteration is: \(C_{1}=\{\{a:a\},\{c,f:c\},\{e:e\}\}\) (the itemset after the semicolon is the generator of this closure).  
**2 nd Map Step.** As before, we follow node \(m_{1}\). This time the set of closed frequent itemsets is not empty, so according to the algorithm, we iterate over all \(c\in C_{1}\). If the input transaction \(t\) contains\(c\), we add to \(c\) all the items in \(t\backslash c\), each at a time, and emit it. So, the messages that \(m_{1}\) emits are the following:  
\[\begin{array}{l}<\{a,c\},\{a,c,d,e,f\}>,\\ <\{a,d\},\{a,c,d,e,f\}>,\\ <\{a,e\},\{a,c,d,e,f\}>,\\ <\{a,f\},\{a,c,d,e,f\}>,\\ <\{c,d\},\{a,c,d,e,f\}>,\\ <\{c,e\},\{a,c,d,e,f\}>,\\ <\{c,f\},\{a,c,d,e,f\}>.\end{array}\]  
**2 nd Reduce Step.** Consider reduce task \(R_{ac}\). According to the Map-Reduce paradigm, this reduce task receives all the messages containing the key \(\{a,c\}\), which are transactions \(t_{1}\) and \(t_{4}\). Since \(minSup=2\), we pass the frequency test. Next, we consider the key \(\{a,c\}\) as a generator and intersect all the transactions getting the closure \(\{a,c,d,f\}\). The final check is whether the added item \(c\) is lexicographically larger than the closure minus the generator. In our case it is not, so we add \(\{a,c,d,f\}\) to the set of closed frequent itemsets.  
The full set of closed frequent itemsets is shown in Table 3. Next, we prove the soundness and completeness of the algorithm.