Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Walter Balzano » 14.Strutture dati efficienti per la ricerca della similarità - parte seconda


Strutture Dati efficienti per la ricerca della similarità

  • B+ tree Multidimensionali
  • B+ tree Multidimensionali, operazioni
  • Ricerca su MB Tree Multimensionali
  • K-d Tree
  • K-d Tree, operazioni
  • Grid Files
  • R Tree
  • R Tree, operazioni

B+ tree Multidimensionali (MB+ tree)

Il B+ tree Multidimensionale (MB+ tree) è una estensione del B+ Standard (da MonoDimensionale a MultiDimensionale).
L’MB+ tree supporta le “Similarty Query” (Query per intervalli e per prossimità).

Esempio in 2D: Ogni feature vector è un punto nello spazio 2D.

L’intero spazio delle feature “bounding-box” che contenente tutti i punti è il rettangolo identificato dallo spigolo in basso a sinistra (xmin, ymin) e dallo spigolo in alto a destra (xmax, ymax).
Dividiamo il bounding-box in regioni contenenti feature simili.
Ordiniamo le regioni secondo un criterio (Prima X, poi Y). Ogni regione contiene i puntatori ai feature-vector che ricadono all’interno della regione.
Ogni feature-vector ha un link con il dato multimediale di cui è una rappresentazione.

Differenze con B+ standard:

  • l’albero ottenuto dipende dall’ordinamento delle regioni (e non dalle chiavi);
  • ogni regione corrisponde alla lista di vettori di caratteristiche (anziché i record dei dati).

B+ tree Multidimensionali (MB+ tree)

B+ tree: rappresentazione grafica mediante rettangolo.
Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

B+ tree: rappresentazione grafica mediante rettangolo. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


B+ tree Multidimensionali (MB+ tree)

B+ tree: rappresentazione grafica.
Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

B+ tree: rappresentazione grafica. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


Ricerca su MB trees MultiDimensionali

Point query

  • Ricerca di un vettore dato (x,y);
  • si parte dalla root e si trova la regione che contiene il vettore da ricercare;
  • si scorre la lista di feature-vector associata alla regione.

Range query

  • ricerca di tutti i vettori che ricadono in un rettangolo;
  • partendo dalla root troviamo tutte le regioni che si sovrappongono al rettangolo di ricerca;
  • si scorre la lista di feature-vector associata alla regione K.

Nearest-Neighbor query

  • Ricerca dei k vettori più vicini ad un vettore dato;
  • Si usa un procedimento iterativo, basato sulla ripetizione di Range query finché non si trova un numero sufficiente di vettori candidati;
  • Si usa il calcolo della distanza euclidea tra il vettore da ricercare ed i vettori candidati.

K-d trees

I K-d trees sono considerati una estensione degli alberi binari.

Albero K-D Tree:

  • ogni chiave è costituita dal vettore K-dimensionale invece che da un solo valore;
  • per generare l’albero occorre regolamentare la modalità di inserimento di un nuovo elemento (sinistra oppure destra):
    • al primo livello si decide basandosi sulla prima componente del vettore;
    • al secondo livello si decide basandosi sulla seconda componente del vettore;
    • ecc …
    • esaurite le K dimensioni si ricomincia dalla prima componente del vettore.
Nodo dell’albero.

Nodo dell'albero.


K-d trees (segue)

Costruzione del K-d tree.
Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

Costruzione del K-d tree. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


K-d trees (operazioni)

Inserimento:

  • per ciascun livello vale l’ordinamento relativo alla componente corrispondente del feature vector;
  • problema: la struttura dell’albero dipende dall’ordine di inserimento dei record;
  • l’albero può diventare sbilanciato e richiedere operazioni di ri-bilanciamento.

Ricerca:

  • è simile al processo di inserimento;
  • per ogni livello la scelta dipende solo dal valore della relativa componente del vettore.

Eliminazione:

  • può risultare complicata quando occorre eliminare un nodo intermedio dell’albero;
  • si possono effettuare delle cancellazioni logiche senza modificare la struttura dell’albero.

Range query:

  • facile da implementare e comporta la riduzione del numero dei nodi da visitare.

Grid files

I Grid files costituiscono una modalità di indicizzazione e ricerca semplice, spesso impiegata in implementazioni reali.

Consistono nella suddivisione dello spazio n-dimensionale in ipercubi aventi tutti la stessa dimensione.

Ogni ipercubo contiene zero o più feature-vector.

Grid files. Esempio 2D.
Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

Grid files. Esempio 2D. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


Grid files (operazioni)

L’inserimento di un valore nella struttura è molto semplice:

Esempio: se nella griglia 2D precedente si deve inserire il vettore di feature {80, 70} allora esso dovrà essere inserito nella griglia con indice (1,1) e quindi sarà puntato dal puntatore P1,1 .

