SS tree (par SYLLA Demba et TALBI Rachid)

Indexation de données SS tree

• Demba SYLLA

• Rachid TALBI

Indexation multidimensionnelle des données multimédia

Contexte

1

Multimédia

• Arrivée des CD_ROM (1980) apparition du mot multimédia

• Il désignait les applications qui pouvait utiliser ou piloter différents médias simultanément.

• Recherche informatique : mutlimédia l’étude des média non textuels

Images , Vidéos, Son

Introduction

2

Base de données multimédia (MMDB)

• Initialement traitées comme des BD standards:

– Objet multimédia ↔ un seul item : champ d’une BDDR

– Recherche sur mots clés.

– Utilisation des relation entre objet.

– Recherche sur les mots dans les pages web (http://images.google.com)

Introduction

3

Spécificités des MMDB

Introduction

Informations

• L’information portée par le multimédia est tout ce qui peut venir du monde réel, alors que l’information portée par une base de données classique ne peut être qu’une représentation symbolique de faits limités a l’univers de la base de données.

•Le développeur d’une MMDB ne peut expliciter tous les aspects des données qui seront importants pour l’utilisateur.

4

Spécificités des MMDB

Introduction

• Ex de requête impossible avec un SGDB “classique”:

récupérer toutes les images “qui ressemblent” à une image requête ??

•Besoin de recherche d’information sur le contenu des objets, non pas sur leurs attributs. (recherche approximative/par contenu )

5

Spécificités des MMDB

Introduction

• Ex de requête impossible avec un SGDB “classique”:

récupérer toutes les images “qui ressemblent” à une image requête ??

•Besoin de recherche d’information sur le contenu des objets, non pas sur leurs attributs. (recherche approximative/par contenu )

6

• Décrire les images par leurs contenu à l’aide des descripteurs relatifs aux indices visuels (couleurs, forme, texture,…).

Indexation

Image BD DescripteursIndices visuels

Couleur

Forme

Texture

Vecteur caractéristique

V

7

• L’idée clé dans la recherche de média est la recherche approximative

• Utilise la notion de proximité, de similarité, de distance entre objets

Retrouver les vecteurs similaires à un vecteur de requête au sens d’une mesure de similarité (distance entre eux)

Recherche approximative /par similarité

8

• Avoir un outil quantitatif pour répondre à la question:

Est-ce que deux entités X et Y se ressemblent ?

• comparer des entités obtenir un scalaire indiquant la proximité de ces entités

Distance et mesure de similarité

9

• Une distance d sur un ensemble E de vecteurs est une application dans R+ vérifiant les axiomes suivantes:

Séparation : d(x,y)=0 ↔ x=y

Symétrie: d(x,y)=d(y,x)

Inégalité triangulaire : d(x,z)<= d(x,y)+d(y,z)

Distance

10

• La similarité est basée sur la notion de distance entre deux points x, y:

Distance euclidienne:

Distance X2: pour comparer deux distributions

Distance

d(x,y) =

11

• Recherche à Ɛ près: (par intervalle)

Q (q,ε )= { v∈ BD/ sim(q,v) < ε }

Approches de recherche par similarité

q

V1

V2

V3

V4

V5

12

• Recherche des K plus proches voisins :

Approche de recherche par similarité

q

V3

V1

V2

V4

V5

K=2

13

Le SS-tree

• Arbre de recherche par similarité basé sur des sphères qui englobes les objets

Le centre de la sphère est le centre de gravité des points

14

Le SS-tree

Utilisation de sphèresCentre d’une sphère= centre De gravité des points englobés

Représentation multidimensionnelle

15

Le SS-tree

représentation de l'arbre utilisé dans la mémoireou sur le disque

16

Le SS-tree

• Maintien le nombre des points dans les sous arbres

• La sphère représentée par son centre et le rayon

Avantages:

Moins d’espace que le rectangle (R*-tree)

Fanout plus élevé en raison du fait que l’espace de stockage requis est plus petit

17

Le SS-tree

Avantages:

Moins d’espace que le rectangle (R*-tree)

Fanout plus élevé en raison du fait que l’espace de stockage requis est plus petit

Inconvénients:

SS-tree comporte plus de volume que le R-tree, ce qui augmente la quantité de chevauchement

18

SR-tree

Idéalement, un noeud d'index devrait combiner l’espace de stockage petit du SS-tree avec le volume petit du R *-tree, d’où le SR-tree

19

SR-tree

• Utilise les sphères de délimitation du SS-tree et les rectangles englobant du R-tree

20

SR-tree

• Le nœud d’index est l’intersection de ces deux

21

SR-tree

• Le nœud d’index est l’intersection de ces deux

22

SR-tree

Sur mémoire

23

SR-tree

• Structures:

Nœud d'index maintient explicitement à la fois

o sphère délimitant

o rectangle englobant

Center est barycentre pondéré de nœuds enfants

Le rayon est le minimum des distances maximales de

o Sphères englobant des nœuds enfants

o Rectangles de délimitation de nœuds enfants

24

Questions ??