In this paper we present SPADE, a new algorithm for fast discovery of Seque
ntial Patterns. The existing solutions to this problem make repeated databa
se scans, and use complex hash structures which have poor locality. SPADE u
tilizes combinatorial properties to decompose the original problem into sma
ller sub-problems, that can be independently solved in main-memory using ef
ficient lattice search techniques, and using simple join operations. All se
quences are discovered in only three database scans. Experiments show that
SPADE outperforms the best previous algorithm by a factor of two, and by an
order of magnitude with some pre-processed data. It also has linear scalab
ility with respect to the number of input-sequences, and a number of other
database parameters. Finally, we discuss how the results of sequence mining
can be applied in a real application domain.