# New and Efficient Algorithms for Producing Frequent Itemsets with the Map-Reduce Framework
## 4 Incremental Frequent Itemset Mining with Map-Reduce
### Experimental Evaluation
#### 4.3.7 The Algorithm Relation to the Spark Architecture  
Spark [3] is a distributed parallel system that has recently gathered popularity. The main difference from Map-Reduce is that it tries to make all computations in memory. Spark uses notation of Resilient Distributed Datasets (RDDs), which can be recomputed in case of failure. On the contrary, Map-Reduce  
Figure 9: **(a)** T20 Run Time _minSup_ 0.1% Cluster 5; **(b)** T20 CPU Time _minSup_ 0.1% Cluster 5; **(c)** T20 Run Time _minSup_ 0.2% Cluster 5; **(d)** T20 CPU Time _minSup_ 0.2% Cluster 5; **(e)** T20 Run Time _minSup_ 0.1%, _inc_ 10%; **(f)** T20 CPU Time _minSup_ 0.1%, _inc_ 10%; **(g)** WebDocs Run time _minSup_ 15% _inc_ 10%; **(h)** WebDocs CPU time _minSup_ 15% _inc_ 10%; **(i)** WebDocs _minSup_ 20% Run Time; **(j)** WebDocs minSup_ 20% CPU Time; **(k)** WebDocs _minSup_ 15% Run Time; **(l)** WebDocs _minSup_ 15% CPU Time; **(m)** WebDocs _minSup_ 15% Run Time Close Up; **(n)** WebDocs _minSup_ 15% CPU Time Close Up.  
saves all intermediate and final results on a local or a distributed file system (DFS). The fact that Spark uses in-memory computation, and in-memory distributed cache allows Spark to achieve better performance. It has much less I/O operations as data is being cached in memory. This provides a significant boost to many algorithms.  
Our general algorithm is not going to change due to the switch of the computation framework to Spark. We still need to assume that there is a way to compute frequent itemsets in Spark (and indeed Spark's mllib library contains the FIM algorithm, which is currently based on a FP-Growth-FPGrowth class). Joining two lists/tables is also easily done in Spark. Spark has many kinds of joins implemented (\"join\" function). The last parts are recounting transactions in different datasets, which could be once again easily done via a set of calls to \"map\" and \"reduceByKey\" Spark functions. Broadcasting and caching datasets of all new potential frequent itemsets on each node will improve the overall run time (SparkContext.broadcast). This is possible as the amount of potential frequent itemsets tends to be much lower than all datasets and could be cached in the memory of each partition. As the calculation of frequent itemsets is a computationally intensive operation, the Spark incremental scheme for FIM would have better performance than full re-computation in most cases, similar to Map-Reduce.  
The early pruning optimization that was introduced in Section 4.2.2 would have a positive effect in Spark too, as there will be less itemsets to cache in memory, and less itemsets to check against the different datasets.  
Job reduction optimizations from Section 4.2.4 are less effective in Spark because of the following: Spark does not spawn a new process/VM for each task, but utilizes multi-threading, so it achieves a better job start time. Spark also encourages writing programs in declarative ways so some \"job merging\" is achieved naturally by allowing the SparkContext executors to decide for themselves how to solve the problem more effectively. If the size of a dataset tends to be much larger than the total RAM of the cluster, then the cache would be frequently flushed, and data would be re-read from the disk. In such cases, manually forcing a data read only once would be still beneficial, so joining a few computations into a single pass on data will be preferable.  
The reuse of discarded data from Section 4.2.5 tends to reduce the number of itemsets that need to be checked in the old dataset. The issue is that the default FIM algorithm in Spark does not produce any intermediate results as it is based on FP-Growth. If some other algorithm for FIM could be used that would produce additional itemsets, we suggest using them and this optimization.  
Spark streaming is based on re-running the algorithm on \"micro batches\" of newly arrived data. Our algorithm could be used to achieve this task. However, the sizes of batches that are suitable for efficient streaming computation should be further studied.