PrePost(+): An efficient N-lists-based algorithm for mining frequent itemsets via Children-Parent Equivalence pruning

摘要

N-list is a novel data structure proposed in recent years. It has been proven to be very efficient for mining frequent itemsets. In this paper, we present PrePost(+), a high-performance algorithm for mining frequent itemsets. It employs N-list to represent itemsets and directly discovers frequent itemsets using a set-enumeration search tree. Especially, it employs an efficient pruning strategy named Children-Parent Equivalence pruning to greatly reduce the search space. We have conducted extensive experiments to evaluate PrePost(+) against three state-of-the-art algorithms, which are PrePost, FIN, and FP-growth*, on six various real datasets. The experimental results show that PrePost(+) is always the fastest one on all datasets. Moreover, PrePost(+) also demonstrates good performance in terms of memory consumption since it use only a litter more memory than FP-growth* and less memory than PrePost and FIN. (C) 2015 Elsevier Ltd. All rights reserved.