prefixspan

PrefixSpan, short for Prefix-Projected Sequential Pattern mining, is an algorithm for discovering frequent sequential patterns in a database of sequences. It improves efficiency over earlier, candidate-generation heavy methods by using a prefix-projected growth approach. The algorithm identifies all subsequences that occur in at least a user-specified proportion of sequences (the support threshold) and is capable of handling long sequences and large data sets.

Its central idea is to recursively extend frequent prefixes. For a given frequent prefix P, PrefixSpan constructs a projected database consisting of, for every sequence that contains P, the suffix of that sequence that follows the end of the first occurrence of P. This projected database is then scanned to find items that can extend P to P·i while maintaining the required support. Each such extension defines a new prefix, and the process repeats recursively in a depth-first fashion until no further extension is frequent.

PrefixSpan does not generate and test all candidate sequences, which reduces the number of database scans and the size of the candidate set. The method is adaptable to various sequence domains, supports different types of items, and has several variants and improvements, including extensions for gap constraints or closed-pattern mining and parallel implementations. It has been widely used in data mining tasks such as market-basket analysis over time, web click streams, and biological sequence analysis.