Discovering Frequent Substructures in Large Unordered Trees
Lecture notes in computer sciencePublished 1 January 2003
Tatsuya Asai, Hiroki Arimura, Takeaki Uno, S Nakano
Citations171
SJR quartileQ2
SJR score0.35
SNIP0.55
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
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.
Abstract
In this paper, we study a frequent substructure discovery problem in semi-structured data. We present an efficient algorithm Unotthat computes all frequent labeled unordered trees appearing in a large collection of data trees with frequency above a user-specified threshold. The keys of the algorithm are efficient enumeration of all unordered trees in canonical form and incremental computation of their occurrences. We then show that Unotdiscovers each frequent pattern T in O(kb 2 m) per pattern, where k is the size of T, b is the branching factor of the data trees, and m is the total number of occurrences of T in the data trees.
Keywords
Computer Science
Series on software engineering and knowledge engineeringData Structures and Algorithms
2,131 Citations2003
The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.
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.
Frequent subgraph discovery
1,063 Citations2002M. Kuramochi, George Karypis
The empirical results show that the algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though it has to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery.
Lecture notes in computer scienceAn Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
1,029 Citations2000Akihiro Inokuchi, Takashi Washio +1 more
A novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set through the extended algorithm of the basket analysis is proposed.
Discrete Applied MathematicsReverse search for enumeration
760 Citations1996David Avis, Komei Fukuda
This paper develops the reverse search technique in a general framework and shows its broader applications to various problems in operations research, combinatorics, and geometry, and proposes new algorithms for listing.
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.
Efficient Substructure Discovery from Large Semi-structured Data
363 Citations2002Tatsuya Asai, Kenji Abe +4 more
Extracting schema from semistructured data
224 Citations1998Svetlozar Nestorov, Serge Abiteboul +1 more
It is established that the general problem of finding an optimal form of semistructured data based on labeled, directed graphs is NP-hard, but some heuristics and techniques based on clustering that allow efficient and near-optimal treatment of the problem are presented.
Knowledge Discovery and Data MiningSubstructure discovery in the SUBDUE system
217 Citations1994Lawrence B. Holder, Diane J. Cook +1 more
The SUBDUE system, which uses the minimum description length (MDL) principle to discover substructures that compress the database and represent structural concepts in the data, is described.
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.
Kyushu University Institutional Repository (QIR) (Kyushu University)Efficient Substructure Discovery from Large Semi-structed Data
183 Citations2001Tatsuya Asai, 達哉 浅井 +10 more
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.
Computing frequent graph patterns from semistructured data
167 Citations2003Natalia Vanetik, Ehud Gudes +1 more
A new algorithm for mining graph data is proposed, based on a novel definition of support, that can be useful for many applications, including: compact representation of source information and a road-map for browsing and querying information sources.
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.
Schema discovery for semistructured data
71 Citations1997Ke Wang, Huiqing Liu
This work motivates the schema discovery in this general setting and proposes a framework and algorithm for it and applies the framework to a real Web database, the Internet Movies Database, to discover typical schema of most voted movies.
Information Processing LettersEfficient generation of plane trees
56 Citations2002Shin-ichi Nakano
This paper gives a simple algorithm to generate all rooted plane trees with at most n vertices that uses O(n) space and generates such trees in O(1) time per tree without duplications.
Online algorithms for mining semi-structured data stream
55 Citations2003Tetsuya Asai, Hiroki Arimura +3 more
An online algorithm StreamT is presented that receives fragments of an unseen possibly infinite semi-structured data in the document order through a data stream, and can return the current set of frequent patterns immediately on request at any time.
Lecture notes in computer scienceDiscovery of Frequent Tag Tree Patterns in Semistructured Web Documents
52 Citations2002Tetsuhiro Miyahara, Yusuke Suzuki +4 more
This work proposes a new method for discovering frequent tree structured patterns in semistructured Web documents by using a tag tree pattern as a hypothesis, and presents an algorithm for generating all maximally frequent tag tree patterns.
Lecture notes in computer scienceA Fast Algorithm for Enumerating Bipartite Perfect Matchings
49 Citations2001Takeaki Uno
This paper proposes an algorithm for enumerating all the perfect matchings included in a given bipartite graph G = (V,E) so that the current fastest algorithm takes O(|V|) time per perfect matching.
Efficient Generation of Rooted Trees
44 Citations2003Shin-ichi Nakano, Takeaki Uno
An algorithm to generate all rooted trees with at most n vertices in constant time on average, that clarifies a simple relation among the trees, that is a family tree of trees, and outputs trees based on the relation.
Exact learning of unordered tree patterns from queries
23 Citations1999Thomas R. Amoth, Paul Cull +1 more
Unordered trees and forests are shown to be learnable with an alternative matching semantics that allows an instance to have extra children at each node.