Mining Closed and Maximal Frequent Induced Free Subtrees

Author

Shiozaki, Hitohiro ; Ozaki, Tomonobu ; Ohkawa, Takenao

Author_Institution

Graduate Sch. of Sci. & Technol., Kobe Univ.

fYear

2006

fDate

Dec. 2006

Firstpage

14

Lastpage

18

Abstract

Mining frequent tree patterns is an important problem, since tree structures are used in various fields such as computational biology, XML databases, and so on. However, mining all frequent subtrees is sometimes infeasible because of the combinatorial explosion. In this paper, by combining an efficient algorithm for enumerating free trees and the pruning techniques for mining closed and maximal rooted trees, we present an efficient algorithm named CMFree-TreeMiner that discovers only closed and maximal frequent induced free subtrees in a database of labeled free trees. Experimental results show the effectiveness of the proposed algorithm

Keywords

data mining; tree data structures; trees (mathematics); CMFree-TreeMiner; combinatorial explosion; frequent induced free subtrees; frequent tree pattern mining; labeled free trees; pruning techniques; rooted trees; tree structures; Computational biology; Data mining; Databases; Explosions; Frequency; Labeling; Pattern recognition; Tree data structures; Tree graphs; XML;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on

Conference_Location

Hong Kong

Print_ISBN

0-7695-2702-7

Type

conf

DOI

10.1109/ICDMW.2006.111

Filename

4063590