Overview

More and more human activities are supported by computerized systems. This generates more and more volumes of data to be considered when analysing and monitoring human activities. When the volume of data increases it becomes very expensive (sometimes impossible) to store all available data before processing them: it is necessary to process them ‘on the fly’ as streams of data. Moreover, many new applications generate directly streams of data produced by a large number of sensors (weather forecast, environmental studies, road traffic, health care, power plants, …).

In order to face this increase of available data, much research work has been done in the USA to develop methods and tools to process on the fly streams of structured data (opposed to audio and video streams which are unstructured). A good survey of these approaches can be found in the recent Springer book of C.Aggarwal “Data Streams: Models and Applications”. Two main directions have been explored: (1) Data Stream Management Systems (DSMS) which enable to query streams ‘on the fly’, (2) data stream mining methods to apply data mining methods directly to the streams without storing them. The main characteristic of these approaches is that all the processing is done ‘on the fly’ without storing the entire streams. In order to achieve this goal, a common solution is to apply queries and data mining algorithms to a small part of the stream defined as a sliding window containing most recent information.

In many applications, there is a need to keep an historical view of the streams, for instance to provide historical aggregate information from the streams or to detect anomalous behaviour of monitored systems. For these applications, applying queries and algorithms to sliding windows prevents from obtaining needed information: it is necessary to keep track of the history of the streams by building and updating summaries on the fly.

The MIDAS project is a ‘Recherche Fondamentale’ project which aims at studying, developing and demonstrating new methods for summarizing data streams. It tackles the following scientific challenges related to the construction of summaries:

• Summaries are built from infinite streams but must have a fixed or low increasing size;
• The construction of summaries must be incremental (done ‘on the fly’);
• The amount of CPU used to process each element of the streams must be compatible with the arrival rate of the elements;
• The summaries must cover the whole stream and enable to build summaries of any past part of the history of a stream.

The MIDAS project gathers both academic and industrial partners. The academic partners are already active in the field of data stream management and mining. The industrial partners are very large companies (France Telecom and Electricité de France) who have to face the increase of available data to monitor their activity: they will provide problems and data to direct research and assess new developed approaches.

The MIDAS project falls within the scope the 2nd thematic axis of the MDCO call: “Algorithms for processing massive data sets”.

The project began in January 2008 and is expected to finish in December 2010.

Synthèse

De plus en plus d’activités humaines sont supportées par des systèmes informatiques. Ceci génère de plus en plus de données à traiter pour analyser et superviser ces activités. Lorsque le volume des données croît, il devient très onéreux – voire impossible – de stocker sur disque les données disponibles avant de les analyser : il faut alors les traiter à la volée comme des flux de données. De plus, de nombreuses nouvelles applications génèrent elles-mêmes directement des flux de données produits par un grand nombre de capteurs (prévision météo, études environnementales, trafic routier, médecine, centrales de production d’énergie, …).

Afin de faire face à cette inflation des données disponibles, de nombreux travaux de recherche ont été réalisés aux USA pour développer des méthodes et des outils de traitement à la volée de flux de données structurés (par opposition aux flux de données audio ou vidéo). Une bonne synthèse de ces travaux peut être consultée dans le livre récent de C.Aggarwal “Data Streams: Models and Applications”, édité chez Springer en 2007. Deux directions principales ont été explorées : (1) le développement de Systèmes de Gestion de Flux de Données (Data Stream Management Systems en anglais) qui permettent d’adresser des requêtes à des flux, (2) le développement de méthodes de fouille de flux de données qui s’appliquent directement aux flux sans les mémoriser. La caractéristique principale de ces approches est que tous les traitements sont réalisés à la volée sans stocker sur disque le contenu des flux. La solution communément retenue pour atteindre cet objectif est d’appliquer les requêtes ou les algorithmes de fouille sur une partie des flux, définie par une fenêtre glissante contenant les informations les plus récentes.

Cependant dans beaucoup d’applications, il est nécessaire de conserver une vue historique des flux, par exemple pour restituer des informations agrégées historiques sur le contenu des flux ou encore pour détecter des comportements anormaux dans les systèmes analysés. Pour ces applications, l’utilisation de fenêtres glissantes sur les flux empêche d’obtenir l’information nécessaire : il faut donc garder trace de l’historique des flux de données en construisant et maintenant à jour, à la volée, des résumés des flux.

Le projet MIDAS est un projet de type ‘Recherche Fondamentale’ dont l’objectif est d’étudier, développer et illustrer de nouvelles approches de résumés de flux de données. Il s’attaque aux verrous suivants concernant la construction de résumés :

• Les résumés sont construits à partir de flux infinis mais doivent avoir une taille fixe ou peu croissante ;
• La construction des résumés doit être incrémentale (réalisée ‘à la volée’) ;
• Le temps CPU alloué au traitement de chaque élément du flux doit être compatible avec le taux d’arrivée de ces éléments ;
• Les résumés doivent couvrir l’ensemble de l’historique du flux, mais aussi permettre d’en extraire des résumés portant sur n’importe quelle partie de l’histoire du flux.

Le projet MIDAS réunit à la fois des partenaires académiques et industriels. Les partenaires académiques sont déjà actifs dans le domaine de la gestion et de la fouille de flux de données. Les partenaires industriels sont de très grandes entreprises (France Telecom et Electricité de France) qui doivent faire face à une forte augmentation des données disponibles pour analyser et superviser leur activité. Ces dernières fourniront au projet des problématiques et des données pour orienter les recherches et permettre l’évaluation des approches développées.

Le projet MIDAS s’inscrit dans l’axe thématique 2 de l’appel MDCO : « Algorithmes pour le traitement massif de données ».