Efficiently mining frequent trees in a forest

By Mohammed J. Zaki. Knowledge Discovery and Data Mining, 2002

599 citations recorded by the source corpus.

Mining frequent trees is very useful in domains like bioinformatics, web mining, mining semistructured data, and so on. We formulate the problem of mining (embedded) subtrees in a forest of rooted, labeled, and ordered trees. We present TREEMINER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list. We contrast TREEMINER with a pattern matching tree mining algorithm (PATTERNMATCHER). We conduct detailed experiments to test the performance and scalability of these methods. We find that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties. We also present an application of tree mining to analyze real web logs for usage patterns.

Subfields: Computer Networks and Communications, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/fcab6748230e7d0742292b999743510e4b3b1778

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

In Signal Processing

Citations in the corpus

An efficient algorithm for discovering frequent subgraphs (2004, background): “[4] and Zaki [48] that operate on rooted ordered trees and find all frequent subtrees.”
SPIN: mining maximal frequent subgraphs from graph databases (2004, methodology): “Our current work benefits extensively from existing algorithms for maximal itemset mining such as [3, 7] and frequent subtree mining algorithms [1, 22 ].”
A Boosting Algorithm for Classification of Semi-Structured Text (2004, methodology): “(Abe et al., 2002; Zaki, 2002) Let t and t (cid:48) be labeled ordered trees.”
State of the art of graph-based data mining (2003, background): “The objective data formats in the beginning of the field were limited to relational tables and transactions where each instance is represented by one row in a table or one transaction represented as a set.”
Frequent Subtree Mining – An Overview (2004, methodology): “The data set we used is T1M, which is obtained using the generator given b y Zaki [48].”
Mining idioms from source code (2014, background): “This task is called frequent tree mining, and has been the subject of some work in the data mining literature [25, 49, 54, 55].”
gSpan: graph-based substructure pattern mining (2002, methodology): “This restriction is similar to TreeMinerV’s equivalence class extension [8] and FREQT’s rightmost expansion [2] in frequent tree discovery.”
2015 Ieee International Conference on Big Data (big Data) Task-based Recommendation on a Web-scale (unknown): “The research of FPM investigates algorithms for a wide scope of data mining problems, including frequent item set mining [22] , association rule mining [23], frequent sequence mining [24], [25], [26], and frequent tree or graph mining [27], [28].”
Efficiently mining frequent trees in a forest: algorithms and applications (2005, methodology): “As described in [40], we represent a tree T by its string encoding, denoted T , generated as follows: Add vertex labels to T in a depthfirst preorder traversal of T and add a unique symbol À1 = 2 L whenever we backtrack from a child to its parent.”
Frequent pattern mining: current status and future directions (2007, methodology): “2001), TreeMinerV (Zaki 2002), andFREQT (Asai et al.”
Modelling input texts: from Tree Kernels to Deep Learning (2015, background): “, millions of instances, mining the most frequent substructures [192] becomes slow.”
Cyclic pattern kernels for predictive graph mining (2004, background): “[3, 34 ] for further details on canonical string representations of trees.”
A quickstart in frequent structure mining can make a difference (2004, methodology): “Diﬀer-ent codes have been proposed, among which DFS codes (in gSpan [14]), adjacency matrices (in FFSM [5]) and tree codes with backtrack symbols (in FreeTreeMiner [2] and TreeMiner [15]).”