Approximations Géométriques et Combinatoires de Données Massives
Les données géométriques massives représentent un défi pour le traitement algorithmique. Non seulement le temps de traitement peut s’avérer extrêmement long, mais l’espace de stockage nécessaire pourrait bien excéder la capacité des machines. L’idée est la suivante : Soit une donnée P sur laquelle on veut résoudre un problème, et un paramètre d’approximation ε, on construit une esquisse S de P telle que S soit de taille beaucoup plus petite que P et qu’une solution exacte sur S permette de construire une (1+ε)-approximation de la solution sur P.
L’objectif est de construire une esquisse dont la taille est indépendante de celle de P, en minimisant la dépendance en le paramètre ε. Une approche classique qui a fait ses preuves est l’échantillonnage aléatoire, mais cette méthode ne respecte pas forcément la structure originale de la donnée. Des travaux sur des partitions géométriques respectant la structure ont déjà été réalisés sur des nuages de points, mais nous pouvons nous demander ce qu’il en est pour d’autres types de données. Cette thèse s’accompagnera d’une étude de fonctions de la configuration géométrique dans le but de majorer la complexité de la construction d’esquisses.
Geometric and Combinatorial Approximations of Massive Data
Geometric massive data presents a challenge for algorithmic processing. Not only due to the fact that the time spent to process it would be extremely long, but also the space needed may exceed the memory of individual machines. The idea is the following : let P be a data on which we want to solve a problem, and ε an approximation parameter, we construct a sketch S such that S has a smaller size than P, and an exact solution on S can extend to an (1+ε)-approximation of a solution on P. The goal is to construct sketches whose size is independent of the size of the original data, while minimizing the dependance on the approximation parameter ε. A classical approach which had great success is via random sampling, however, this method does not account for the global structure of the data. There are works on geometric partitions of finite sets of points, but the question of geometric partitions of other kinds of data is still open. This PhD thesis will include work on functions of the geometric configuration in order to bound the complexity of the construction of sketches.