Accueil > Manifestations > Thèses et HDR > Thèses > Nicolo Rivetti

Nicolo Rivetti

Directeur de thèse

Achour Mostefaoui
Yann Busnel

Résumé

De nos jours, l’analyse de flux de données est utilisée dans beaucoup de contexte où la masse des données et/ou le débit auquel elles sont générées, excluent d’autre approches (par exemple le traitement par lots). Le modèle flux fourni des solutions aléatoires et/ou fondée sur des approximations pour calculer des fonctions d’intérêt données sur des flux (repartis) de n-uplets, en considérant le pire cas, et en essayant de minimiser l’utilisation des ressources disponibles (mémoire, processeur, réseau, etc.).
En particulier, nous nous intéressons à deux problèmes classiques du modèle flux, lesquels sont corrélés : l’estimation de fréquence et les poids lourds(repartis). Les solutions à ces problèmes ont un champ d’application très vaste, allant des bases de données jusqu’à la métrologie des réseaux.
Un champ d’application moins courant est le traitement de flux en temps-réel. Celui-ci est d’une certaine façon un champ complémentaire aux modèle flux. Le modèle de traitement de flux fournis des systèmes qui passent à l’échèle en s’appuyant sur les technologies des centre de données (type cloud computing), pour effectuer des calculs génériques sur les flux en temps réel souple. Cette dualité nous permet d’appliquer des solutions du modèle flux pour optimiser des systèmes de traitement de flux.
Dans cette thèse, nous proposons un nouvel algorithme pour la détection d’éléments surabondants dans des flux repartis, ainsi que deux extensions d’un algorithme classique pour l’estimation des fréquences des items. Nous nous intéressons également à deux problèmes associés (et leurs solutions) : construire un partitionnement équitable de l’univers des n-uplets par rapport à leur fréquences et l’estimation des valeurs de ces n-uplets. Nous appliquons ensuite ces solutions à la métrologie des réseaux et au traitement de flux. En particulier, nous utilisons ces algorithmes pour équilibrer et/ou délester la charge des opérateurs parallèles dans les systèmes de traitement de flux.

Mot Clefs :

Modèle flux, Approximation, Algorithmes à processus aléatoires, Eléments surabondants, Estimation de fréquences, Sureté de fonctionnement des réseaux, Traitement de flux en temps réel, Equilibrage de charge

Abstract :

Nowadays Stream Analysis is used in many context where the amount of data and/or the rate at which it is generated rules out other approaches (such as batch processing). The Data Streaming model provides randomized and/or approximated solutions to compute specific functions over (distributed) stream(s) of data-items in worst case scenarios, while striving for small resources usage (memory, cpu, network, etc.).
In particular, we look into two classical and related Data Streaming problems : frequency estimation and (distributed) heavy hitters. Solutions to these problems have a wide area of application, spanning from data bases to network monitoring.
A less common field of application is Stream Processing. It is a somehow complementary and more practical field providing efficient and highly scalable framework to perform soft real-time generic computation on streams relying on cloud computing solution. This duality allows us to apply Data Streaming solutions to improve some optimizations of stream processing systems.
In this thesis, we provide a novel algorithm to track heavy hitters in distributed streams and two extensions of a well-known algorithm to estimate the frequencies of data items. We also tackle two related problems and their solution : provide even partitioning of the item universe based on their frequencies and provide an estimation of the values carried by the items of the stream. We then apply these results to both network monitoring and stream processing. In particular, we leverage these solutions to design a load balancer for parallelized operators, as well as a load-shedding algorithm, for stream processing systems.

Key Words :

Data Streaming, Randomized Approximation, Heavy Hitter, Frequency Estimation, Network Dependability, Stream Processing, Load Balancing,

Composition du jury

  • Cormode GRAHAM, Full Professor, University of Warwick, Royaume-Uni, Rapporteur
  • Marteen VAN STEEN, Full Professor, University of Twente, Pays-Bas, Rapporteur
  • Clémence MAGNIEN, Directrice de Recherche, UPMC, Paris, Examinatrice
  • Roberto BALDONI, Full Professor, Sapienza University of Rome, Italie, Examinateur
  • Sofian MAABOUT, Maître de Conference (HDR), Universite de Bordeaux 1, Examinateur
  • Achour MOSTEFAOUI, Professeur, Universite de Nantes, Directeur de thèse
  • Leonardo QUERZONI, Maitre de Conference, Sapienza University of Rome, Co-directeur
  • Yann BUSNEL, Maitre de Conference, ENSAI, Rennes, Co-encadrant
  • Pieter PIETZUCH, Maitre de Conference, Imperial College, London, Royaume-Uni, Membre invité

Dernière modification : lundi 4 juillet 2016