PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Trasarti R., Bonchi F., Goethals B. A new technique for sequential pattern mining under regular expressions. In: SEBD 2009 - 17th Italian Symposium on Advanced Database Systems (Camogli, Genova, italy, 21-24 June 2009). Atti, Seneca Edizioni, 2009.
 
 
Abstract
(English)
In this paper we study the problem of mining frequent sequences satisfying a given regular expression. Previous approaches 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 expression. We introduce Sequence Mining Automata (SMA), a specialized kind of Petri Net that while reading input sequences, it produces for each sequence all and only the patterns 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).
Subject Sequence mining
H.2.8 Database Management


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional