CE48 - Fondements du numérique : informatique, automatique, traitement du signal

Algorithmes pour les données multidimensionnelles – ADDS

ADDS: Algorithmes pour les données multidimensionnelles

Les données massives représentent un défi particulièrement difficile : d'une part la plupart des problèmes rencontrés sont NP-difficile, et d'autre part, le temps d'exécution ou l'espace mémoire sont restreints. Pour surmonter ces défis, il faut développer une nouvelle génération d'algorithmes et de techniques.

Des solutions efficaces aux défis posés par le traitement de données massives grâce à la notion de 'sketches'

L'une des clés pour resoudre ces défis est la notion de 'sketch' : extraire un petit sous-ensemble - de taille constante - qui capture les caractéristiques étudiées de l'intégralité des données, à epsilon près. Le but est de construire des sketches dont la taille est indépendante de la taille des données d'entrée, tout en minimisant la dépendance à la dimension et au paramètre d'approximation epsilon.

Le projet peut être divisé en trois tâches :

Tâche 1 : L'étude des échantillons et des approximations de données géométriques.

Tâche 2 : L'utilisation d'échantillons pour concevoir des sketches de données géométriques.

Tâche 3 : L'utilisation des sketches pour concevoir des algorithmes d'approximation pour les problèmes d'optimisation.

Jusqu'à présent, nos travaux ont permis de résoudre ou d'améliorer un certain nombre de problèmes ouverts :

-Les travaux de Guilherme Dias da Fonseca et de ses collègues ont permis de résoudre un problème d'approximation d'un ensemble convexe.

-Les solutions aux instances de problèmes difficiles de motion planning ont remporté le premier prix de défi international CG:SHOP2021 associé à la conférence SoCG.

-En collaboration avec Imre Bárány, nous avons étudié la profondeur des points de Radon dans les espaces Euclidiens.

-La technique de poids multiplicatifs a été utilisée pour améliorer le temps d'exécution de la construction de low-crossing matchings.

L'amélioration des sketches pourrait potentiellement conduire à des percées dans de nombreux problèmes d'optimisation géométrique. Chacun de ces domaines de l'optimisation géométrique est déjà intéressant, mais comme ces algorithmes sont les outils de calculs scientifiques dans de nombreux domaines différents, l'amélioration de l'un d'entre eux implique un impact sur de nombreux domaines différents.

Les travaux réalisés dans le cadre de ce projet ont déjà été publiés dans les revues : d'apprentissage automatique (JMLR), de géométrie algorithmique (SCG, DCG), d'algorithmique (SODA, TOC) et de combinatoire (AMS : Contemporary Mathematics).

Les algorithmes ont été implémentés et mis à la disposition du public.

Si les capteurs collectant des données sont omniprésents, l'exploitation des données géométriques de plus en plus massives obtenues pose un sérieux défi à la communauté scientifique, notamment sur le plan algorithmique. Notre approche pour traiter ces données consiste à construire, pour un paramètre d'approximation eps donné, un sous ensemble S des donnees plus petit jeu de données artificiel S, à résoudre le problème sur S, et finalement à étendre la solution à une (1+epsilon)-approximation du problème original. Notre projet est divisé en trois parties nécessitant une expertise en statistique, en géométrie computationnelle, en apprentissage, en combinatoire et en algorithmique. On examine tout d'abord les propriétés géométriques des données qui sont pertinentes pour les transférer lors de la construction de S. Deuxièmement, on étudie les complexités (en temps et en mémoire) de la construction de S lorsque la dimension est grande, en se basant sur une compréhension des phénomènes géométriques et combinatoires sous-jacents. Enfin, on montre comment utiliser S pour améliorer la précision, et la rapidité des algorithmes d'optimisation.

Coordinateur du projet

Monsieur Nabil Hassan Mustafa (Chambre de Commerce et d'Industrie régionale de Paris Ile-de-France - ESIEE Paris)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LIMOS Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
LIPN - USPN LABORATOIRE D'INFORMATIQUE PARIS NORD
CREST Centre de Recherche en Economie et Stastistique - CREST
ESIEE Paris Chambre de Commerce et d'Industrie régionale de Paris Ile-de-France - ESIEE Paris

Aide de l'ANR 420 119 euros
Début et durée du projet scientifique : décembre 2019 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter