Projet ANR-13-JS02-0010 – EXSTREAM : Extensions du traitement par flux
Programme : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2) 2013
Année de financement : 2013
Coordinateur du projet : Monsieur Olivier GAUWIN (Laboratoire Bordelais de Recherche en Informatique)
Partenaires : Laboratoire Bordelais de Recherche en Informatique
Montant : 187800.0 euros
Date de début : 2014
Durée : 48 mois
Résumé : La tendance actuelle dans le domaine des données est de considérer ces données comme éphémères plutôt que stockées, et donc de les traiter à la volée, plutôt qu'à la demande. Ainsi de nombreuses applications récentes produisent des données sous la forme de flux de données continus, et de longueur arbitraire (par exemple, les messages d'information (logs), les messages de discussion, les données en provenance de capteurs, les flux financiers, les données génomiques, etc.). Cette tendance est particulièrement prononcée dans les communautés liées à l'informatique dans les nuages (cloud computing) et à la gestion de grandes masses de données (big data), qui cherchent des solutions innovantes pour faire face au nombre croissant de flux à traiter et à leur taille. Les caractéristiques des problèmes informatiques liés à la gestion des flux sont (i) la forme sérialisée des données, c'est-à-dire leur accès sous la forme d'une suite d'évènements, et (ii) la contrainte forte sur les ressources en temps et en espace (par exemple, obtenir une borne sur la consommation mémoire, et un temps constant par évènement traité).
Dans le but d'obtenir des traitements par flux efficaces, de nouveaux standards, algorithmes et langages sont recherchés, et de nouvelles questions émergent sur le plan théorique. L'objectif de ce projet de recherche et de développer de nouveaux modèles de calcul et des outils mathématiques rigoureux pour compléter l'état de l'art dans ce domaine. Les questions abordées par ce projet concernent ainsi plusieurs domaines de l'informatique, allant des bases de données à la théorie de la complexité, de la logique aux automates, de la combinatoire à l'algèbre. Elles comprennent un certain nombre de problèmes ouverts difficiles.
Plusieurs types de tâches réalisées en flux seront considérés, principalement liées à XML (requêtes XPath, transformations XSL, validation par rapport à des schémas) et à la recherche de motif. Ces tâches sont représentées formellement par des familles de problèmes paramétrées par des requêtes, contraintes, motifs, etc., et reçoivent en entrée des flux d'évènements.
Plus précisément, le programme scientifique s'organise autour de deux tâches principales. La première consiste à développer des algorithmes pour traiter les flux de manière optimale. Ceci inclut des algorithmes pour énumérer efficacement les réponses d'une requêtes posées sur un flux,
des algorithmes pour transformer des flux de données, des procédures de décision sur la réalisabilité à mémoire constante d'une requête ou d'une transformation, la synthèse de validateurs de flux à mémoire bornée, des solutions pour le problème de recherche de motif paramétré sur des flux. La seconde tâche vise à déterminer les paramètres des problèmes concernés par ce projet, permettant un traitement par flux efficace. Une étape intermédiaire est l'étude de formalismes basés sur les automates et des hiérarchies logiques qui permettront la définition formelle de classes de paramètres (par exemple des requêtes XPath). Une attention particulière sera portée à la capacité de traiter les égalités entre attributs provenant d'un domaine infini (test d'égalité sur des données). Nous comparerons ensuite les formalismses en terme d'expressivité et de concision. Enfin nous espérons caractériser de manière effective certains niveaux des hiérarchies que nous définirons.
Les questions abordées dans ce programme de recherche sont ambitieuses par plusieurs aspects. D'une part, elles peuvent être considérées comme 
des variantes de problèmes de vérification et de théorie des langages. D'autre part, elles comprennent des contraintes algorithmiques spécifiques
au traitement en flux. La combinaison de ces deux aspects produit des problèmes très complexes, qui requièrent de nouveaux modèles mathématiques pour être résolus.