Direction de recherche : Michèle SORIA

Co-encadrement : FLAJOLET Philippe

Algorithmes probabilistes pour la fouille quantitative de données et la génération aléatoire

Cette thèse examine deux types de problèmes: l'analyse de grands flux de données réelles, et le problème complémentaire de la génération de grande quantités de données aléatoires. Pour cela, elle exploite un ensemble d'outils communs que sont la combinatoire analytique (et les fonctions génératrices), l'énumeration, les probabilités, les algorithmes probabilitistes, avec en particulier la méthode Boltzmann pour la génération aléatoire.
Tout d'abord, nous étudions des algorithmes de traitement de données: ces algorithmes sont capables d'extraire des informations de grands flux de données en utilisant des ressources très limitées (notamment pour ce qui est de la mémoire et du temps de traitement par élément du flux). Une des nos contributions principales est de livrer l'analyse complète d'un algorithme optimal pour l'estimation du nombre d'éléments distincts dans un flux, un problème qui a suscité de nombreux travaux. Notre seconde contribution, un travail en commun avec des chercheurs de l'UPC à Barcelone, est d'introduire un estimateur novateur du nombre distinct d'éléments sui se base sur des statistiques sur les permutations.
La seconde partie se concentre sur la génération aléatoire de lois discrètes, et d'objets combinatoires. Nous introduisons le premier algorithme optimal pour la génération de la loi uniforme discrète, un élément central utilisé pour les simulations par ordinateur. Nous introduisons aussi, dans un travail en commun avec Olivier Bodini, une extension du modèle de Boltzmann pour permettre la génération aléatoire d'une nouvelle sorte d'objets appartenant à la combinatoire dite multiplicative, qui possède des liens étroits avec la théorie analytique des nombres. Enfin, toujours avec Olivier Bodini, nous présentons un travail en cours qui pourraient permettre d'améliorer l'aspect pratique de la méthode de Boltzmann.

Publications 2009-2012

• 2012
  • J. Lumbroso : “Algorithmes probabilistes pour la fouille quantitative de données et la génération aléatoire”, thèse, soutenance 13/12/2012, direction de recherche Soria, Michèle, co-encadrement : Flajolet, Philippe (2012)
  • Ah. Helmi, J. Lumbroso, C. Martínez, A. Viola : “Data Streams as Random Permutations: the Distinct Element Problem”, Discrete Mathematics and Theoretical Computer Science, vol. DMTCS Proceedings vol. AQ, 23^rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings, Montreal, Canada, pp. 323-338, (Discrete Mathematics and Theoretical Computer Science) (2012)
  • O. Bodini, J. Lumbroso : “Dirichlet Random Sampling for Multiplicative Combinatorial Structures”, Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2012, Kyoto, Japan, pp. 92-106, (SIAM) (2012)
• 2010
  • J. Lumbroso : “An optimal cardinality estimation algorithm based on order statistics and its full analysis”, Discrete Mathematics and Theoretical Computer Science, vol. DMTCS Proceedings vol. AM, 21^st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings, Vienna, Austria, pp. 489-504, (Discrete Mathematics and Theoretical Computer Science) (2010)
• 2009
  • O. Bodini, J. Lumbroso : “Optimal Partial Tiling of Manhattan Polyominoes”, DGCI 2009 - 15^th IAPR International Conference on Discrete Geometry for Computer Imagery, vol. 5810, Lecture Notes in Computer Science, Montreal, Canada, pp. 79-91, (Springer) (2009)