Can I read TRIPS and TIDES: new algorithms for tree mining on EtoBox?

TRIPS and TIDES: new algorithms for tree mining by Shirish Tatikonda; Srinivasan Parthasarathy; Tahsin Kurc is a scholarly article available to read on EtoBox.

What is TRIPS and TIDES: new algorithms for tree mining about?

Recent research in data mining has progressed from mining frequent itemsets to more general and structured patterns like trees and graphs. In this paper, we address the problem of frequent subtree mining that has proven to be viable in a wide range of applications such as bioinformatics, XML processing, computational linguistics, and web usage mining. We propose novel algorithms to mine frequent subtrees from a database of rooted trees. We evaluate the use of two popular sequential encodings of trees to systematically generate and evaluate the candidate patterns. The proposed approach is very generic and can be used to mine embedded or induced subtrees that can be labeled, unlabeled, ordered, unordered, or edge-labeled. Our algorithms are highly cache-conscious in nature because of the compact and simple array-based data structures we use. Typically, L1 and L2 hit rates above 99% are observed. Experimental evaluation showed that our algorithms can achieve up to several orders of magnitude speedup on real datasets when compared to state-of-the-art tree mining algorithms.

Author

Shirish Tatikonda; Srinivasan Parthasarathy; Tahsin Kurc

Publisher

ACM Press

Published

2006

Language

EN