Extension et interrogation de résumés de flux de données

Ces dernières années, de nouvelles applications ont émergé pour lesquelles les données sont générées de façon continue et rapide sous forme de flux. Parmi ces applications nous citons : l’analyse financière (détection de fraude, échanges internationaux, etc.), la supervision des systèmes et des réseaux (surveillance du trafic, détection des attaques, etc.), les réseaux de capteurs (supervision du trafic routier, les compteurs relevant la consommation électrique, etc.), etc. Ces données sont produites sous forme de séquences d’évènements obtenues généralement en temps réel, de manière continue et ordonnée. Elles sont par nature imprévisibles et potentiellement infinies. Les systèmes se trouvent ainsi confrontés à des flux très importants de données pour lesquels un accès rapide et un stockage permanent de la totalité des évènements serait très coûteux, voir impossible.

De part leurs caractéristiques, l’apparition des flux de données a soulevé un certain nombre de problèmes et de contraintes liées à la technologie actuelle ainsi qu’aux méthodes de traitement, d’extraction et d’analyse des données existantes. Bien que tous les flux possèdent les mêmes spécificités de volume et de débit, ils ne sont généralement pas tous de même grandeur. Prenons l’exemple d’un flux de données généré à partir de l’ensemble des conversations et messages qui circulent entre les différents agents boursiers. Selon [6], le trafic de ces messages peut atteindre 100k messages/sec. Ou encore, dans le domaine de l’énergie des particules par exemple, les données produites par les expérimentations peuvent atteindre un débit de 800Go/s [142]. Tous ces exemples nécessitent un accès en temps réel aux données à des fins de supervision, de surveillance et de suivi. L’émergence de ce type d’applications est essentiellement due à deux causes [154] : (i) l’augmentation de l’utilisation et le déploiement des dispositifs de télédétection, et (ii) des raisons de sécurité tel que le terrorisme. C’est l’exemple du réseau mondial ECHELON qui utilise plus de 150 satellites ainsi que des récepteurs radio à large spectre permettant d’analyser les différentes communications en indiquant un ensemble de mots clés potentiellement intéressants [53].

Dans un nombre non négligeable de situations faisant intervenir des flux de données, l’utilisation d’outils classiques de gestion de données (tels que les Systèmes de Gestion de Base de Données (SGBD)) ne convient pas. On entre dans le domaine de la gestion de flux dès lors que (i) les données n’ont pas vocation à être stockées, (ii) elles nécessitent un traitement immédiat et (iii) les requêtes sont exécutées continuellement. C’est ainsi que sont apparus les Systèmes de Gestion de Flux de Données (SGFD). Ces systèmes ont pour objectif de répondre au même type de besoin qu’un système de gestion de bases de données classique mais en posant des requêtes continues sur des flux de données qui sont par nature éphémères, là où les SGBD posaient des requêtes ponctuelles sur des tables relativement statiques. Ces SGFD permettent le requêtage ainsi que les tâches de fouille sur les flux ou sur des fenêtres qui sont un sous ensemble fini du flux, afin d’extraire les informations les plus pertinentes à partir d’une gigantesque masse de données.

Il est dans la nature des données volatiles de n’être plus disponibles pour les analyses après leur expiration, ce qui suppose de poser a priori sur un flux l’ensemble des requêtes dont on pourra avoir besoin par la suite. Or, de nouveaux besoins peuvent parfois apparaitre après le passage des données. Dans ce cas, le SGFD ne pourra pas répondre aux requêtes posées car toutes les données n’appelant aucun traitement sont définitivement perdues. Une des solutions proposées dans la litterature est la conservation d’une représentation compacte du flux de données appelée résumé. De nombreuses structures de résumé ont été développées tels que les sketches, l’échantillonnage, etc. Le choix d’une méthode de résumé particulière dépend de la nature des données à traiter et de la problématique à résoudre. La majorité des algorithmes de résumé existants sont destinés à des tâches spécifiques tel que le calcul du nombre d’événements. Une telle spécificité est un défaut si le but du résumé est de permettre une certaine flexibilité dans les traitements. Il est ainsi nécessaire de mettre en place un résumé opérationnel pour tout type d’application et sur lequel une large panoplie de requêtes peut être appliquée. De plus, le résumé doit pouvoir s’adapter aux variations des flux de données et permettre une bonne estimation aux différentes requêtes. C’est dans ce cadre que s’inscrit la première contribution de cette thèse. Il s’agit de l’élaboration d’un résumé généraliste de flux de données.

C’est dans un contexte d’utilisation et d’interrogation des résumés généralistes de flux de données que s’introduit le sujet de cette thèse. Les objectifs du travail sont doubles. Le premier axe consiste à étudier des extensions des résumés généralistes. Le second consiste à développer des outils permettant l’interrogation et l’intégration de ces résumés dans les SGFD.

Avec le développement des nouvelles technologies, les applications sont de plus en plus contraintes à faire face à une masse importante de données disponibles en temps réel, de manière continue et ordonnée. Cela a entraîné l’apparition de très grandes bases de données, puis plus tard des entrepôts de données (Datawarehouse). Cependant, la masse de données est devenue si importante qu’il devient impossible de la conserver en totalité. Un nouveau modèle a ainsi fait son apparition, il s’agit des flux de données (ou flot de données, Data Stream) où les données sont en circulation avec des débits en général importants. Les flux de données constituent un champ de recherche récent et se situent au carrefour de plusieurs domaines (fouille de données, bases de données, réseaux de capteurs, statistiques, etc.).

De nouvelles caractéristiques (e.g. données séquentielles et éphémères) et de nouvelles contraintes (e.g. un seul accès possible aux données, débit variable) liées à la nature même de ces données nécessitent de reconsidérer les approches traditionnelles de stockage, de traitement, d’extraction et d’analyse de l’information ainsi que les systèmes destinés à gérer ces données. Sous toutes ces contraintes, le modèle classique de communication dans lequel les données sont d’abord collectées et stockées puis analysées doit être révisé pour permettre une collecte et un traitement « à la volée » de ces données dès leur arrivée. Une nouvelle famille de systèmes a fait son apparition : les Systèmes de Gestion de Flux de Données (SGFD) (Data Stream Management System). Les données traitées par ces systèmes sont sous forme de flux transitoires et temporairement stockés dans la mémoire centrale rendant ainsi le processus de traitement de l’information instantané.

Outre ces caractéristiques, les flux de données proviennent de plusieurs sources géographiquement distribuées pour alimenter un ou plusieurs serveurs. Ce mode de traitement fait apparaître de nouveaux défis : l’hétérogénéité des sources, le passage à grande échelle, la fiabilité, la sécurité, etc. Une partie de ce chapitre sera consacrée au caractère distribué des flux de données cependant, dans le cadre de cette thèse nous nous intéressons à un flux de données unique.