# New and Efficient Algorithms for Producing Frequent Itemsets with the Map-Reduce Framework
## 2 Background and Related Work
### Map-Reduce Model  
Map-Reduce is a parallel model and framework introduced in [1]. The abstract model requires defining two functions (algorithms):  
\[map\ (k1,\ v1)\to list(k2,v2)\]  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Frequent in \(\mathcal{D}\)** & **Not Frequent in \(\mathcal{D}\)** \\ \hline Frequent in \(\Delta\) & Frequent in \(\mathcal{D}^{+}\) & Unknown \\ Not frequent in \(\Delta\) & Unknown & Not frequent in \(\mathcal{D}^{+}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Cases for item to be frequent and the outcome.  
\[reduce\left(k2,list(v2)\right)\to list(v2)\]  
Map is applied to all input elements and transforms them to a key/value pair. Reduce is applied to all elements with the same key (after transformation by \"map\") and generates the final output. Reduce has access to all the values that are associated with some key, so it can output one, many or no values at all.  
The framework takes care of everything else--reading the physical input, splitting it into distributed nodes, executing the worker processes on the remote machines for handling logical tasks, running the map function tasks on all the records from the input, sending the results to reduce function tasks, output of the final results from reducers, fault tolerance, and recovery if required, etc. The flow is shown in Figure 1. Each map and reduce combination that is executed on some input is called a job. Some algorithms may require multiple consecutive jobs of the same or different Map-Reduce functions to accomplish the algorithm goal (e.g., iterative algorithms like Apriori may require K iterations before finishing--one Map-Reduce for a candidate of length K--that would generate K Map-Reduce jobs). Data for Map-Reduce is saved in a distributed file system. In Hadoop [2], it is called Hadoop Distributed File System (HDFS) [27]. Data is kept in blocks of constant size. The most common values for block sizes that are being used are 32 megabytes (MB), 64 MB and 128 MB.  
In Map-Reduce, each chunk of split input is called simply a \"Split\". The standard way for Map-Reduce to split the input is by using a constant size. MR does this by using the HDFS file system blocks, so the sizes are mostly similar to HDFS or its multiplier. The MR framework makes sure not to split the logical input in the middle of an information unit. By default, information from a Split is being provided to a Mapper line-by-line. There is a strong correlation between a Split and a Mapper: each Split is related to a single Mapper and vice versa. The data from the Split is processed exactly once. The exceptions to it are in fault/recovery scenarios and speed optimization (if we have more than one idle machine, we can do the same computation twice and use the results of the fastest machine).  
The Map-Reduce framework may have more stages in a job that supports executing map and reduce functions, e.g., Combiner can perform local \"reduce\" just after the Mapper on the same machine and the Partitioner is responsible for sending data from the Mapper/Combiner output to the Reducer input. Most of the steps could be customized to support more advanced scenarios via configuration, code or changing the source code of Hadoop itself, i.e., Input Reading: instead of reading input  
Figure 1: Map-Reduce Framework [1].  
line-by-line, the whole file could be read and provided to the map stage as one large input. Another example is providing a custom partitioning function that would send input to the reducer by some algorithm logic instead of doing it by simple hash of the key.