Transactional Tree Mining

Abstract

In the transactional setting of finding frequent embedded patterns from a large collection of tree-structured data, the crucial step is to decide whether a tree pattern is subtree homeomorphic to a database tree. Our extensive study on the properties of real-world tree-structured datasets reveals that while many vertices in a database tree may have the same label, no two vertices on the same path are identically labeled. In this paper, we exploit this property and propose a novel and efficient method for deciding whether a tree pattern is subtree homeomorphic to a database tree. Our algorithm is based on a compact data-structure, called EMET , that stores all information required for subtree homeomorphism. We propose an efficient algorithm to generate EMET s of larger patterns using EMET s of the smaller ones. Based on the proposed subtree homeomorphism method, we introduce TTM , an effective algorithm for finding frequent tree patterns from rooted ordered trees. We evaluate the efficiency of TTM on several real-world and synthetic datasets and show that it outperforms well-known existing algorithms by an order of magnitude.