On the Number of Candidates in Apriori Like Algorithms for Mining Frequent Itemsets

Abstract

Frequent itemset mining has been a focused theme in data mining research for years. It was first proposed for market basket analysis in the form of association rule mining. Since the first proposal of this new data mining task and its associated efficient mining algorithms, there have been hundreds of follow-up research publications. In this paper we further develop the ideas from our previous work where we consider two problems from linear algebra, namely set intersection problem and scalar product problem, and make comparisons to the frequent itemset mining task. In this paper we formulate and prove new theorems that estimate the number of candidate itemsets that can be generated in the level-wise mining approach.