## 3 MrCloud: Our Data Analytic Algorithm
### Processing Uncertain Big Data
Based on the auxiliary information, we learn that airports AMS, BCN, CPH, EDI, FRA and HEL (but not DEL, GUM or IST) satisfy \(C_{10}\)_More specifically, (i) both DEL and GUM are not in Europe; and (ii) travellers visiting either GUM or IST would not be able to earn at least 2000 reward points._  
_Then, for the first transaction \(t_{1}\), the map\({}_{1}\) function outputs only \(\langle\)AMS, 0.9\(\rangle\), \(\langle\)BCN, 1.0\(\rangle\), \(\langle\)CPH, 0.5\(\rangle\), \(\langle\)EDI, 1.0\(\rangle\) and \(\langle\)FRA, 0.2\(\rangle\). Similarly, for the second transaction \(t_{2}\), the map\({}_{1}\) function outputs \(\langle\)AMS, 0.8\(\rangle\), \(\langle\)BCN, 0.8\(\rangle\), \(\langle\)CPH, 1.0\(\rangle\), \(\langle\)EDI, 0.2\(\rangle\), and \(\langle\)FRA, 0.2\(\rangle\). For the third transaction \(t_{3}\), the map\({}_{1}\) function outputs only \(\langle\)AMS, 0.4\(\rangle\), \(\langle\)FRA, 0.2\(\rangle\) and \(\langle\)HEL, 0.5\(\rangle\). These output pairs are then shuffled and sorted._  
_Note that the map\({}_{1}\) function does not output \(\langle\)DEL, 0.9\(\rangle\) for \(t_{1}\) because [DEL] does not satisfy \(C_{10}\). Moreover, it also does not output \(\langle\)IST, 0.6\(\rangle\) for \(t_{2}\) or \(\langle\)GUM, 1.0\(\rangle\) for \(t_{3}\) because both [IST] and [GUM] also do not satisfy \(C_{10}\)._  
_Afterwards, the reduce\({}_{1}\) function first reads \(\langle\)AMS, [0.9, 0.8, 0.4\(\rangle\)], \(\langle\)BCN, [1.0, 0.8\(\rangle\)], \(\langle\)CPH, [0.5, 1.0]\(\rangle\), \(\langle\)EDI, [1.0, 0.2]\(\rangle\), \(\langle\)FRA, [0.2, 0.2, 0.2]\(\rangle\) and \(\langle\)HEL, [0.5\(\rangle\)]; the function then outputs \(\langle\)[AMS], 2.1\(\rangle\), \(\langle\)[BCN], 1.8\(\rangle\), \(\langle\){CPH}, 1.5\(\rangle\) and \(\langle\)[EDI], 1.2\(\rangle\) (i.e., valid frequent singletons and their corresponding expected support)._  
_Also note that, although the reduce\({}_{1}\) function reads \(\langle\)FRA, [0.2, 0.2, 0.2]\(\rangle\) and \(\langle\)HEL, [0.5\(\rangle\)], it does not output \(\langle\)[FRA], 0.6\(\rangle\) or \(\langle\)[HEL], 0.5\(\rangle\) because valid singletons [FRA] and [HEL] are infrequent._  
_After rereading the first transaction \(t_{1}\), the map\({}_{2}\) function outputs \(\langle\){BCN}, [AMS: 0.9, BCN: 1.0\(\rangle\)] (where [AMS: 0.9, BCN: 1.0\(\rangle\)] is a prefix of \(t_{1}\) ending with item BCN), \(\langle\){CPH}, [AMS: 0.9, BCN: 1.0, CPH: 0.5]\(\rangle\) and \(\langle\)[EDI], [AMS: 0.9, BCN: 1.0, CPH: 0.5, EDI: 1.0\(\rangle\)] (where [AMS: 0.9, BCN: 1.0, CPH: 0.5, EDI: 1.0\(\rangle\), C.S. )_ _and_ _(_EDI_, _[AMS: 0.9, BCN: 1.0, CPH: 0.5, EDI: 1.0\(\rangle\)]_ _contains only valid frequent items--i.e., it does not contain invalid item DEL). Similarly, after rereading the second transaction \(t_{2}\), the map function\({}_{2}\) outputs \(\langle\){BCN}, [AMS: 0.8, BCN: 0.8\(\rangle\)], \(\langle\){CPH}, [AMS: 0.8, BCN: 0.8, CPH: 1.0, EDI: 0.2\(\rangle\)]. After rereading the third transaction \(t_{3}\), the map\({}_{2}\) function does not output anything. All output pairs are then shuffled and sorted._  
_Note that the map\({}_{2}\) function does not output \(\langle\)[AMS], [AMS: 0.9\(\rangle\)] for \(t_{1}\) because [AMS: 0.9] does not contain any valid frequent item other than AMS itself (i.e., singleton prefix of transactions does not contribute to the mining of non-singletons). The same comments apply to not outputting \(\langle\)[AMS], [AMS: 0.8\(\rangle\)] for \(t_{2}\) or \(\langle\)[AMS], [AMS: 0.4\(\rangle\)] for \(t_{3}\). Moreover, recall that the reduce\({}_{1}\) function outputs \(\langle\)[AMS], 2.1\(\rangle\), \(\langle\)[BCN], 1.8\(\rangle\), \(\langle\){CPH}, 1.5\(\rangle\) and \(\langle\)[EDI], 1.2\(\rangle\) (as FRA & HEL are infrequent and GUM is invalid).