Sequential pattern mining is an important data mining problem with broad applications. However, it is also a difficult problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Most of the previously developed sequential pattern mining methods, such as GSP, explore a candidate generation-and-test approach [R. Agrawal et al. (1994)] to reduce the number of candidates to be examined. However, this approach may not be efficient in mining large sequence databases having numerous patterns and/or long patterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficient mining of sequential patterns. In this approach, a sequence database is recursively projected into a set of smaller projected databases, and sequential patterns are grown in each projected database by exploring only locally frequent fragments. Based on an initial study of the pattern growth-based sequential pattern mining, FreeSpan [J. Han et al. (2000)], we propose a more efficient method, called PSP, which offers ordered growth and reduced projected databases. To further improve the performance, a pseudoprojection technique is developed in PrefixSpan. A comprehensive performance study shows that PrefixSpan, in most cases, outperforms the a priori-based algorithm GSP, FreeSpan, and SPADE [M. Zaki, (2001)] (a sequential pattern mining algorithm that adopts vertical data format), and PrefixSpan integrated with pseudoprojection is the fastest among all the tested algorithms. Furthermore, this mining methodology can be extended to mining sequential patterns with user-specified constraints. The high promise of the pattern-growth approach may lead to its further extension toward efficient mining of other kinds of frequent patterns, such as frequent substructures.

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 \t which may substantially reduce the number of combinations to be examined. However, \t 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 prefixprojection 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 -based GSP algorithm and another recently proposed method, FreeSpan, in mining large sequence databases. 1

Article FreeSpan: frequent pattern-projected sequential pattern mining Share on Authors: Jiawei Han Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6View Profile , Jian Pei Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6View Profile , Behzad Mortazavi-Asl Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6View Profile , Qiming Chen Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, California Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, CaliforniaView Profile , Umeshwar Dayal Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, California Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, CaliforniaView Profile , Mei-Chun Hsu Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, California Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, CaliforniaView Profile Authors Info & Claims KDD '00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data miningAugust 2000 Pages 355–359https://doi.org/10.1145/347090.347167Online:01 August 2000Publication History 503citation3,103DownloadsMetricsTotal Citations503Total Downloads3,103Last 12 Months105Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access