FreeSpan: Frequent pattern-projected sequential pattern mining

Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, Qiming Chen, Umeshwar Dayal, Mei Chun Hsu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Sequential pattern mining is an important data mining problem with broad applications. It is also a difficult problem 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 since the Apriori-based method 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 re-examine the sequential pattern mining problem and propose a novel, efficient sequential pattern mining method, called FreeSpan (i.e., Frequent pattern-projected Sequential pattern mining). The general idea of the method is to integrate the mining of frequent sequences with that of frequent patterns and use projected sequence databases to confine the search and the growth of subsequence fragments. FreeSpan mines the complete set of patterns but greatly reduces the efforts of candidate subsequence generation. Our performance study shows that FreeSpan examines a substantially smaller number of combinations of subsequences and runs considerably faster than the Apriori based GSP algorithm.

Original languageEnglish (US)
Title of host publicationProceeding of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
EditorsR. Ramakrishnan, S. Stolfo, R. Bayardo, I. Parsa, R. Ramakrishnan, S. Stolfo, R. Bayardo, I. Parsa
Pages355-359
Number of pages5
StatePublished - Dec 1 2000
Externally publishedYes
EventProceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2001) - Boston, MA, United States
Duration: Aug 20 2000Aug 23 2000

Publication series

NameProceeding of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

OtherProceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2001)
CountryUnited States
CityBoston, MA
Period8/20/008/23/00

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'FreeSpan: Frequent pattern-projected sequential pattern mining'. Together they form a unique fingerprint.

Cite this