Sequence mining automata: a new technique for mining frequent sequences under regular expressions

In this paper we study the problem of mining frequent se- quences satisfying a given regular expression. Previous ap- proaches to solve this problem were focusing on its search space, pushing (in some way) the given regular expression to prune unpromising candidate patterns. On the contrary, we focus completely on the given input data and regular ex- pression. We introduce SequenceMining Automata (SMA), a specialized kind of Petri Net that while reading input se- quences, it produces for each sequence all and only the pat- terns contained in the sequence and that satisfy the given regular expression. Based on this automaton, we develop a family of algorithms. Our thorough experimentation on different datasets and application domains confirms that in many cases our methods outperform the current state of the art of frequent sequence mining algorithms using regular expressions (in some cases of orders of magnitude).