## 3 MrCloud: Our Data Analytic Algorithm
### Processing Uncertain Big Data  
Once the users queried uncertain big data by specifying their constraints that express their interest, our MrCloud algorithm processes these user-specified queries to find frequent patterns that satisfy these user-specified constraints. Given (i) an implicit frequency constraint \(C_{2}\equiv\)_exp_Sup(\(X\)) \(\geq\)_minsup_; and (ii) an explicit user-specified constraints, MrCloud explores the anti-monotonicity of these constraints in pruning the search space. More specifically, the implicit frequency constraint satisfies the anti-monotonicity: \begin{table}
\begin{tabular}{c l} \hline \hline
**Classification** & **Constraints** \\ \hline \multirow{7}{*}{AM} & _X.attribute_\(\theta\)_constant_, where \(\theta\in\{>,\geq=,\leq,<\}\) \\  & max(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{=,\leq,<\}\) \\  & min(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{>,\geq,=\}\) \\  & sum(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{\leq,<\}\) \\  & \(C_{1}\wedge C_{2}\), where \(C_{1}\) and \(C_{2}\) are AM constraints \\  & \(C_{1}\lor C_{2}\), where \(C_{1}\) and \(C_{2}\) are AM constraints \\ \hline \multirow{7}{*}{non-AM} & max(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{>,\geq\}\) \\  & min(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{\leq,<\}\) \\  & sum(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{>,\geq\}\) \\ \cline{1-1}  & avg(_X.attribute_) \(\theta\)_constant_, where \(\theta\in\{>,\geq,=,\leq,<\}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Classification of some AM and non-AM constraints. * If a pattern \(X\) is frequent (_i.e._, _expSup\((X)\geq\) minsup_), then all subsets of \(X\) are guaranteed to satisfy the AM constraints because _expSup\((X^{\prime})\geq\) expSup\((X)\geq\) minsup_ for every subset \(X^{\prime}\subseteq X\). * If a pattern \(Y\) is infrequent (_i.e._, _expSup\((Y)<\) minsup_), then all supersets of \(Y\) are guaranteed to be infrequent because _expSup\((Y^{\prime})<\) expSup\((Y)<\) minsup_ for every superset \(Y^{\prime}\supseteq Y\). Thus, every superset \(Y^{\prime}\) of \(Y\) can be pruned. However, if a pattern \(X\) is frequent, then some supersets of \(X\) may be frequent while some other may not be frequent. Thus, frequency checking is needed to be applied to every superset of \(X\). Similarly, if the user-specified constraint satisfies the anti-monotonicity, then we can prune the search space due to the following:  
* If a pattern \(X\) satisfies AM constraints, then all subsets of \(X\) are guaranteed to satisfy the AM constraints. * If a pattern \(Y\) does not satisfy AM constraints, then all supersets of \(Y\) are guaranteed not to satisfy the AM constraints and thus can be pruned. However, if a pattern \(X\) satisfies AM constraints, then some supersets of \(X\) may satisfy the AM constraints while some other may not satisfy the AM constraints. Thus, constraint checking is needed to be applied to every superset of \(X\). These observations about anti-monotone constraints hold not only for constraints involving one AM constraint but also constraints involving multiple AM constraints due to the following. **Theorem 1**. : _If constraints \(C_{a}\) and \(C_{b}\) are anti-monotone, then the constraint (\(C_{a}\wedge C_{b}\)) is also anti-monotone._  
Proof. : For anti-monotone constraints \(C_{a}\) and \(C_{b}\), if a pattern \(X\) satisfies \(C_{a}\) and \(C_{b}\), then all subsets of \(X\) are guaranteed to satisfy \(C_{a}\) and satisfy \(C_{b}\). In other words, all subsets of \(X\) are guaranteed to satisfy (\(C_{a}\wedge C_{b}\)). Conversely, if a pattern \(Y\) does not satisfy \(C_{a}\) and does not satisfy \(C_{b}\), then all supersets of \(Y\) are guaranteed not to satisfy (\(C_{a}\wedge C_{b}\)). Thus, (\(C_{a}\wedge C_{b}\)) is also anti-monotone. **Theorem 2**. : _If constraints \(C_{a}\) or \(C_{b}\) are anti-monotone, then the constraint (\(C_{a}\lor C_{b}\)) is also anti-monotone._  
Proof.