Efficient breadth-first mining of frequent pattern with monotone constraints

The key point of this article is that, in frequent pattern mining, the most appropriate way of exploiting monotone constraints in conjunction with frequency is to use them in order to reduce the input data; this reduction in turn induces a stronger pruning of the search space of the problem. Followi...

Full description

Saved in:
Bibliographic Details
Published in:Knowledge and information systems 2005-08, Vol.8 (2), p.131-153
Main Authors: Bonchi, Francesco, Giannotti, Fosca, Mazzanti, Alessio, Pedreschi, Dino
Format: Article
Language:English
Subjects:
Algorithms
Computation
Data mining
Datasets
Exploitation
Information systems
Laboratories
Pattern analysis
Preprocessing
Prices
Pruning
Searching
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The key point of this article is that, in frequent pattern mining, the most appropriate way of exploiting monotone constraints in conjunction with frequency is to use them in order to reduce the input data; this reduction in turn induces a stronger pruning of the search space of the problem. Following this intuition, we introduce ExAMiner, a breadth-first algorithm that exploits the real synergy of antimonotone and monotone constraints: the total benefit is greater than the sum of the two individual benefits. ExAMiner generalizes the basic idea of the preprocessing algorithm ExAnte (Bonchi et al. 2003(b)), embedding such ideas at all levels of an Apriori-like computation. The resulting algorithm is the generalization of the Apriori algorithm when a conjunction of monotone constraints is conjoined to the frequency antimonotone constraint. Experimental results confirm that this is, so far, the most efficient way of attacking the computational problem in analysis. [PUBLICATION ABSTRACT]
ISSN:0219-1377
0219-3116
DOI:10.1007/s10115-004-0164-7