VISTA: A View of Eective Sampling for Frequent Itemset Mining
Mudireddy Jagadesh Babu · 2011
Sampling is a well established technique to speed up the process of discovering frequent itemsets. While the early literature focused on heuristic techniques, mathematical bounds on the sample size required to probabilistically achieve approximately correct results were recently presented in [6], [12]. A particularly appealing feature of these bounds is that they are independent of the database row-cardinality. In this report, we demonstrate through an extensive empirical evaluation that the bounds, although theoretically elegant, are loose by as much as one to two orders of magnitude in practice. We therefore investigate the possibility of obtaining better bounds through prior knowledge of statistics on the datasets. In particular, we assume that the number of maximal frequent itemsets in the data mining result is known in advance. However, even with such a strong assumption, the revised bound turns out to be several multiples of the required sample size. This motivates us to consider the question of algorithmically identifying a reduced sample size that is sufficient to obtain accurate results. To address this issue, we present VISTA, a voting-based iterative sampling algorithm for accurately discovering frequent itemsets, whose sampling overheads are comparable to the ideal sample size for one-shot frequent itemset mining. VISTA incrementally mines samples in small batches and uses the presence or absence of a frequent itemset in each batch to determine its voting characteristics. The stopping condition is the reaching of a fix point in the identities of frequent itemsets that receive a clear majority of the votes across the batches. All results presented here are validated through extensive experimental evaluation on massive synthetic and real datasets.