Efficient Pattern-Growth Methods for Frequent Tree Pattern Mining
Lecture notes in computer sciencePublished 1 January 2004
Chen Wang, Mingsheng Hong, Jian Pei, Haofeng Zhou, Wei Wang, Baile Shi
Citations100
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 extensive performance study shows that the two newly developed algorithms outperform TreeMinerV [13], one of the fastest methods proposed before, in mining large databases.
Abstract
Mining frequent tree patterns is an important research problems with broad applications in bioinformatics, digital library, e-commerce, and so on. Previous studies highly suggested that pattern-growth methods are efficient in frequent pattern mining. In this paper, we systematically develop the pattern growth methods for mining frequent tree patterns. Two algorithms, Chopper and XSpanner, are devised. 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. Furthermore, algorithm XSpanner is substantially faster than Chopper in many cases.
Keywords
Computer Science
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +1 more
Mining frequent patterns without candidate generation
3,195 Citations2000Jiawei Han, Jian Pei +1 more
This study proposes a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develops an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth.
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.
Future Generation Computer SystemsMining generalized association rules
1,617 Citations1997Ramakrishnan Srikant, Rakesh Agrawal
A new interest-measure for rules which uses the information in the taxonomy is presented, and given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules.
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.
Journal of Parallel and Distributed ComputingA Tree Projection Algorithm for Generation of Frequent Item Sets
506 Citations2001Ramesh C. Agarwal, Charų C. Aggarwal +1 more
This paper provides an implementation of the tree projection method which is up to one order of magnitude faster than other recent techniques in the literature and has a well-structured data access pattern which provides data locality and reuse of data for multiple levels of the cache.
Journal of Artificial Intelligence ResearchSubstructure Discovery Using Minimum Description Length and Background Knowledge
481 Citations1994Diane J. Cook, Lawrence B. Holder
A new version of the SUBDUE substructure discovery system based on the minimum description length principle is described, which discovers substructures that compress the original data and represent structural concepts in the data.
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.
H-mine: hyper-structure mining of frequent patterns in large databases
408 Citations2002Jian Pei, Jiawei Han +4 more
This study shows that H-mine has high performance in various kinds of data, outperforms the previously developed algorithms in different settings, and is highly scalable in mining large databases.
Efficient Substructure Discovery from Large Semi-structured Data
363 Citations2002Tatsuya Asai, Kenji Abe +4 more
Lirias (KU Leuven)Finding frequent substructures in chemical compounds
171 Citations1999Luc De Raedt, Hannu Toivonen +1 more
This paper applies data mining to the problem of predicting chemical carcinogenicity, and presents a knowledge discovery method for structured data, where patterns reflect the one- to-many and many-to-many relationships of several tables.
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.
Lecture notes in computer scienceDiscovery of Frequent Tree Structured Patterns in Semistructured Web Documents
48 Citations2001Tetsuhiro Miyahara, Takayoshi Shoudai +3 more
An algorithm for finding all maximally frequent tag tree patterns in semistructured data such as Web documents is presented and some experimental results on XML documents are reported by using the algorithm.
Automated discovery of active motifs in multiple RNA secondary structures
25 Citations1996Jason T. L. Wang, Bruce A. Shapiro +3 more
A method for discovering approximately common motifs in multiple RNA secondary structures using two optimization heuristics based on sampling and pattern matching techniques and demonstrating the utility of these algorithms to conducting the phylogenetic study of RNA sequences obtained from GenBank.