Author_Institution :
Hubei Province Key Lab. of Intell. Robot, Wuhan Inst. of Technol., Wuhan, China
Abstract :
Mining frequent sub tree from databases of labeled trees is a new research field that has many practical applications in areas such as computer networks, Web mining, bioinformatics, XML document mining, etc. These applications share a requirement for the more expressive power of labeled trees to capture the complex relations among data entities. In this paper an efficient algorithm is introduced for mining frequent, ordered, embedded sub tree in tree-like databases. Using a new data structure called scope-list, which is a canonical representation of tree node, the algorithm first generates all candidate trees, then enumerates embedded, ordered trees, finally joins scope-list to compute frequency of embedded ordered trees. Experiments show the performance of the algorithm is about 15% better than other similar mining methods and has good scale-up properties.
Keywords :
data mining; database management systems; trees (mathematics); embedded ordered trees; labeled trees; mining frequent embedded subtree; scope-list data structure; tree-like databases; Algebra; Algorithm design and analysis; Arrays; Data mining; Databases; Encoding; Vegetation; Canonical representation; Embedded Subtree; Enumeration tree; Frequent Subtree Mining;