# New and Efficient Algorithms for Producing Frequent Itemsets with the Map-Reduce Framework
## Mining Closed Frequent Itemsets with Map-Reduce
### The Algorithm
#### 3.2.3 Algorithm Steps  
Map Step  
A map task in iteration \(i\) gets three parameters as an input: (1) a set of all the closed frequent itemsets (with their generators) found in the previous iteration, denoted \(C_{i-1}\) (which is shared among all the mappers in the same iteration); (2) a single transaction denoted \(t\); and (3) the set of all frequent items in \(D\) (again, this set is also shared among all the mappers in the same iteration and in all iterations). Note that in the Hadoop implementation, the mapper gets a set of transactions called Split and the mapper object calls the map function for each transaction in its own Split only. For each \(c\in C_{i-1}\), if \(c\subseteq t\), then \(t\) holds the potential of finding new closed frequent itemsets by looking at the complement of \(c\) in \(t\) (line 3). For each \(item\in(t\backslash c)\), we check if \(item\) is frequent (line 5). If so, we concatenate \(item\) to the generator of \(c\) (denoted \(c\)_generator_), thus creating \(g\) (we denote that added item as \(g\)_item_), a potential new generator for other closed frequent itemsets (line 6). The function emits a message where \(g\) is the key and the tuple \((t,1)\) is the value (line 7). The \"1\" is later summed up and used to count the support of the itemset. Notice that \(g\) is not only a generator, but it is always a minimal generator. Concatenating an item not in its closure guarantees to reach another minimal generator. More precisely, it generates all minimal generators that are supersets of \(g\) with one additional item, and such, that \(t\) supports it. Since all transactions are taken, every minimal generator with a support of at least one is emitted at some point (this is proven later). The pseudo-code of the map function is presented in Algorithm 2. ```
Input:\(C_{i-1}\): The set of closed frequent itemsets with their generators, found in the previous iteration \(t\): A single transaction from \(\mathcal{D}\) \(f\_items\): The set of all frequent items Output: Key: potentially new generator  Value: transaction that contains the generator and its support
1 foreach\(c\in C_{i-1}\)do
2 if\(c\subseteq t\)then
3\(t^{\prime}\gets t\setminus c\_items\);
4 foreach\(item\in t^{\prime}\)do
5 if\(item\in f\_items\) & \(c\_generator\) < \(item\)then
6\(g\leftarrow\)concat(\(c\_generator\),\(item\));
7\(\texttt{emit}(\langle g,(t,1)\rangle)\);
8
9 end if
10
11 end for
```  
**Algorithm 2**Mapper. Combine Step  
A combiner is not a part of the Map-Reduce programming paradigm, but a Hadoop implementation detail that minimizes the data transferred between map and reduce tasks. Hadoop gives the user the option of providing a combiner function that is to run on the map output on the same machine running the mapper, and the output of the combiner function is the input for the reduce function. In our implementation, we have used a combiner, which is quite similar to the reducer but much simpler. The input to the combiner is a key and a collection of values: the key is the generator \(g\) (which is an itemset), and the collection of values is a collection of tuples, composed of transactions \(T\), all containing \(g\) and a number \(s\) indicating the support of the tuple. Since the combiner is \"local\" by nature, it has no use of the minimum support parameter, which must be applied in a global point of view. The combiner sums the support of the input tuples, stores it in the variable \(sum\), and then performs an intersection on the tuples to get \(t^{\prime}\). The combiner emits a message where \(g\) is the key and the tuple \((t^{\prime},sum)\) is the value. The pseudo-code of the combiner function is presented in Algorithm 3. ```
Input: Key: \(g\), a generator Values: \((t_{1},s_{1}),...,(t_{n},s_{n})\): a collection of \(n\) tuples such that \(t_{i}\) is a transaction and \(s_{i}\) is its support Output: Key: potentially new generator Value: transaction that contains the generator, and its support \(sum\leftarrow\sum_{i=1}^{n}s_{i}\) ; /* Applying the \(f\) function on \(t_{1},...t_{n}\), i.e.