SPADE: An efficient algorithm for mining frequent sequences

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.