efficiently mining frequent trees in a forest
Mining frequent trees is very useful in domains like bioinformatics, web mining, mining semistructured data, and so on. We formulate the problem of mining (embedded) subtrees in a forest of rooted, labeled, and ordered trees. We present T REE M INER , a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list. We contrast T REE M INER with a pattern matching tree mining algorithm (P ATTERN M ATCHER ). We conduct detailed experiments to test the performance and scalability of these methods. We find that T REE M INER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties. We also present an application of tree mining to analyze real web logs for usage patterns.
mining tree tree domain bioinformatics web web mining data embedding algorithm data structures pattern match pattern experience test performance scalability method factor applications trees