[[alternative]]A Tree-Projected Pattern Growing Method for Mining Frequent Sub-Trees Efficiently

[[abstract]] A new approach, called Tree-Projection algorithm, is proposed in this thesis for mining embedded frequent sub-trees in a forest of rooted, labeled, and ordered trees. This approach greatly reduces the efforts of generating candidate sub-trees. Moreover, Tree-Projection algorithm is extended to solve an additional problem: mining top-K frequent closed sub-trees, where K is the desired number of closed sub-trees to be mined specified by users. According to the various orders of performing tree-projec-tions and whether the dynamic minimum-support raising strategy is applied, three va-rieties of Tree-Projection algorithm are designed: they are named DFS, DFS-TC, and SS-TC, respectively. The experimental results show that, within a limited database size, the increment of runtime for Tree-Projection algorithm keeps stable under the various minimum-supports setting at run-time and arguments setting of data sets. In most cases, Tree-Projection algorithm outperforms the existing TreeMiner algorithm in terms of the execution time. Furthermore, the SS-TC variety of Tree-Projection al-gorithm adopts support descending order to perform tree-projections and raises minimum-support dynamically. When K is small proportional to the number of all closed sub-trees, the SS-TC variety could discover the top-K frequent closed sub-trees by pruning the unnecessary tree-projections dramatically and provide excellent mining efficiency.