Soutenance mémoire
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.
Résumé généraliste de flux de données
Quand le volume de données augmente, il devient très coûteux (voire impossible) de les stocker avant leur traitement : il est donc nécessaire de développer des traitements à la volée ou de mettre au point le stockage d’un seul résumé intelligent de celles-ci. Nous considérons un résumé intelligent tout résumé généraliste permettant de répondre a posteriori et approximativement à n’importe quelle requête portant sur le flux, de façon optimale compte tenu des contraintes de ressources. Notre première contribution consiste à analyser ou étudier les requêtes sur certains résumés généralistes (StreamSamp et CluStream) et à proposer des extensions de ces résumés.
Interrogation des résumé de flux de données
La gestion des résumés de flux de données pose deux problématiques fondamentales. La première concerne la construction et la conservation des résumés. Tandis que la seconde problématique implique leur interrogation. En effet, les systèmes actuels permettent d’évaluer des requêtes qui portent sur les données de la mémoire du SGFD. Cependant, ils sont incapables de traiter les données expirées. Afin d’évaluer des requêtes à posteriori, nous proposons dans ce manuscrit des mécanismes permettant l’intégration des résumés généralistes à l’architecture actuelle des SGFD.
Les flux de données
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. La présentation des différentes caractéristiques et systèmes de flux de données constitue le corps de ce chapitre, suivie d’une illustration des principaux domaines d’utilisation des flux.
Concepts de base des flux de données
Définition
Une définition d’un flux de données est présentée par Golab et Özsu dans [90] : « A data stream is a real-time, continuous, ordered (implicitly by arrival time or explicitly by timestamp) sequence of items. It is impossible to control the order in which items arrive, nor is it feasible to locally store a stream in its entirety. Likewise, queries over streams run continuously over a period of time and incrementally return new results as new data arrive. These are known as long-running, continuous, standing, and persistent queries. » Une deuxième définition est aussi proposée dans [60] : « Un flux de données est une séquence de données structurées que l’on peut considérer comme infinie d’éléments générés de façon continue à un rythme rapide et parfois variable. « Rapide » signifie que la vitesse d’arrivée des nouveaux éléments est grande devant les capacités de traitement et de stockage disponibles ». Plusieurs définitions peuvent être proposées, néanmoins, toutes s’accordent sur les principales caractéristiques de ces évènements. Nous distinguons dans ce qui suit la notion d’évènement qui représente un élément du flux et la notion de données qui est la description contenue dans les évènements.
– Continues : les évènements arrivent d’une manière continue et séquentielle.
– Rapides : les évènements sont produits à un rythme rapide par rapport aux capacités de traitement du système qui les reçoit (e.g. ‘ 100K messages par seconde dans le marché des transactions par Internet [39]) ;
– Ordonnés : l’ordre des évènements est généralement défini par rapport au temps soit implicitement par temps d’arrivée ou explicitement par une estampille temporelle de production à la source (timestamp). En fonction de la représentation du temps dans le flux, cette estampille est soit physique (e.g. une date), soit logique (e.g. un nombre incrémental associé aux évènements).
– Volume illimité : le nombre d’évènements dans un flux de données est potentiellement infini (e.g. communications téléphoniques de l’AT&T : 1Go / heure [39]). La mémorisation de la totalité des données est non-envisageable. Cependant, des techniques d’archivage peuvent être déployées en parallèle du traitement classique du flux (cf. chapitre 2).
– A caractère push : les évènements se présentent d’eux-mêmes. Les sources sont programmées afin d’envoyer régulièrement leurs mesures. Le système recevant le flux n’a aucun contrôle sur ces sources.
– Sources incontrôlables : aucun contrôle n’est possible sur le débit des sources de données. Le débit peut varier de quelques kilo octets par seconde (e.g. évènements provenant des capteurs) à des giga octets par seconde (e.g. évènements circulant sur un canal OC-768 pour la transmission des données par fibres optiques). Les évènements n’arrivent pas à un rythme constant. Le débit avec lequel ils arrivent contribue dans le choix du système de gestion de flux de donnés utilisé.
– Incertitude : les évènements qui arrivent au système sont fiables. Cependant, l’imprécision porte sur la sémantique du flux (e.g. l’ordonnancement et la complétude des évènements). Il peut en effet manquer quelques évènements, avoir des duplications, etc. Ces perturbations peuvent être liées à une déficience de la source, à des problèmes de transmission ou à des problèmes de réseau, etc .
|
Table des matières
Introduction générale
1 Résumé généraliste de flux de données
2 Interrogation des résumé de flux de données
3 Plan du manuscrit
1 Les flux de données
1.1 Introduction
1.2 Concepts de base des flux de données
1.2.1 Définition
1.2.2 Structure et types de données
1.2.2.1 Flux de données structurées
1.2.2.2 Flux de données semi-structurées
1.2.2.3 Flux de données non-structurées
1.2.2.4 Types de données dans un flux
1.3 Modèles de données
1.3.1 Modèle des séries temporelles
1.3.2 Modèle de la caisse enregistreuse
1.3.3 Modèle probabiliste
1.3.4 Modélisation temporelle des flux de données
1.4 Modèle de communication
1.5 Flux de données distribués
1.6 Tâches de fouille sur flux de données
1.6.1 Détection d’anomalie dans un flux de données
1.6.2 Recherche d’évènements fréquents dans un flux
1.6.3 Classification non supervisée d’un flux de données
1.6.4 Classification supervisée d’un flux de données
1.7 Systèmes de gestion de flux de données
1.7.1 Applications de bases de données Vs. applications de flux de données
1.7.2 Caractéristiques attendues d’un SGFD
1.7.2.1 Exigences sur les fonctionnalités des systèmes
1.7.2.2 Exigences sur la performance des systèmes
1.7.3 Gestion du temps et fenêtrage
1.7.4 SGFD Vs. Systèmes de gestion d’événements complexes (SGEC)
1.7.4.1 Systèmes traditionnels de gestion de flux de données
1.7.4.2 Systèmes de gestion d’événements complexes
1.8 Domaines d’application
1.8.1 Télécommunications
1.8.2 Analyses financières
1.8.3 Réseaux de capteurs
1.8.4 Télésurveillance médicale
1.9 Synthèse
2 Résumé de flux de données
2.1 Introduction
2.2 Définition d’un résumé de flux de données
2.3 Conception d’un résumé de flux de données
2.3.1 Conception simple d’un résumé de flux de données
2.3.1.1 Échantillonnage
2.3.1.2 Histogrammes
2.3.1.3 Sketchs
2.3.2 Conception complexe d’un résumé de flux de données
2.3.2.1 Organisation temporelle complexe
2.3.2.2 Algorithmes de résumés généralistes
2.4 Synthèse
3 Traitement des requêtes continues
3.1 Introduction
3.2 Traitement de requêtes continues dans les SGBD
3.2.1 Requêtes continues dans Tapestry
3.2.2 Requêtes continues dans OpenCQ
3.2.3 Requêtes continues dans NiagaraCQ
3.2.4 Requêtes continues dans Oracle
3.3 Traitement de requêtes continues dans les SGFD
3.3.1 File d’attente et stratégie de planification
3.3.2 Requêtes continues sur fenêtres glissantes
3.3.3 Expiration des données
3.3.4 Traitement des requêtes continues dans Esper
3.3.5 Notion de requêtes hybrides continues sur flux de données
3.3.5.1 Définition d’une requête hybride
3.3.5.2 Évaluation des requêtes hybrides
3.4 Synthèse et positionnement
4 Etude des résumés de flux : cas de StreamSamp et CluStream
4.1 Introduction
4.2 Résumé de StreamSamp
4.2.1 Structure du résumé
4.2.1.1 Pondération
4.2.1.2 Effet des paramètres
4.2.2 Persistance des résumés
4.2.3 Tâches d’analyse
4.2.3.1 Constitution de l’échantillon final
4.2.3.2 Tâches de requête
4.2.3.3 Tâches de fouille
4.2.4 Limites de StreamSamp
4.2.5 StreamSamp+
4.2.5.1 Structure de données
4.2.5.2 Réponse aux requêtes
Conclusion générale
Télécharger le rapport complet
