PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
Jian Pei, Jiawei Han, Behzad Mortazavi-Asl et al. · Proceedings - International Conference on Data Engineering · 2005
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
Cited by 1,791 works. doi:10.1109/icde.2001.914830
Authors
References
- Fast algorithms for mining association rules
- Mining sequential patterns
- Mining frequent patterns without candidate generation
- Mining sequential patterns: Generalizations and performance improvements
- Mining frequent patterns without candidate generation
- Discovery of Frequent Episodes in Event Sequences
- Efficient mining of partial periodic patterns in time series database
- Cyclic association rules
- FreeSpan
- SPIRIT: Sequential Pattern Mining with Regular Expression Constraints