, Raaele Perego

In this paper we review the Apriori class of Data Mining algorithms for solving the Frequent Set Counting problem, and propose DCP, a new algorithm which makes several improvements on the classic Apriori. Our goal was to optimize the most time consuming phases of Apriori algorithms for problems characterized by short or medium length frequent patterns. For these problems, the initial iterations of the algorithm, during which small sets of items (itemsets) are counted, are the most expensive. The main enhancements introduced by DCP are the use of an innovative method for storing candidate itemsets and counting their support, and the exploitation of eective pruning tech-niques which signicantly reduce the size of the dataset as execution progresses. We implemented and engineered several algorithms belonging to the Apriori class, and conducted in-depth experimental evaluations to compare them, by taking into account not only execution time, but also virtual mem-ory usage and I/O activity. When possible, locality of data and pointer dereferencing were optimized due to their importance with respect to developments in computer architectures. The results conrm that our new algorithm, DCP, signicantly outperforms the others previously proposed. Our test bed was a Pentium-based Linux workstation, while the datasets used for the tests were synthetically generated