ALCOMFT-TR-03-198

Jaume Baixeries, Gemma Casas-Garriga and Jose Luis Balcazar
A Best-First Strategy For Finding Frequent Sets
Barcelona. Work packages 1 and 4. December 2003.

Abstract: The association rule discovery problem consists in identifying frequent itemsets in a database and, then, forming conditional implication rules among them. The algorithmically most difficult part of this task is finding all frequent sets. There exists a wealth of algorithms both for the problem as such and for variations, particular cases, and generalizations. Except for some recent, fully different approaches, most algorithms can be seen either as a breadth-first search or a depth-first search of the lattice of itemsets. We propose a way of developing best-first search strategies, and explain how the notion can be combined with other related techniques.

Postscript file: ALCOMFT-TR-03-198.ps.gz (38 kb).