La ricerca di un valore avviene in un modo simile:

  • Esempio di point query: per trovare il vettore {40, 125} basterà puntare alla cella (0,2) della griglia e quindi scorrere la lista di vettori puntati da questo (tutti i vettori di feature che si trovano nella stessa griglia sono puntati dallo stesso puntatore).
  • Esempio di range query: è necessario trovare tutte le liste di vettori puntate dai puntatori le cui griglie vengono intersecate dal rettangolo descritto dalla query.

Grid files (considerazioni)

Se

i vettori di features sono distribuiti abbastanza uniformemente all’interno dello spazio dei valori

Allora

tale metodo da buoni risultati

Altrimenti alcune griglie risultano vuote o quasi e altre sovraffollate.

Se una griglia è sovraffollata il puntatore alla griglia individuerà una lista di vettori molto lunga il cui scorrimento e calcolo della similarità comporta perdita di tempo elevata.

Per far fronte a questo problema (nel caso di distribuzione non uniforme) invece di utilizzare griglie fisse della stessa dimensione si crea una suddivisione adattativa cercando di bilanciare il contenuto delle diverse griglie

Nelle zone dello spazio densamente popolate si utilizzano griglie di piccole dimensioni mentre nelle zone scarsamente popolate si utilizzano griglie di dimensioni più grandi.

R Tree (Rectangle)

L’ R Tree (Rectangle) è una generalizzazione dell’ MB+ Tree ed identifica una famiglia di strutture indicizzate molto utilizzate per l’organizzazione dei dati multidimensionali (per es. dati spaziali e geografici).

La struttura dati divide lo spazio in MBR (Minimum Bounding Rectangles).

Ogni nodo dell’R-tree ha un numero variabile di entry (fino ad un massimo predeterminato).

Ogni entry che non sia un nodo foglia contiene due entità: una identifica il nodo figlio, l’altra l’MBR che contiene tutte le entry del nodo figlio.

In ogni nodo non foglia viene memorizzato un puntatore che punta ad un nodo di livello più basso nell’albero e un rettangolo che copre tutti i rettangoli associati ai discendenti del nodo.

Nei nodi foglia viene memorizzata la lista dei vettori che ricadono dentro al singolo rettangolo di livello più basso.

Sono strutture dati utilizzate sia per memorizzare dati che hanno un “boundingbox” che dati di tipo puntuale.

R Tree (Esempio)

Esempio di R Tree.

Esempio di R Tree.


R Tree (Operazioni)

Query:

  • la regione da cercare viene caratterizzata dal suo MBR (minimum bounding-box);
  • a partire dalla root si attraversa l’albero cercando i rettangoli che intersecano l’MBR (possono essere più di uno ad ognuno dei livelli);
  • raggiunti i nodi foglia, si calcola l’intersezione tra l’MBR e il rettangolo collegato.

Insert:

  • si attraversa l’albero selezionando il rettangolo più piccolo che include l’oggetto da inserire o quello che richiederebbe l’allargamento minore per “coprire” il nuovo oggetto;
  • l’inserimento comporta l’ “allargamento” del nodo padre per fare in modo che il suo rettangolo includa completamente il nuovo oggetto;
  • se il nodo nell’albero è già pieno per più di metà, occorre procedere alla operazione di splitting in maniera analoga a quanto avviene sui MB+ tree;
  • lo splitting si può ripercuotere ricorsivamente verso l’alto fino a quando l’aggiunta di un nuovo rettangolo non comporta un riempimento eccessivo.

R Tree (Operazioni – segue)

Delete:

  • si utilizza un procedimento di attraversamento dell’albero simile a quello della ricerca;
  • se l’eliminazione di un oggetto comporta che un nodo dell’albero contiene troppo pochi elementi, il nodo viene eliminato e gli oggetti che conteneva vengono reinseriti nell’albero.

R Tree (Dati puntuali ed efficienza di ricerca)

Dati Puntuali
Per la ricerca, l’inserimento e l’eliminazione di dati puntuali in un R TREE gli algoritmi sono simili a quelli precedenti (dati multidimesionali) e l’unica differenza consiste nel fatto che ogni nodo foglia contiene più di un elemento puntuale di cui viene memorizzato l’MBR.
E’ possibile implementare la ricerca k nearest neighbor attraverso la stima di un rettangolo che contiene sicuramente tutti i punti da ricercare e utilizzando la ricerca su oggetti rettangolari descritta in precedenza.
L’inserimento di un punto avviene ricercando il rettangolo dell’albero che deve essere ampliato di meno per contenerlo.
In modo analogo al caso di oggetti rettangolari vengono trattati i casi di splitting (quando la lista di punti di un nodo conterrebbe troppi elementi) o di eliminazione di un nodo a seguito della eliminazione di uno o più punti.

Efficienza di ricerca
Dipende da 2 concetti (definiti per ognuno dei livelli dell’albero):

  • coverage: è l’area totale di tutti i rettangoli associati ai nodi del livello;
  • overlap: è l’area totale coperta da due o più nodi.

Un R tree è efficiente se sia la coverage che l’overlap sono minimizzati; in particolare l’overlap comporta problemi in fase di ricerca.
Inoltre è cruciale l’ordine di inserimento per ottenere un albero maggiormente bilanciato.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion