New techniques for mining frequent patterns in unordered trees

Sen Zhang, Zhihui Du, Jason T.L. Wang

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

We consider a new tree mining problem that aims to discover restrictedly embedded subtree patterns from a set of rooted labeled unordered trees. We study the properties of a canonical form of unordered trees, and develop new Apriori-based techniques to generate all candidate subtrees level by level through two efficient rightmost expansion operations: 1) pairwise joining and 2) leg attachment. Next, we show that restrictedly embedded subtree detection can be achieved by calculating the restricted edit distance between a candidate subtree and a data tree. These techniques are then integrated into an efficient algorithm, named frequent restrictedly embedded subtree miner (FRESTM), to solve the tree mining problem at hand. The correctness of the FRESTM algorithm is proved and the time and space complexities of the algorithm are discussed. Experimental results on synthetic and real-world data demonstrate the effectiveness of the proposed approach.

Original languageEnglish (US)
Article number6878439
Pages (from-to)1113-1125
Number of pages13
JournalIEEE Transactions on Cybernetics
Volume45
Issue number6
DOIs
StatePublished - Jun 1 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Apriori algorithm
  • pattern matching
  • pattern mining and recognition
  • rooted labeled unordered trees.

Fingerprint

Dive into the research topics of 'New techniques for mining frequent patterns in unordered trees'. Together they form a unique fingerprint.

Cite this