PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth

J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, M. C. Hsu

Research output: Contribution to conferencePaperpeer-review

Abstract

Sequential pattern mining is an important data mining problem with broad applications. It is challenging since one may need to examine a combinatorially explosive number of possible subsequence patterns. Most of the previously developed sequential pattern mining methods follow the methodology of Apriori which may substantially reduce the number of combinations to be examined. However Apriori still encounters problems when a sequence database is large and/or when sequential patterns to be mined are numerous and/or long. In this paper, we propose a novel sequential pattern mining method, called PrefixSpan (i.e., Prefix-projected Sequential pattern mining), which explores prefix-projection in sequential pattern mining. PrefixSpan mines the complete set of patterns but greatly reduces the efforts of candidate subsequence generation. Moreover, prefix-projection substantially reduces the size of projected databases and leads to efficient processing. Our performance study shows that PrefixSpan outperforms both the Apriori-based GSP algorithm and another recently proposed method, FreeSpan, in mining large sequence databases.

Original languageEnglish (US)
Pages215-224
Number of pages10
StatePublished - Jan 1 2001
Externally publishedYes
Event17th International Conference on Data Engineering - Heidelberg, Germany
Duration: Apr 2 2001Apr 6 2001

Other

Other17th International Conference on Data Engineering
Country/TerritoryGermany
CityHeidelberg
Period4/2/014/6/01

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth'. Together they form a unique fingerprint.

Cite this