Sequence mining is one of the fundamental data mining
tasks. In this paper we present a novel approach called
PRISM, for mining frequent sequences. PRISM utilizes a
vertical approach for enumeration and support counting,
based on the novel notion of prime block encoding, which in
turn is based on prime factorization theory. Via an extensive
evaluation on both synthetic and real datasets, we show that
PRISM outperforms popular sequence mining methods like
SPADE [10], PrefixSpan [6] and SPAM [2], by an order of
magnitude or more.