Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GraphComb
Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes
Romain CAMPIGOTTO

01 February 2013, 10h30 - 01 February 2013, 11h30
Salle/Bat : 475/PCRI-N
Contact :

Activités de recherche :

Résumé :
Lorsque l’on traite de façon classique un problème d’optimisation
sur un graphe, celui-ci est le plus souvent disponible dans sa totalité
sur la machine de traitement : il peut être modifié, mis à jour (les
sommets peuvent être marqués, les arêtes supprimées, etc.) et la
solution peut être conservée en mémoire. Cependant, de plus en plus
d’applications produisent des quantités de données qui sont trop
importantes et ne qui peuvent pas être stockées ni traitées dans ce
modèle.

Dans les travaux que nous avons menés, nous nous sommes intéressés en
particulier au problème du Vertex Cover, dans un contexte de traitement
de grands graphes. A la NP-complétude intrinsèque est ajoutée la
difficulté de manipuler les graphes avec des contraintes sévères
(principalement liées à la quantité restreinte de mémoire
disponible).
Nous avons défini un modèle de traitement regroupant certaines
propriétés de plusieurs modèles existants dans la littérature :
_streaming_, _online_, _I/O-efficient_, etc.

Nous avons dans un premier temps étudié trois algorithmes
d'approximation _memory-efficient_ (ils utilisent un espace mémoire en
_O(log n)_ bits). Nous avons analysé leurs performances en terme de
qualité de solution et de complexité, en pire cas et en moyenne.

Nous nous sommes ensuite intéressés à d'autres algorithmes qui
utilisent un espace mémoire de _n_ bits. Nous avons montré qu'il
pouvait être très mauvais (même en moyenne) dès lors que leur espace
mémoire disponible était plus petit que _n_ bits.

Par la suite, nous avons mené une étude expérimentale sur de très
gros graphes (de l'ordre de plusieurs milliards de sommets et
d'arêtes). Cette étude nous a permis de montrer qu'en pratique, les
algorithmes _memory-efficient_ étaient mieux adaptés pour traiter de
grands graphes.

Pour en savoir plus : http://www-complexnetworks.lip6.fr/~campigotto/
Séminaires
A Two-level Auction for Resource Allocation in Mul
Réseaux sans fil et mobiles
Friday 09 March 2018 - 14h30
Salle : 445 - PCRI-N
Mira Morcos .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 09 February 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Approximate Bayesian Computation and Random Forest
Thursday 08 February 2018 - 00h00
Salle : 455 - PCRI-N
Valentin Thouzeau .............................................

A concurrent lock-free algorithm for computing a f
Combinatoire
Friday 12 January 2018 - 14h30
Salle : 445 - PCRI-N
James Mitchell .............................................

Acyclic Partitioning of Large Directed Acyclic Gra
Calcul à haute performance
Tuesday 09 January 2018 - 10h30
Salle : 465 - PCRI-N
Julien Herrmann .............................................