2D Array Structure for Pattern Mining

Discovering frequent patterns is a crucial task during association rules mining. To our knowledge, frequent-pattern growth (FP-Growth) method is among the most efficient algorithms for pattern mining. However, many experimental results show that there is excessive memory requirement to build and traverse the conditional FP-trees in FP-Growth. In this paper we present a novel compact 2D array-based algorithm to reduce the memory consumption for FP-growth. Our algorithm efficiently uses the FP-tree data structure in combination with a new compact 2D array data structure to mine frequent itemsets. The advantage of the proposed method is that it does not require building many conditional FP-trees recursively, instead of that it just builds a single compact 2D array and then mines the frequent items through it. The proposed method generates the same frequent itemset compared with FP-growth for all the tested datasets. Our performance study shows that the proposed algorithm significantly reduces the memory consumption compared with FP-growth for many synthetic and real datasets, especially when support thresholds are low.