From sequential pattern mining to structured pattern mining: A pattern-growth approach

Jia Wei Han, Jian Pei, Xi Feng Yan

Research output: Contribution to journalArticle

Abstract

Sequential pattern mining is an important data mining problem with broad applications. However, it is also a challenging problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Recent studies have developed two major classes of sequential pattern mining methods: (1) a candidate generation-and-test approach, represented by (i) GSP, a horizontal format-based sequential pattern mining method, and (ii) SPADE, a vertical format-based method; and (2) a pattern-growth method, represented by PrefixSpan and its further extensions, such as gSpan for mining structured patterns. In this study, we perform a systematic introduction and presentation of the pattern-growth methodology and study its principles and extensions. We first introduce two interesting pattern-growth algorithms, FreeSpan and PrefixSpan, for efficient sequential pattern mining. Then we introduce gSpan for mining structured patterns using the same methodology. Their relative performance in large databases is presented and analyzed. Several extensions of these methods are also discussed in the paper, including mining multi-level, multi-dimensional patterns and mining constraint-based patterns.

Original languageEnglish (US)
Pages (from-to)257-279
Number of pages23
JournalJournal of Computer Science and Technology
Volume19
Issue number3
DOIs
StatePublished - May 2004

Keywords

  • Data mining
  • Performance analysis
  • Scalability
  • Sequential pattern mining
  • Structured pattern mining

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'From sequential pattern mining to structured pattern mining: A pattern-growth approach'. Together they form a unique fingerprint.

  • Cite this