Paper Info
Title
Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees
Abstract
The tasks of extracting (top-K) Frequent Itemsets (FIs) and Association Rules (ARs) are fundamental primitives in data mining and database applications. Exact algorithms for these problems exist and are widely used, but their running time is hindered by the need of scanning the entire dataset, possibly multiple times. High-quality approximations of FIs and ARs are sufficient for most practical uses. Sampling techniques can be used for fast discovery of approximate solutions, but works exploring this technique did not provide satisfactory performance guarantees on the quality of the approximation due to the difficulty of bounding the probability of under- or oversampling any one of an unknown number of frequent itemsets. We circumvent this issue by applying the statistical concept of Vapnik-Chervonenkis (VC) dimension to develop a novel technique for providing tight bounds on the sample size that guarantees approximation of the (top-K) FIs and ARs within user-specified parameters. The resulting sample size is linearly dependent on the VC-dimension of a range space associated with the dataset. We analyze the VC-dimension of this range space and show that it is upper bounded by an easy-to-compute characteristic quantity of the dataset, the d-index, namely, the maximum integer d such that the dataset contains at least d transactions of length at least d such that no one of them is a superset of or equal to another. We show that this bound is tight for a large class of datasets. The resulting sample size is a significant improvement over previous known results. We present an extensive experimental evaluation of our technique on real and artificial datasets, demonstrating the practicality of our methods, and showing that they achieve even higher quality approximations than what is guaranteed by the analysis.
Year
DOI
Venue
2011
10.1145/2629586
ACM Transactions on Knowledge Discovery From Data
Keywords
DocType
Volume
resulting sample size,algorithms,vc-dimension,experimentation,relative approximation,novel technique,efficient discovery,frequent itemsets,association rule,range space,tight performance guarantee,high quality approximation,sample size,theory,data mining,entire dataset,association rules,sampling,higher quality approximation,artificial datasets,performance
Journal
8
Issue
ISSN
Citations 
4
1556-4681
11
PageRank 
References 
Authors
0.60
57
2
Name
Order
Citations
PageRank
Matteo Riondato134020.63
Eli Upfal24310743.13