Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Pascal Poncelet <>
Submitted on : Friday, April 5, 2019 - 7:11:38 PM
Last modification on : Tuesday, June 15, 2021 - 2:57:31 PM
Long-term archiving on: : Saturday, July 6, 2019 - 4:16:11 PM


Files produced by the author(s)



Federico del Razo Lopez, Anne Laurent, Pascal Poncelet, Maguelonne Teisseire. Tree mining: Equivalence classes for candidate generation. Intelligent Data Analysis, IOS Press, 2009, 13 (4), pp.555-573. ⟨10.3233/IDA-2009-0381⟩. ⟨lirmm-00798708⟩



Record views


Files downloads