Efficient data mining for maximal frequent subtrees

Published 23 April 2004

YingJian Xiao, Jun Yao

DOI10.1109/icdm.2003.1250943

Citations122

TL;DR

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.

Abstract

A new type of tree mining is defined, which uncovers maximal frequent induced subtrees from a database of unordered labeled trees. A novel algorithm, PathJoin, is proposed. The algorithm uses a compact data structure, FST-Forest, which compresses the trees and still keeps the original tree structure. PathJoin generates candidate subtrees by joining the frequent paths in FST-Forest. Such candidate subtree generation is localized and thus substantially reduces the number of candidate subtrees. Experiments with synthetic data sets show that the algorithm is effective and efficient.

Keywords

Computer Science

ACM SIGMOD RecordMining frequent patterns without candidate generation

6,360 Citations2000Jiawei Han, Jian Pei +1 more

Mining sequential patterns

5,115 Citations2002R. K. Agrawal, Ramakrishnan Srikant

Three algorithms are presented to solve the problem of mining sequential patterns over databases of customer transactions, and empirically evaluating their performance using synthetic data shows that two of them have comparable performance.

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.

View PDF

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.

View PDF

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.

IEEE Transactions on Knowledge and Data EngineeringEfficient data mining for path traversal patterns

540 Citations1998Ming-Syan Chen⋆, Jong Soo Park +1 more

The authors explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access and show that the option of selective scan is very advantageous and can lead to prominent performance improvement.

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.

Algorithmics and applications of tree and graph searching

385 Citations2002Dennis Shasha, Jason T. L. Wang +1 more

This paper surveys both algorithms and applications for generalizing keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems.

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.

View PDF