Mining Sequential Pattern Using DF2Ls

In this paper, based on SEP and IEP proposed in our previous work, we present two novel pruning strategies, DSEP (dynamic sequence extension pruning) and DIEP (dynamic item extension pruning), which can be used in all Apriori-like sequence mining algorithms or lattice-theoretic approaches. DSEP/DIEP uses DF2Ls (Dynamic Frequent 2-Sequence Lists), which is built by previous enumerations, to prune out infrequent candidate sequences during mining process. With a little more memory overhead, proposed pruning strategies can prune invalidated search space and decrease the total cost of frequency counting effectively. For effectiveness testing reason, we optimize SPAM by using proposed pruning strategies and present the improved algorithm, SPAM+, which uses DSEP and DIEP to prune the search space of SPAM by sharing dynamic frequent 2-sequences lists. A comprehensive performance experiments study shows that SPAM+ outperforms SPAM by a factor of 10 on small datasets and better than 35% to 58% on reasonably large dataset.