Frequent tree pattern mining: A survey
Intelligent Data AnalysisPublished 5 November 2010
Aı́da Jiménez, Fernando Berzal, Juan-Carlos Cubero
Citations28
SJR quartileQ3
SJR score0.29
SNIP0.45
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper examines some of the most relevant tree mining algorithms and compare them in order to highlight their similarities and differences.
Abstract
The use of non-linear data structures is becoming more and more common in many data mining scenarios. Trees, in particular, have drawn the attention of researchers as the simplest of non-linear data structures. Many tree mining algorithms have been proposed in the literature and this paper surveys some of the recent work that has been performed in this area. We examine some of the most relevant tree mining algorithms and compare them in order to highlight their similarities and differences.
Keywords
Computer Science
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +1 more
gSpan: graph-based substructure pattern mining
2,030 Citations2003Xifeng Yan, Jiawei Han
A novel algorithm called gSpan (graph-based substructure pattern mining), which discovers frequent substructures without candidate generation by building a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label.
PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
1,791 Citations2005Jian Pei, Jiawei Han +5 more
This work proposes a novel sequential pattern mining method, called Prefixspan (i.e., Prefix-projected - Ettern_ mining), which explores prejxprojection in sequential pattern Mining, and shows that Pre fixspan outperforms both the Apriori-based GSP algorithm and another recently proposed method; Frees pan, in mining large sequence data bases.
ACM SIGKDD Explorations NewsletterWeb mining research
1,439 Citations2000Raymond Kosala, Hendrik Blockeel
This paper surveys the research in the area of Web mining, point out some confusions regarded the usage of the term Web mining and suggest three Web mining categories, which are then situate some of the research with respect to these three categories.
Algorithms and computation in mathematicsGraphs, Networks and Algorithms
502 Citations2007Dieter Jungnickel
A quickstart in frequent structure mining can make a difference
471 Citations2004Siegfried Nijssen, Joost N. Kok
The GrAph/Sequence/Tree extractiON (Gaston) algorithm is introduced that implements the "quickstart principle", which is based on the fact that these classes of structures are contained in each other, thus allowing for the development of structure mining algorithms that split the search into steps of increasing complexity.
Efficiently mining frequent trees in a forest
467 Citations2002Mohammed 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 finds that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties.
Mining molecular fragments: finding relevant substructures of molecules
438 Citations2003Christian Borgelt, Michael R. Berthold
An algorithm to find fragments in a set of molecules that help to discriminate between different classes of for instance, activity in a drug discovery context is presented, which results in substantially faster search by eliminating the need for frequent, computationally expensive reembeddings and by suppressing redundant search.
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.
XRules
185 Citations2003Mohammed J. Zaki, Charų C. Aggarwal
This paper discusses the problem of rule based classification of XML data by using frequent discriminatory substructures within XML documents and shows the effectiveness of the method with respect to other classifiers.
Lecture notes in computer scienceDiscovering Frequent Substructures in Large Unordered Trees
171 Citations2003Tatsuya Asai, Hiroki Arimura +2 more
An efficient algorithm Unot is presented that computes all frequent labeled unordered trees appearing in a large collection of data trees with frequency above a user-specified threshold and finds each frequent pattern T in O(kb 2 m) per pattern.
IEEE Transactions on Knowledge and Data EngineeringMining closed and maximal frequent subtrees from databases of labeled rooted trees
130 Citations2005Yün Chi, Yi Xia +2 more
CMTreeMiner is presented, a computationally efficient algorithm that discovers only closed and maximal frequent subtrees in a database of labeled rooted trees, where the rooted trees can be either ordered or unordered.
Fundamenta InformaticaeEfficiently Mining Frequent Embedded Unordered Trees
129 Citations2004Mohammed J. Zaki
This paper introduces SLEUTH, an efficient algorithm for mining frequent, unordered, embedded subtrees in a database of labeled trees, and gives the first algorithm that enumerates all embedded, un ordered trees.
Challenges in mining social network data
128 Citations2007Jon Kleinberg
A family of attacks such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes is described, suggesting that anonymization contains pitfalls even in very simple settings.
Efficient data mining for maximal frequent subtrees
122 Citations2004YingJian Xiao, Jun Yao
A new type of tree mining is defined, which uncovers maximal frequent induced subtrees from a database of unordered labeled trees and a novel algorithm, PathJoin, which uses a compact data structure, FST-Forest, which compresses the trees and still keeps the original tree structure.
Xproj
121 Citations2007Charų C. Aggarwal, Na Ta +3 more
This paper proposes an effective clustering algorithm for XML data which uses substructures of the documents in order to gain insights about the important underlying structures and proposes new ways of using multiple sub-structuralinformation in XML documents to evaluate the quality of intermediate cluster solutions.
Lecture notes in computer scienceOptimized Substructure Discovery for Semi-structured Data
120 Citations2002Kenji Abe, Shinji Kawasoe +3 more
An efficient algorithm is presented that discovers the best labeled ordered trees that optimize a given statistical measure, such as the information entropy and the classification accuracy, in a collection of semi-structured data.
HybridTreeMiner: an efficient algorithm for mining frequent rooted trees and free trees using canonical forms
110 Citations2004Yün Chi, Yirong Yang +1 more
HybridTreeMiner is a computationally efficient algorithm that discovers all frequently occurring subtrees in a database of rooted unordered trees by traversing an enumeration tree that systematically enumerates all subtrees.
Indexing and mining free trees
109 Citations2004Y. Chi, Yining Yang +1 more
This work presents FreeTreeMiner, a computationally efficient algorithm that discovers all frequently occurring subtrees in a database of free trees and defines a novel representation, the canonical form, for rooted trees and extends the definition to free trees.
Efficient discovery of frequent unordered trees
102 Citations2003Siegfried Nijssen, Joost N. Kok
A new algorithm for mining unordered frequent induced subtrees in an ordered data tree is proposed and it is shown that the complexity of enumerating unordered trees is not higher than the complexityof enumerating ordered trees.
Genome-scale disk-based suffix tree indexing
96 Citations2007Benjarath Phoophakdee, Mohammed J. Zaki
TRELLIS is a novel disk-based suffix tree algorithm which effectively scales up to genome-scale sequences and can index the entire human genome using 2GB of memory in about 4 hours and can recover all its suffix links within 2 hours.
The VLDB JournalPractical methods for constructing suffix trees
87 Citations2005Yuanyuan Tian, Sandeep Tata +2 more
This paper presents a new disk-based suffix tree construction algorithm that is based on a sort-merge paradigm, and shows that for constructing very large suffix trees with very little resources, this algorithm is more efficient than TDD.
Lecture notes in computer scienceIMB3-Miner: Mining Induced/Embedded Subtrees by Constraining the Level of Embedding
77 Citations2006Henry Tan, Tharam S. Dillon +3 more
This paper proposes an efficient approach to tackle the complexity of mining embedded subtrees by utilizing a novel Embedding List representation, Tree Model Guided enumeration, and introducing the Level ofEmbedding constraint.
Frequent free tree discovery in graph data
72 Citations2004Ulrich Rückert, Stefan Krämer
This paper is investigating the middle ground between these two extremes: mining free trees in graph data, and defining free trees and their canonical form, before presenting FreeTreeMiner, an algorithm making efficient use of this canonical form during search.
DRYADE: A New Approach for Discovering Closed Frequent Trees in Heterogeneous Tree Databases
67 Citations2005Alexandre Termier, M.-C. Rousset +1 more
This algorithm uses a relaxed tree inclusion definition, making the problem more complex (checking tree inclusion is NP-complete), but allowing to mine highly heterogeneous databases, and discovers only closed frequent tree patterns.
TRIPS and TIDES
43 Citations2006Shirish Tatikonda, Srinivasan Parthasarathy +1 more
This paper proposes novel algorithms to mine frequent subtrees from a database of rooted trees to achieve up to several orders of magnitude speedup on real datasets when compared to state-of-the-art tree mining algorithms.
UnipiEprints Open Archive (Università di Pisa)Exact Rooted Subtree Matching in Sublinear Time
40 Citations2001Fabrizio Luccio, Antonio Mesa Enriquez +2 more
The problem of exact subtree matching is the one of deciding if a pattern tree P of m vertices is a subtree of a text tree T of n vertices, and, in the affirmative case, finding all the occurrences of P in T, and it is shown how the problem can be solved in Theta(m + log n) time once a proper data structure is built for T in a preprocessing phase which requires TheTA(n) time and space.
AMIOT: Induced Ordered Tree Mining in Tree-Structured Databases
37 Citations2006Shohei Hido, Hiroyuki Kawano
AMIOT algorithm to discover all frequent ordered subtrees in a tree-structured database is presented and it is shown that AMIOT reduces redundant candidate trees and outperforms FREQT algorithm by up to five times in execution time.
UNI3 - efficient algorithm for mining unordered induced subtrees using TMG candidate generation
30 Citations2007Fedja Hadzic, Henry Tan +1 more
The proposed UNI3 algorithm considers both transaction based and occurrence match support, and is motivated by the fact that in many applications of frequent subtree mining the order among siblings is not considered important.
IEEE Transactions on Knowledge and Data EngineeringDiscovering Frequent Agreement Subtrees from Phylogenetic Data
28 Citations2007Shihang Zhang, j.T.L. Wang
The paper establishes a framework for tackling the FAST problem for both rooted and unrooted phylogenetic trees using data mining techniques, and develops a novel canonical form for rooted trees together with a phylogeny-aware tree expansion scheme for generating candidate subtrees level by level.
MB3-Miner: mining eMBedded subTREEs using Tree Model Guided candidate generation
26 Citations2005Hua Tan, TS Dillon +3 more
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.
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.
Lecture notes in computer scienceMining Induced and Embedded Subtrees in Ordered, Unordered, and Partially-Ordered Trees
14 Citations2008Aı́da Jiménez, Fernando Berzal +1 more
This paper introduces a scalable algorithm, POTMiner, that is able to identify both induced and embedded subtrees and, as special cases, it can handle both completely ordered and completely unordered trees.
Efficient Mining of High Branching Factor Attribute Trees
10 Citations2006Alexandre Termier, Marie-Christine Rousset +4 more
It is shown that DryadeParent outperforms the current fastest algorithm, CMTreeMiner, by orders of magnitude on datasets where the frequent patterns have a high branching factor and depth.
Matching in Frequent Tree Discovery
9 Citations2005B. Bringmann
A notion of tree matching for use in frequent tree mining is introduced and it is shown that it generalizes the framework of Zaki while still being more specific than that of Termier et al.
Lecture notes in computer scienceTo See the Wood for the Trees: Mining Frequent Tree Patterns
3 Citations2006Björn Bringmann
It is shown how Zaki's TreeMinerV algorithm can be adapted to employ three of the four notions of tree matching and how they are related to each other.