MB3-Miner: mining eMBedded subTREEs using Tree Model Guided candidate generation

Published 1 January 2005

Hua Tan, TS Dillon, Fedja Hadzic, Ling Feng, Elizabeth Chang

Citations26

TL;DR

This paper presents the mathematical model of a breadth-first-search Tree Model Guided (TMG) candidate generation approach, and proposes a novel and unique embedding list representation that is suitable for describing embedded subtrees.

Abstract

Tree mining has many useful applications in areas such as Bioinformatics, XML mining, Web mining, etc. In general, most of the formally represented information in these domains is a tree structured form. In this paper we focus on mining frequent embedded subtrees from databases of rooted labeled ordered subtrees. We propose a novel and unique embedding list representation that is suitable for describing embedded subtrees. This representation is completely different from the string-like or conventional adjacency list representation previously utilized for trees. We present the mathematical model of a breadth-first-search Tree Model Guided (TMG) candidate generation approach previously introduced in [8]. The key characteristic of the TMG approach is that it enumerates fewer candidates by ensuring that only valid candidates that conform to the structural aspects of the data are generated as opposed to the join approach. Our experiments with both synthetic and real-life datasets provide comparisons against one of the state-of-the-art algorithms, TreeMiner [15], and they demonstrate the effectiveness and the efficiency of the technique.

Keywords

Computer Science

Fast vertical mining using diffsets

586 Citations2003Mohammed J. Zaki, Karam Gouda

This paper presents a novel vertical data representation called Diffset, that only keeps track of differences in the tids of a candidate pattern from its generating frequent patterns, and shows that diffsets drastically cut down the size of memory required to store intermediate results.

IEEE Transactions on Knowledge and Data EngineeringAn efficient algorithm for discovering frequent subgraphs

351 Citations2004M. Kuramochi, George Karypis

The results show that despite the underlying complexity associated with frequent subgraph discovery, FSG is effective in finding all frequently occurring subgraphs in data sets containing more than 200,000 graph transactions and scales linearly with respect to the size of the data set.

IEEE Transactions on Knowledge and Data EngineeringEfficiently mining frequent trees in a forest: algorithms and applications

308 Citations2005Mohammed J. Zaki

This work presents TREEMINER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list, and contrasts it with a pattern matching tree mining algorithm (PATTERNMATCHER), and also compares it with TREEMinERD, which counts only distinct occurrences of a pattern.

Fundamenta InformaticaeFrequent Subtree Mining - An Overview

264 Citations2004Yün Chi, Richard R. Muntz +2 more

An overview of a broad range of tree mining algorithms focusing on the common theoretical foundations of the current frequent subtree mining algorithms and their relationship with their counterparts in frequent itemset mining is provided.

TreeFinder: a first step towards XML data mining

185 Citations2003Alexandre Termier, M.-C. Rousset +1 more

This paper considers the problem of searching frequent trees from a collection of tree-structured data modeling XML data, and shows that TreeFinder reaches completeness or falls short for a range of experimental settings.

Elsevier eBooksEfficient Mining of XML Query Patterns for Caching

118 Citations2003Liang Huai Yang, Mong Li Lee +1 more

Theorems are developed to prove that only a small subset of the generated candidate patterns needs to undergo expensive tree containment tests, and it is demonstrated how the frequent query patterns can be used to improve caching performance.

Discovering typical structures of documents

115 Citations1998Ke Wang, Huiqing Liu

This work studies the problem of discovering “typical” structures of a collection of such documents, where the user specifies the minimum frequency of a typical structure.

Lecture notes in computer scienceEfficient Pattern-Growth Methods for Frequent Tree Pattern Mining

100 Citations2004Chen Wang, Mingsheng Hong +4 more

An extensive performance study shows that the two newly developed algorithms outperform TreeMinerV [13], one of the fastest methods proposed before, in mining large databases.

Lecture notes in computer scienceAn XML-Enabled Association Rule Framework

45 Citations2003Ling Feng, Tharam S. Dillon +2 more

This paper proposes an extended XML-enabled association rule framework, which is flexible and powerful enough to represent both simple and complex structured association relationships inherent in XML data.

X3-Miner: Mining Patterns from XML Database

23 Citations2005Hua Tan, TS Dillon +3 more

This work proposes an approach, X3-Miner, that efficiently extracts patterns from a large XML data set, and overcomes the challenges by exploring the use of a model validating approach in deducing the number of candidates generated by taking into account the semantics embedded in the tree-like structure in an XML database.