26
Indexation de données SS tree Demba SYLLA Rachid TALBI

SS tree (par SYLLA Demba et TALBI Rachid)

  • Upload
    rchbeir

  • View
    169

  • Download
    2

Embed Size (px)

Citation preview

Page 1: SS tree (par SYLLA Demba et TALBI Rachid)

Indexation de données SS tree

• Demba SYLLA

• Rachid TALBI

Page 2: SS tree (par SYLLA Demba et TALBI Rachid)

Indexation multidimensionnelle des données multimédia

Contexte

1

Page 3: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 4: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 5: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 6: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 7: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 8: SS tree (par SYLLA Demba et TALBI Rachid)

• 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

Page 9: SS tree (par SYLLA Demba et TALBI Rachid)

• 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

Page 10: SS tree (par SYLLA Demba et TALBI Rachid)

• 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

Page 11: SS tree (par SYLLA Demba et TALBI Rachid)

• 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

Page 12: SS tree (par SYLLA Demba et TALBI Rachid)

• 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

Page 13: SS tree (par SYLLA Demba et TALBI Rachid)

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

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

Approches de recherche par similarité

q

V1

V2

V3

V4

V5

12

Page 14: SS tree (par SYLLA Demba et TALBI Rachid)

• Recherche des K plus proches voisins :

Approche de recherche par similarité

q

V3

V1

V2

V4

V5

K=2

13

Page 15: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 16: SS tree (par SYLLA Demba et TALBI Rachid)

Le SS-tree

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

Représentation multidimensionnelle

15

Page 17: SS tree (par SYLLA Demba et TALBI Rachid)

Le SS-tree

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

16

Page 18: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 19: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 20: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 21: SS tree (par SYLLA Demba et TALBI Rachid)

SR-tree

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

20

Page 22: SS tree (par SYLLA Demba et TALBI Rachid)

SR-tree

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

21

Page 23: SS tree (par SYLLA Demba et TALBI Rachid)

SR-tree

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

22

Page 24: SS tree (par SYLLA Demba et TALBI Rachid)

SR-tree

Sur mémoire

23

Page 25: SS tree (par SYLLA Demba et TALBI Rachid)

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

Page 26: SS tree (par SYLLA Demba et TALBI Rachid)

Questions ??