LIX Ecole PolytechniqueGeometrica INRIA Sophia

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
Luca Castelli Aleardi LIX Ecole PolytechniqueGeometrica - INRIA Sophia Soutenance de these, 12 decembre 2006, LIX Representations compactes de structures de donnees geometriques

  • disque dur

  • structures de donnees geometriques

  • representations compactes de structures

  • statue du david

  • donnees structurees de nature geometrique

  • explosion de la taille des donnees

  • modelisation geometrique


Publié le : vendredi 1 décembre 2006
Lecture(s) : 63
Source : lix.polytechnique.fr
Nombre de pages : 66
Voir plus Voir moins

Repr´esentations compactes de structures
de donn´ees g´eom´etriques
Soutenance de th`ese, 12 d´ecembre 2006, LIX
Luca Castelli Aleardi
´Geometrica - INRIA Sophia LIX Ecole PolytechniqueLe domaine de rechercheDonn´ees structur´ees de nature g´eom´etrique
Triangulations et graphes maillages surfaciques maillages volumiques
Domaines d’application
Mod´elisation g´eom´etriqueRecontruction
de surfaces GIS TechnologyMasses de donn´ees
L’explosiondelatailledesdonn´eesposedespbsdetraitement
Statue de St. Matthieu (Stanford’s Digital
Michelangelo Project, 2000)
186 million de sommets
6 Giga octets (stockage sur disque)
dizaines de minutes (temps pour la lecture
de disque dur)
Statue du David (Stanford’s Digital
Michelangelo Project, 2000)
2 milliards de polygons
32 Giga octets (sans compression)
Pas d’algorithme et structure de
donn´ees pouvant traiter le mod`ele
tout entierTh`emes de recherche
Compression de maillages
Structures de donn´ees g´eom´etriques
Transmission sur r´eseau
Stockage
Repr´esentations compactes d’objets g´eom´etriques
i
...Repr´esentations compactesUn exemple: arbres binaires et ordonn´es
arbre ordonn´e `a n arˆetes
mot de parenth`eses ´equilibibrr´´ee
1110100010110100
⇒ 2n bits pour coder un arbre avec n arˆetes.
´Enum´eration des arbres plans avec n arˆetes.

32n1 2n −
2kB k = ≈ 2 nn n+1 nUn exemple: arbres binaires et ordonn´es
arbre ordonn´e `a n arˆetes
mot de parenth`eses ´equilibibrr´´ee
1110100010110100
⇒ 2n bits pour coder un arbre avec n arˆetes.
Ce codage est ”asymptotiquement optimal”.
• le coutˆ m´emoire d’un objet correspond asymptotique-
ment `a l’entropie de la classe;
log kB k = 2n+O(lgn)2 nUn exemple: arbres binaires et ordonn´es
Le code de contour d’un arbre plan (arbre ordonn´e).
arbre ordonn´e `a n arˆetes
mot de parenth`eses ´equilibibrr´´ee
1110100010110100
⇒ 2n bits pour coder un arbre avec n arˆetes.
maisnepermetpasderepondreefficacement`adesrequˆetesd’adjacenceUn exemple: arbres binaires et ordonn´es
Repr´esentation explicite par pointeurs
lgnlgn
lgn lgnparent parent
/
lgn
parent
parent parent
/ / / /
parent parent
/ / / /
il est possible de tester en temps O(1) l’adjacence entre sommets
ce codage n’est pas optimal: il faut Θ(nlgn) bits

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.