# 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.1 General Scheme  
We first propose a general algorithm (Algorithm 5) for incremental frequent itemset mining. It can be used for any distributed or parallel framework, but it also suits the model of Map-Reduce. The algorithm is loosely based on the FUP [15] algorithm and shares similarities with ARMIDB [7] (see Section 2.3). The idea is to first find all frequent itemsets in the new database (only _deltaFI_) and then unite (join) the new frequent itemsets with the old frequent itemsets, and finally revalidate itemsets which are in the \"unknown\" state in each of the databases. This algorithm is general because it doesn't set any constraints on the FIM algorithm that is used (any Map-Reduce algorithm for finding frequent itemsets will suit). We show some optimizations of it later. Brief description of the algorithm (Algorithm 5): Step 1 is the execution of the MR main program (\"driver\"). Step 2 is getting all parameters and filling the MR job configuration. Steps 3 and 4 are the execution of any standard MR FIM algorithm on the incremental DB (\(\Delta\)), and saving its output back to HDFS (Step 4). For example, the use of IMRApriori as a MR FIM will include running first an MR job with a mapper that finds FI for each data Split and then its reducer will merge all \"local\" FI to a single candidate list. A second MR job will use its mapper to count all candidate occurrences in each  
Figure 7: Comparing execution time of the algorithms on real data. data Split, and the reducer will be used to summarize the candidate occurrences, and to output only \"globally\" frequent itemsets. Input: _minSup_, \(\Delta\), \(\mathcal{D}\), \(\text{FI}(\mathcal{D})\)  
Optional Input: Additional Previous knowledge (_PK_). 1: Start
2: Get all input
3: Run Frequent Itemset Mining Algorithm with MapReduce on \(\Delta\) with _minSup_
4: Save frequent itemset for \(\Delta\) as _deltaFI_
5: **if** no \(\mathcal{D}\) exists **then**
6: report _deltaFI_ as total frequent itemsets and **end**. 7: **else** Join Mapper loads all frequent itemsets and send them to reducer
8: Join Reducer joins itemset \(x\) from \(\mathcal{D}\) and \(\Delta\) and categories \(x\) into one of 3 sets: Appears in both DBs, appears only in \(\Delta\) and appears only in old \(\mathcal{D}\)
9: All itemsets that appear in both DBs are outputted as frequent itemsets in the updated database
10: All itemsets that appear frequent only in \(\Delta\) are counted by the Count Mapper in old \(\mathcal{D}\)
11: Count Reducer: outputs only itemset \(x\) that satisfies \(sup_{\mathcal{D}}(x)+sup_{\Delta}(x)\geq minSup\)\({}^{*}\mathcal{D}^{+}\)
12: All itemsets that appear frequent only in old \(\mathcal{D}\) are counted by the Count Mapper in \(\Delta\)
13: Count Reducer: outputs only itemset \(x\) that satisfies \(sup_{\mathcal{D}}(x)+sup_{\Delta}(x)\geq minSup\)\({}^{*}\mathcal{D}^{+}\)
14: **end** /* All outputs together generate total frequent itemsets for updated database */ ```
**Algorithm 5** General incremental frequent itemset mining algorithm. Steps 5 and 6 check if it is incremental run or not; in the latter case, the algorithm just stops. If it is the incremental run, then we need to find \"globally\" frequent itemsets (GFI) from \(\text{FI}(\Delta)\), and previous \(\text{FI}(\mathcal{D})\), i.e., \(\text{FI}(\mathcal{D}^{+},minSup)\). As mentioned in Section 2.3, when adding new transactions, locally frequent itemsets have three options. To determine to which option each itemset applies, we propose using a MR job for joining itemsets (Steps 7-8). Any join MR algorithm may be used here (during result evaluation, we have used repartition join for this task). The key of the Join reducer would be the itemset itself, and the list of values would be occurrences of the itemset in the different DB parts, together with its count. During our evaluation, Step 7 (Join's mapper) read itemsets from the databases, and outputted them together with their database mark.