Affiliations: Computer Science Department, Rensselaer Polytechnic
Institute, Troy NY 12180, USA. zaki@cs.rpi.edu
Note: [] Address for correspondence: Lally 307, CSCI, RPI, 110 8th St,
Troy NY 12180, USA
Abstract: Mining frequent trees is very useful in domains like bioinformatics,
web mining, mining semi-structured data, and so on. In this paper we introduce
SLEUTH, an efficient algorithm for mining frequent, unordered, embedded subtrees
in a database of labeled trees. The key contributions of our work are as
follows: We give the first algorithm that enumerates all embedded, unordered
trees. We propose a new equivalence class extension scheme to generate all
candidate trees. We extend the notion of scope-list joins to compute frequency
of unordered trees. We conduct performance evaluation on several synthetic and
real datasets to show that SLEUTH is an efficient algorithm, which has
performance comparable to TreeMiner, that mines only ordered trees.
Keywords: Tree Mining, Embedded Trees, Unordered Trees
