Formation doctorale Informatique
Proposition de sujet mémoire de DEA
Sujet : Etiquetage compact pour le plus petit ancêtre commun
Responsable : Cyril Gavoille
Téléphone : 05.40.00.88.12
e-mail : gavoille@labri.fr
Site Web : http://dept-info.labri.fr/~gavoille
Equipe : Combinatoire et Algorithmique: Graphes & Applications
Présentation du sujet :
On considère le problème suivant : trouver un couple d'algorithmes (L,f)
tels que, pour tout arbre enraciné T à n sommets, on ait :
- L(T,x) est une étiquette binaire de O(logn) bits unique pour
chaque sommet x de T ;
- f(L(T,x),L(T,y))=L(T,nca(x,y)) pour toute paire {x,y}, où
nca(x,y) est le plus petit ancêtre commun de x et de y dans T.
Dit autrement, on souhaite étiquetter les sommets d'un arbre de sorte
qu'étant données deux étiquettes on puisse calculer l'étiquette du plus
petit ancêtre commun des deux sommets correspondant.
Ce problème intervient dans plusieurs problèmes de stockage des
fichiers XML du Web (ayant la structure d'arbre) et représentant de
gigantesques banques de données. Un paramètre crucial pour le stockage de la
banques de données étant la longueur des étiquettes, les étiquettes devant
doit être stockées.
Dans l'article [AGKR02] ci-dessous, il a été donné une construction pour
un tel couple (L,f). Cependant, la taille exacte des étiquettes
n'a pas été explicitement calculée. Stocker une étiquette sur 2logn bits au
lieu de 8logn bits par exemple, permettrait des gains en espace mémoire qui
se mesure en téra-octets.
L'objectif de ce stage est donc l'analyse et l'amélioration de la solution
proposée dans [AGKR02]. L'une des questions qui pourra ensuite être abordée
est de savoir quelle est la complexité exacte de la longueur minimum de telles
étiquettes. En particulier, est-il possible d'obtenir des étiquettes de
taille (1+o(1))logn bits ? (la meilleure borne inférieure connue sur la taille
minimum est seulement logn + cloglogn, où c est une constante > 0).
Mot-clés : algorithmes, arbres, structures de données compactes et distribuées
Références :
[AGKR02] Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe.
Nearest common ancestors: A survey and a new distributed algorithm.
In 14th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA),
pages 258-264. ACM PRESS, August 2002.
(article disponible sur la page Web:
http://dept-info.labri.fr/~gavoille/gavoille_publis.fr.html)
Commentaires :
Il est clair qu'un tel sujet peut déboucher sur un sujet de thèse sur des
problèmes connexes.