Istituto di Scienza e Tecnologie dell'Informazione     
Bonchi F., Giannotti F., Mazzanti A., Pedreschi D. Adaptive Constraint Pushing in Frequent Pattern Mining. In: Knowledge Discovery in Databases: PKDD 2003 (Cavtat-Dubrovnik, Croatia, 22-26 September 2003). Proceedings, p. 12. Nada Lavrac and Dragan Gamberger and Hendrik Blockeel and Ljupco (eds.). (Lecture Notes in Computer Science, vol. 2838). Springer, 2003.
Pushing monotone constraints in frequent pattern mining can help pruning the search space, but at the same time it can also reduce the effectiveness of anti-monotone pruning. There is a clear tradeoff. Is it better to exploit more monotone pruning at the cost of less anti-monotone pruning, or viceversa? The answer depends on characteristics of the dataset and the selectivity of constraints. In this paper, we deeply characterize this trade-off and its related computational problem. As a result of this characterization, we introduce an adaptive strategy, named ACP (Adaptive Constraint Pushing) which exploits any conjunction of monotone and anti-monotone constraints to prune the search space, and level by level adapts the pruning to the input dataset and constraints, in order to maximize efficiency.
URL: http://springerlink.metapress.com/app/home/contribution.asp?wasp=16rgpkvwxqh6kd
Subject Data Mining
H. Information Systems

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional