Prise en compte de l’interaction dans la sélection statique et dynamique de structures d’optimisation

Sujets de thèse 2013

Intitulé de la thèse
Prise en compte de l’interaction dans la sélection statique et dynamique de structures d’optimisation
Publication du sujet sur le site de l’ABG : OUI
Nature du financement : Financement institutionnel, Contrat Doctoral, Financement régional, Contrats université sur projets,)
Domaine de compétences principal (pour l’ABG) : Informatique, électronique
Domaine de compétences secondaire (pour l’ABG) : Mathématiques
Spécialité de doctorat : Informatique et Applications

Lieu de travail
LIAS / ENSMA
Laboratoire d’accueil : LIAS

Présentation de l’équipe de recherche
La thèse se déroulera au sein du LIAS / ENSMA dans l’équipe Ingénierie des Données et des Modèles.

Résumé de la thèse en français
cf. la description complète

Résumé de la thèse en anglais
cf. la description complète

Description complète du sujet de thèse
L’explosion du volume des données générées, traitées et accédées nous fait entrer dans l’ère du Big Data. Sous l’impulsion de nouveaux fournisseurs de données tels que les réseaux sociaux, les capteurs, les systèmes e-commerce etc…, de nouveaux défis ont vu le jour. Le premier d’entre eux est une exigence toujours plus grande pour la performance en temps de réponse de requêtes qui attaquent des données de plus en plus volumineuses. Un second défi est, dans un contexte de crise économique, de minimiser le coût dans les déploiements payant (cloud). Enfin, la question de l’économie d’énergie se pose également.

Une sélection intelligente de structures d’optimisation peut permettre de répondre en partie à ces questions. Par exemple, la fragmentation horizontale est une technique d’optimisation qui permet à la fois d’augmenter les performances (en éliminant les partitions inutiles, on réduit les accès disques et donc le temps de réponse), de réduire le coût (couplé à une structure d’optimisation redondante telle que vue matérialisée ou index, elle en réduit la taille et donc le prix lié au stockage), et de réduire la dépense énergétique (dans un environnement distribué, les serveurs hébergeant les fragments inutiles peuvent être éteints).

La notion d’interaction existe à plusieurs niveaux. Dans notre cas, on s’intéresse d’une part à l’interaction entre les requêtes d’une charge, d’autre part à l’interaction entre des problèmes traditionnellement traités séparément (notamment le problème de placement des données).
L’interaction entre les requêtes dans la sélection des techniques d’optimisation est généralement ignorée, or sa prise en compte permet d’améliorer considérablement la pertinence des structures choisies.
Dans un environnement distribué, il existe des algorithmes performants de fragmentation ou d’allocation, mais la conjonction de deux bons algorithmes établis séparément ne donne pas nécessairement une solution finale optimale. Si l’on tient compte de l’interaction existant entre la fragmentation et l’allocation, ce problème devient alors un problème de sélection multiple.
Enfin, face à une évolution permanente des besoins, la vitesse de sélection d’une structure d’optimisation est un critère important. Les solutions proposées aux problèmes posées doivent pouvoir s’adapter à des charges évolutives.

Ce travail s’inscrit dans la mouvance de travaux précédemment initiés au laboratoire (thèse Ahcene Boukorka, thèse Amira Kerkad) et les poursuit dans des directions nouvelles, porteuses et en adéquation avec les besoins d’économie d’énergie.

Objectifs scientifiques de la thèse
Le travail se décompose de la manière suivante:
Etat de l’Art: devant la variété techniques d’optimisation existantes (index, vues matérialisées, fragmentation, ordonnancement des requêtes, gestion de buffer…) et des algorithmes de sélection, il est nécessaire d’établir un état de l’art complet qui mettra en évidence les problématiques de la thèse.

Interaction entre requêtes: Une charge de requêtes est facilement identifiable à un graphe ou un hypergraphe (suivant que l’on considère l’ordre d’exécution des opérations ou non). Pour exploiter au mieux l’interaction des requêtes, on peut étudier et adapter les algorithmes de partitionnement de graphes.

Modèles de coûts: Le gain en performance, l’économie d’énergie et l’économie financière doivent être quantifiés par des modèles de coût. Ces modèles de coûts doivent être établis de manière à pouvoir étudier ensemble les problèmes habituellement traités séparément. Une formalisation précise permet de ramener ces problèmes à des problèmes d’optimisation de programmation linéaire.

Sélection statique et dynamique: Déterminer des algorithmes de sélection de structures d’optimisation dans deux cas: charge prédéterminée et charge évolutive.

Validation expérimentale.

Compétences à l’issue de la thèse
Spécialiste dans les questions liées à l’économie d’energie dans les IT, optimisation d’algorithme de fragmentation

Mots clés (séparés par des virgules)
énergie, fragmentation, index, vues matérialisées, ordonnancement des requêtes, gestion de buffer, graphe…
Conditions restrictive de candidature (nationalité, âge, …) : NON

Modalité de dépôt des candidatures
contacter le co-encadrant. Prévoir d’envoyer par courriel CV, avec relevé de notes M1-M2, et lettre de motivation.

Date limite de candidature
30 avril 2013

Directeur de thèse
Ladjel BELLATRECHE
Adresse mail du directeur de thèse : bellatreche@ensma.fr
Téléphone Directeur de thèse : 0549498072

Co-directeur de thèse
Zoé FAGET
Adresse mail du co-directeur de thèse : zoe.faget@ensma.fr
Téléphone co-Directeur de thèse : 0549498060
Cofinancement LABEX SigmaLIM demandé : NON

Recherche

Menu principal

Haut de page