## 3 MrCloud: Our Data Analytic Algorithm
### Processing Uncertain Big Data
: For anti-monotone constraints \(C_{a}\) or \(C_{b}\), if a pattern \(X\) satisfies \(C_{a}\) and \(C_{b}\), then all subsets of \(X\) are guaranteed to satisfy \(C_{a}\) or satisfy \(C_{b}\). In other words, all subsets of \(X\) are guaranteed to satisfy (\(C_{a}\lor C_{b}\)). Conversely, if a pattern \(Y\) does not satisfy \(C_{a}\) or does not satisfy \(C_{b}\), then all supersets of \(Y\) are guaranteed not to satisfy (\(C_{a}\) or not to satisfy \(C_{b}\)). In other words, all supersets of \(Y\) are guaranteed not to satisfy (\(C_{a}\lor C_{b}\)). Thus, (\(C_{a}\lor C_{b}\)) is also anti-monotone. On the other hand, if the explicit user-specified constraints do not satisfy anti-monotonicity, our MrCloud first discovers all frequent patterns and then verifies the validity of each of these discovered patterns to see if it satisfies the user-specified constraints at a post-processing step. To process uncertain big data, our MrCloud algorithm first reads and divides the uncertain big data into several partitions and assigns them to different processors. The map function (denoted as \(\text{map}_{1}\)) receives \(\langle\text{transaction ID}\), content of that transaction\(\rangle\) as input. To facilitate time-efficient and space-efficient constrained frequent pattern mining, MrCloud pushes the user-specified non-frequency AM constraints \(C_{AM}\) early in the mining process by pushing them into the \(\text{map}_{1}\) function. So, for every transaction \(t_{j}\), the \(\text{map}_{1}\) function performs constraint checking for \(C_{AM}\) and emits an \(\langle x,P(x,t_{j})\rangle\) pair for each occurrence of valid item \(x\in t_{j}\) (_i.e._, those domain items satisfying the non-frequency AM constraints):  
\[\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}\]  
In other words, by specifying the following, the \(\text{map}_{1}\) function produces a list of \(\langle\text{valid $x$,P(x,t_{j})\rangle$}\) pairs with many different valid \(x\) and \(P(x,t_{j})\) for the keys and values:  
**for each**\(t_{j}\in\) partition of the uncertain big data **do**  
**for each** item \(x\in t_{j}\)**and**\(\{x\}\) satisfies \(C_{AM}\)**do**  
**emit**\(\langle x,P(x,t_{j})\rangle\).  
Afterwards, these \(\langle\text{valid $x$,P(x,t_{j})$}\rangle\) pairs are shuffled and sorted. Each processor then executes the reduce function (denoted as \(\text{reduce}_{1}\)) on the shuffled and sorted pairs to obtain the expected support of \(x\). Recall that each item in the uncertain big data is associated with an existential probability value. The \(\text{reduce}_{1}\) function computes the expected support of all domain items (_i.e._, singleton patterns) by using MapReduce with Equation (1), which can be simplified to become the following when computing singleton patterns:  
\[\text{\it expSup}(\{x\})=\sum_{j=1}^{n}P(x,t_{j}) \tag{3}\]  
where \(P(x,t_{j})\) is an existential probability of item \(x\) in transaction \(t_{j}\). In other words, the \(\text{reduce}_{1}\) function sums all existential probabilities of \(x\) for each valid \(x\) to compute its expected support:  
\[\text{reduce}_{1}\text{: }\langle\text{valid $x$, list of $P(x,t_{j})$}\rangle\ \mapsto\text{ list of }\langle\text{ valid frequent $\{x\}$, $\text{\it expSup}(\{x\})$}\rangle \tag{4}\]  
More specifically, the \(\text{reduce}_{1}\) function finds those items satisfying the frequency constraints by specifying the following:  
**for each**\(x\in\langle\text{valid $x$, list of $P(x,t_{j})$}\rangle\)**do**  
**set**\(\text{\it expSup}(\{x\})\) = 0;  
**for each**\(P(x,t_{j})\in\) list of \(P(x,t_{j})\)**do**  
\(\text{\it expSup}(\{x\})=\text{\it expSup}(\{x\})+P(x,t_{j})\);  
**if**\(\text{\it expSup}(\{x\})\geq\text{\it minsup}\)**then**  
**emit**\(\langle\{x\}\), \(\text{\it expSup}(\{x\})\rangle\).