## 3 MrCloud: Our Data Analytic Algorithm
### Processing Uncertain Big Data
For the explicit user-specified non-AFM constraints \(C_{\text{\it nonAM}}\), our MrCloud verifies the validity of each discovered frequent \(\{x\}\) returned by the \(\text{reduce}_{1}\) function to see if it satisfies the user-specified constraints. Consequently, we obtain all valid frequent singletons (_i.e._, domain items that satisfy the user-specified constraints) and their associated existential support values. MrCloud then proceeds to the next step, which is computationally intensive, by rereading each transaction in the uncertain big data to form an \(\{x\}\)-projected database (_i.e._, a collection of all prefixes of transactions ending with \(x\)) for each valid frequent singleton \(\{x\}\) returned by the reduce\({}_{1}\) function. This second map function (denoted as map\({}_{2}\))  
\[\text{map}_{2}\text{: }\langle\text{ID of transaction }t_{j}\text{, content of }t_{j}\rangle\ \mapsto\ \text{list of }\langle\text{valid frequent }\{x\}\text{, part of }t_{j}\text{ with }x\rangle \tag{5}\]  
can be specified as follows:  
**for each**\(t_{j}\in\) partition of the uncertain big data **do**  
**for each**\(\{x\}\in\langle\{x\},\mathit{expSup}(\{x\})\rangle\) **do**  
**if** prefix of \(t_{j}\) ending with \(x\) contains items besides \(x\) **then**  
**emit**\(\langle\{x\}\), prefix of \(t_{j}\) ending with \(x\rangle\). The worker node corresponding to each partition helps to form an \(\{x\}\)-projected database for every valid frequent item \(x\) in the transactions assigned to that partition. The \(\{x\}\)-projected database consists of prefixes of relevant transactions (from the uncertain big data) that end with \(x\). More precisely, the worker node outputs \(\langle\{x\}\), portion of \(t_{j}\) for forming the \(\{x\}\)-projected database\(\rangle\) pairs. Then, the reduce function  
\[\text{map}_{1}\text{: }\langle\text{ID of transaction $t_{j}$, content of $t_{j}$}\rangle\mapsto\text{ list of }\langle\text{ valid $x$,P(x,t_{j})\rangle$} \tag{2}\]0  
shuffles and sorts these pairs of \(\{x\}\)-projected databases, from which valid frequent non-singleton patterns can be found and their expected support values can be computed. As any non-singleton patterns containing valid singleton items are not guaranteed to be valid, additional constraint check on AM constraints \(C_{\mathit{AM}}\) is required when forming the projected database in mining valid frequent patterns. So, the worker node corresponding to each projected database then builds appropriate trees (e.g., UF-tree, TPC-tree, or BLIMP-tree)--based on the projected databases assigned to the worker node--to mine every valid frequent non-singleton pattern \(X\) (with cardinality \(k\), where \(k\geq 2\)). The worker node also outputs \(\langle X,\mathit{expSup}(X)\rangle\), _i.e._, every valid frequent non-singleton pattern with its expected support:  
**for each**\(x\in\{x\}\)-projected database **do**  
build a tree for \(\{x\}\)-projected database to find \(X\);  
**if**\(X\) satisfies \(C_{\mathit{AM}}\)**and**\(\mathit{expSup}(X)\geq\mathit{minsup}\)**then**  
**emit**\(\langle X,\mathit{expSup}(X)\rangle\). Again, for the explicit user-specified non-frequency non-AM constraints \(C_{\mathit{nonAM}}\), our MrCloud verifies the validity of each discovered frequent \(X\) returned by the reduce\({}_{2}\) function to see if it satisfies the user-specified constraints. **Example 1**. : _Let us consider an illustrative sample set of an uncertain big database (as shown in Table 1) and its auxiliary information (as shown in Table 2) with (i) the user-specified minsup=0.9; and (ii) a user-specified constraint \(C_{10}\equiv\) [min(X.RewardPoints) \(\geq\) 2000] \(\land\) [X.Location = Europe] (which expresses the user interest in finding every pattern \(X\) such that the minimum reward points earned by travellers among all European airports visited are at least 2000).