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:
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. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”
Point query
Range query
Nearest-Neighbor query
I K-d trees sono considerati una estensione degli alberi binari.
Albero K-D Tree:
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.”
Inserimento:
Ricerca:
Eliminazione:
Range query:
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.
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:
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.
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.
Query:
Insert:
Delete:
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):
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.
1. Introduzione
2. Tipologia e formati dei dati MultiMediali. Il testo
3. Tipologia e formati dei dati MultiMediali. L'audio
4. Tipologia e formati dei dati MultiMediali. Grafica e video
5. Progetto di DB Multimediali
6. Indicizzazione e recupero dei documenti di testo
7. Indicizzazione e recupero dell'audio
8. Metodi di classificazione dell'audio
9. Colori
10. Indicizzazione e recupero delle immagini
11. Esempi reali di image retrieval
12. Video
13. Strutture dati efficienti per la ricerca della similarità - pa...
14. Strutture dati efficienti per la ricerca della similarità - pa...
15. Sistemi di supporto e misure di efficacia
17. Geographical Information System - parte prima
18. Geographical Information System -parte seconda
19. Geographical Information System - parte terza