Pre xSpan: Mining Sequential Patterns by Pre x-Projected Pattern

Sequential pattern mining discovers frequent subsequences as patterns in a sequence database. Most ofthe previously developed sequential pattern mining methods, such as GSP, explore a candidategeneration-and-test approach [1] to reduce the number of candidates to be examined. However, thisapproach may not be efficient in mining large sequence databases having numerous patterns and/or longpatterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficientmining of sequential patterns. In this approach, a sequence database is recursively projected into a set ofsmaller projected databases, and sequential patterns are grown in each projected database by exploringonly locally frequent fragments. Based on an initial study of the pattern growth-based sequential patternmining, FreeSpan, we propose a more efficient method, called PSP, which offers ordered growth andreduced projected databases technique is developed in PrefixSpan.