Mining frequent itemsets over uncertain databases

In recent years, due to the wide applications of uncertain da-ta, mining frequent itemsets over uncertain databases has at-tracted much attention. In uncertain databases, the support of an itemset is a random variable instead of a fixed occur-rence counting of this itemset. Thus, unlike the correspond-ing problem in deterministic databases where the frequent itemset has a unique definition, the frequent itemset under uncertain environments has two different definitions so far. The first definition, referred as the expected support-based frequent itemset, employs the expectation of the support of an itemset to measure whether this itemset is frequent. The second definition, referred as the probabilistic frequent itemset, uses the probability of the support of an itemset to measure its frequency. Thus, existing work on mining frequent itemsets over uncertain databases is divided into two different groups and no study is conducted to compre-hensively compare the two different definitions. In addition, since no uniform experimental platform exists, current so-lutions for the same definition even generate inconsistent results. In this paper, we firstly aim to clarify the relation-ship between the two different definitions. Through exten-sive experiments, we verify that the two definitions have a tight connection and can be unified together when the size of data is large enough. Secondly, we provide baseline imple-mentations of eight existing representative algorithms and test their performances with uniform measures fairly. Final-ly, according to the fair tests over many different benchmark data sets, we clarify several existing inconsistent conclusions and discuss some new findings. 1