A fast algorithm of mining induced subtrees

Induced subtrees mining is of important researching value in the fields of XML documents, bioinformatics, web log and so forth. In this paper, the two conceptions of subtree vector and pruning threshold are proposed, and an algorithm ITMSV (induced subtrees mining based on subtree vector) is presented to discover frequent induced subtrees quickly by taking full advantages of the features of subtree vector and combining with the hash table. The algorithm, as a result of constructing a multi-layered data structure, can lessen the time of distinguishing isomorphism during mining, and need scan database only once so that it induces times of scanning and improves the efficiency of algorithm. The experimental result shows that the algorithm ITMSV is more efficient and effective than TreeMiner.