Éditeur(s) : HAL CCSD
Résumé : Many works deal with the subsequence matching problem using automata structures. It is to decide, given two sequences $s$ and $t$, whether $s$ is a subsequence of $t$. Automata like the Directed Acyclic Subsequence Graph (DASG) or the Subsequence Automaton (SA) accept all subsequences of a set of texts. We focus on this last structure and provide some useful results upon dynamically updates of the SA. Indeed, sequences are indexed as soon as they are processed, allowing to dynamically add or to remove sequences from the set of indexed texts. Moreover, the highlight of these properties also makes it possible to update this automaton whenever a sequence of the set is modified.
https://hal.inria.fr/inria-00257567

inria-00257567
https://hal.inria.fr/inria-00257567
https://hal.inria.fr/inria-00257567/document
https://hal.inria.fr/inria-00257567/file/iSA.pdf

Éditeur(s) : HAL CCSD Cépaduès-Éditions
Résumé : International audience
Nous présentons dans cet article un nouvel algorithme permettant la construction et la mise à jour incrémentale du FIAθ : FIASCO. Notre algorithme effectue un seul passage sur les données et permet de prendre en compte les nouveaux batches, itemset par itemset et pour chaque itemset, item par item.
EGC: Extraction et Gestion des Connaissances
Nice, France

hal-00447421
https://hal.archives-ouvertes.fr/hal-00447421
https://hal.archives-ouvertes.fr/hal-00447421/document
https://hal.archives-ouvertes.fr/hal-00447421/file/2008--Lionel_Vinceslas--FIASCO_un_nouvel_algorithme_d_extraction_d_itemsets_frequents_dans_les_flots_de_donnees.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
Mining sequential patterns in data streams is a new challenging problem for the datamining community since data arrives sequentially in the form of continuous rapid and infinite streams. In this paper, we propose a new on-line algorithm, SPAMS, to deal with the sequential patterns mining problem in data streams. This algorithm uses an automaton-based structure to maintain the set of frequent sequential patterns, i.e. SPA (Sequential Pat- tern Automaton). The sequential pattern automaton can be smaller than the set of frequent sequential patterns by two or more orders of magnitude, which allows us to overcome the problem of combinatorial explosion of se- quential patterns. Current results can be output constantly on any user 's specified thresholds. In addition, taking into account the characteristics of data streams, we propose a well-suited method said to be approximate since we can provide near optimal results with a high probability. Experimental studies show the relevance of the SPA data structure and the efficiency of the SPAMS algorithm on various datasets. Our contribution opens a promis- ing gateway, by using an automaton as a data structure for mining frequent sequential patterns in data streams.
Advances in Knowledge Discovery and Management

lirmm-00435841
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00435841
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00435841/document
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00435841/file/akdmSPAMS.pdf

Éditeur(s) : HAL CCSD
Résumé : Given a set of strings, the Common Subsequence Automaton accepts all common subsequences of these strings. Such an automaton can be deduced from other automata like the Directed Acyclic Subsequence Graph or the Subsequence Automaton. In this paper, we introduce some new issues in text algorithm on the basis of Common Subsequences related problems. Firstly, we make an overview of different existing automata, focusing on their similarities and differences. Secondly, we present a new automaton, the Constrained Subsequence Automaton, which extends the Common Subsequence Automaton, by adding an integer $q$ denoted quorum.
https://hal.inria.fr/inria-00257561

inria-00257561
https://hal.inria.fr/inria-00257561
https://hal.inria.fr/inria-00257561/document
https://hal.inria.fr/inria-00257561/file/CSAq.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
L'extraction de motifs séquentiels fréquents dans les data streams est un enjeu important traité par la communauté des chercheurs en fouille de données. Plus encore que pour les bases de données, de nombreuses contraintes supplémentaires sont à considérer de par la nature intrinsèque des streams. Dans cet article, nous proposons un nouvel algorithme en une passe : SPAMS, basé sur la construction incrémentale, avec une granularité très fine par transaction, d'un automate appelé SPA, permettant l'extraction des motifs séquentiels dans les streams. L'information du stream est apprise à la volée, au fur et à mesure de l'insertion de nouvelles transactions, sans pré-traitement a priori. Les résultats expérimentaux obtenus montrent la pertinence de la structure utilisée ainsi que l'efficience de notre algorithme appliqué à différents jeux de données.
EGC'09 : Extraction et Gestion des Connaissances
Strasbourg, France

lirmm-00345563
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00345563

Éditeur(s) : HAL CCSD Cépaduès-Éditions
Résumé : International audience
Nous présentons dans cet article un nouvel automate : le FIA qui permet de traiter de façon efficace la problématique de l'extraction des itemsets fréquents dans les data streams. Le FIA est une structure de données très compacte et informative qui, par ailleurs, présente des propriétés incrémentales facilitant grandement la mise à jour avec une granularité très fine. L'algorithme développé pour la mise à jour du FIA effectue un unique passage sur les données qui sont prises en compte par batch, itemset par itemset et pour chaque itemset, item par item. Utilisé dans le cadre d'une approche prédictive, le FIA permet d'indexer les itemsets véritablement fréquents du stream en maximisant soit le rappel soit la précision.
EGC: Extraction et Gestion des Connaissances
Nice, France

hal-00447420
https://hal.archives-ouvertes.fr/hal-00447420
https://hal.archives-ouvertes.fr/hal-00447420/document
https://hal.archives-ouvertes.fr/hal-00447420/file/2008--Jean-Emile_Symphor--Le_FIA_un_nouvel_automate_permettant_l_extraction_efficace_d_itemsets_frequents_dans_les_data_streams.pdf