Tree mining: Equivalence classes for candidate generation

Abstract : With the rise of active research fields such as bioinformatics, taxonomies and the growing use of XML documents, tree data are playing a more and more important role. Mining for frequent subtrees from these data is thus an active research problem and traditional methods (e.g., itemset mining from transactional databases) have to be extended in order to tackle the problem of handling tree-based data. Some approaches have been proposed in the literature, mainly based on generate-and-prune methods. However, they generate a large volume of candidates before pruning them, whereas it could be possible to discard some solutions as they contain unfrequent subtrees. We thus propose a novel approach, called pivot, based on equivalence classes in order to decrease the number of candidates. Three equivalence classes are defined, the first one relying on a right equivalence relation between two trees, the second one on a left equivalence relation, and the third one on the ground of a root equivalence relation. In this paper, we introduce this new method, showing that it is complete (i.e., no frequent subtree is forgotten), and efficient, as illustrated by the experiments led on synthetic and real datasets.
Type de document :
Article dans une revue
Intelligent Data Analysis, IOS Press, 2009, 13 (4), pp.555-573
Liste complète des métadonnées
Contributeur : Pascal Poncelet <>
Soumis le : dimanche 10 mars 2013 - 02:46:05
Dernière modification le : jeudi 24 mai 2018 - 15:59:23


  • HAL Id : lirmm-00798708, version 1


Del Razo Lopez Federico, Anne Laurent, Pascal Poncelet, Maguelonne Teisseire. Tree mining: Equivalence classes for candidate generation. Intelligent Data Analysis, IOS Press, 2009, 13 (4), pp.555-573. 〈lirmm-00798708〉



Consultations de la notice