Levelwise Search of Frequent Patterns
Buchtitel: Actes des 16 Journ Bases de Donn Avanc, Blois, France, 24-27 Octobre 2000
In this paper, we propose the algorithm Pascal which introduces a novel op- timization of the well-known algorithm Apriori. Being provided with a given minsup threshold, Pascal discovers all frequent patterns by performing as few counting as possible. In order to derive the support of larger patterns without accessing the database whenever it is possible, we use the knowledge about the support of some of their sub-patterns, the so-called key patterns. Experiments comparing Pascal to the three algorithms Apriori, Close and Max-Miner, each of which being representative of a frequent patterns discovery strategy, show that Pascal is the most eÆcient algorithm for extracting patterns from strongly correlated data. Moreover, its execution times are equivalent to those of Apriori and Max-Miner when data is weakly correlated.