## 2 Background and Related Works
### Big Data Mining with the MapReduce Model  
MapReduce [13] is a high-level programming model for processing vast amounts of data. It usually uses parallel and distributed computing on clouds of nodes (_i.e._, computers). As implied by its name, MapReduce involves two key functions: \"map\" and \"reduce\".  
First, the input data are read, divided into several partitions (sub-problems), and assigned to different processors. Each processor executes the map function on each partition (sub-problem). The map function takes a pair of \(\langle key,value\rangle\) and returns a list of \(\langle key,value\rangle\) pairs as an intermediate result:  
\[\text{map: }\langle key_{1},value_{1}\rangle\mapsto\text{list of }\langle key_{2},value_{2}\rangle\]where (i) \(key_{1}\) & \(key_{2}\) are keys in the same or different domains; and (ii) \(value_{1}\) & \(value_{2}\) are the corresponding values in some domains.  
Afterwards, the pairs returned by the map function are shuffled and sorted. Each processor then executes the reduce function on (i) a single key from this intermediate result together with (ii) the list of all values that appear with this key in the intermediate result. The reduce function \"reduces\"--by combining, aggregating, summarizing, filtering, or transforming--the list of values associated with a given key (for all \(k\) keys) and returns a single (aggregated or summarized) value:  
\[\text{reduce: }\langle key_{2},\text{list of }value_{2}\rangle\mapsto value_{3}\]  
where (i) \(key_{2}\) is a key in some domains; and (ii) \(value_{2}\) & \(value_{3}\) are the corresponding values in some domains. Examples of MapReduce applications include the construction of an inverted index as well as the word counting of a document for data processing [13].  
To mine frequent patterns from precise data using the MapReduce model, three Apriori-based algorithms called SPC, FPC and DPC [37] were proposed. Among them, SPC uses single-pass counting to find frequent patterns of cardinality \(k\) at the \(k\)-th pass (_i.e._, the \(k\)-th database scan) for \(k\geq 1\). FPC uses fixed-passes combined-counting to find all patterns of cardinalities \(k\), \((k+1)\),..., \((k+m)\) in the same pass or database scan. On the one hand, this fixed-passes technique fixes the number of required passes from \(k_{max}\) (where \(k_{max}\) is the maximum cardinality of all frequent patterns that can be mined from the precise data) to a user-specified constant. On the other hand, due to combined-counting, the number of generated candidates is higher than that of SPC. In contrast, DPC uses dynamic-passes combined-counting, which takes the benefits of both SPC and FPC by taking into account the workloads of nodes when mining frequent patterns with MapReduce. In addition, a parallel randomized algorithm called PARMA [38] was proposed for mining approximations to the top-\(k\) frequent patterns and association rules from precise data by using MapReduce.  
As a preview, our MrCloud algorithm also uses MapReduce. However, unlike SPC, FPC or DPC [37] (which use the Apriori-based approach to mine frequent patterns from precise data), our MrCloud uses a tree-based approach to mine frequent patterns from uncertain data--which deals with a much larger search space than that for mining precise data due to the presence of the existential probability values. Moreover, unlike PARMA (which mines all of the approximately frequent patterns from precise data), our data analytic algorithm mines some--specifically, those interesting patterns that satisfy the user-specified constraints--of the truly frequent patterns from uncertain data.