Résumé généraliste de flux de données
Institution:
Paris, ENSTDisciplines:
Directors:
Abstract EN:
This thesis deals with the creation and management of general purpose summaries build from data streams. It is centered on the development of two algorithms, one designed to produce general purpose summaries for a single data stream, and the other for three data stream sharing relational information. A data stream is defined as a real-time, continuous, ordered 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. Such data streams appear in many applications, such as utility networks, IT or in monitoring tasks for instance in meteorology, geology or even finance. The first step in this work is to define the meaning of a general purpose data stream summary. The first property of such a summary is that it should be suitable for a variety of data mining and querying tasks. The second one is that it should be possible to build from the main summary a summary concerning only a selected portion of the stream encountered so far. The first algorithm designed, StreamSamp, is a general purpose summary algorithm dealing with a single data stream and based around the principle of sampling. While the second algorithm, CrossStream, is is a general purpose summary algorithm dealing with three data streams sharing relational information with one another, one relation stream linking two entity streams. This algorithm is based on the use of micro clusters, inspired by the CluStream algorithm designed by Aggarwal combined with the use of Bloom Filter. Both algorithm were implemented and tested against various sets of data to assess their performance in a number of situations.
Abstract FR:
Cette thèse traite de la mise en place de résumés généralistes de flux de données. Elle est centrée autour du développement de deux algorithmes, l'un produisant des résumés généralistes d'un flux de données et l'autre de trois flux de données partageant des liens relationnels. Un flux de données est défini comme une séquence continue d'objets tels qu'il soit impossible de contrôler l'ordre d'arriver des objets ou de stocker le flux dans son intégralité. On retrouve ces flux de données dans des applications comme les télécommunications, les réseau de capteurs ou l'analyse financière. La première étape de ce travail a été de définir ce qu'est un résumé généraliste de flux de données. Sa première propriété est qu'il doit être utilisable pour une large gamme de tâches de fouille de données. La seconde est qu'il doit être possible de constituer à partir du résumé principal un résumé ne concernant qu'une portion du flux arrivé jusqu'alors. Le premier algorithme réalisé, StreamSamp, est un algorithme de résumé généraliste d'un seul flux de données et il est basé sur des techniques d'échantillonnage. Le second, CrossStream est destiné à résumer trois flux de données partageant des informations relationnelles entre eux, un flux de relation liant deux flux d'entités. Cet algorithme est basé sur des micro classes inspirées de l'algorithme CluStream d'Aggarwal combinés à l'utilisation de Filtres de Bloom. Les deux algorithmes ont été implémentés et testé sur plusieurs jeux de données pour déterminer leur performances face à divers situations.