Albero MB+: variante MultiDimensionale degli alberi B+

L’albero B+ viene suddiviso in rettangoli bounding-box

Gli alberi MB+ rappresentano l’estensione degli alberi B+ da Monodimensionale a Multidimensionale. Questo tipo particolare di albero supporta le cosiddette “Similarty Query”, in italiano query per intervalli e per prossimità. Ad esempio in uno spazio 2D avremo che:

1. Ogni vettore caratteristico è rappresentato da un punto nella spazio 2D;
2. L’intero spazio delle caratteristiche (bounding-box) è il rettangolo identificato dallo spigolo in basso a sinistra (x-min, y-min) e dallo spigolo in alto a destra (x-max, y-max);
3. Il bounding-box viene diviso in regioni contenenti caratteristiche (feature) simili;
4. Le regioni individuate nel bounding-box vengono ordinate in base ad un determinato criterio. Ogni regione contiene i puntatori ai vettori caratteristiche (feature vector) che ricadono all’interno della regione;
5. Ogni feature vector ha un link con il dato multimediale di cui è una rappresentazione.

Le principali differenze di un MB+ rispetto ad un albero B+ sono due:

1. L’albero ottenuto da un MB+ dipende dall’ordinamento delle regioni (e non dalle chiavi);
2. Ogni regione di questa struttura dati corrisponde alla lista di vettori di caratteristiche (invece dei record dei dati).

Ricerca su MB trees MultiDimensionali

Gli alberi MB+ offrono come gli alberi B+ operazioni di ricerca efficienti, in questo caso avremo tre tipo di ricerche:

1. Point query,
   • Cercare un vettore (x,y);
   • Partendo dalla root, si cerca la regione che contiene il vettore da ricercare;
   • Infine si scorre la lista dei feature vector associata alla regione.
2. Range query,
   • Ricercare di tutti i vettori che ricadono in determinato rettangolo;
   • Partendo dalla root si cercano tutte le regioni che si sovrappongono al rettangolo cercato;
   • Per finire si scorre la lista dei feature vector associata alla regione.
3. Nearest-Neighbor query,
   • Ricercare k vettori più vicini ad un vettore dato;
   • Viene utilizzato un procedimento iterativo, basato sulla ripetizione di Range query finché non si trova un numero sufficiente di vettori candidati;
   • Infine si utilizza il calcolo della distanza euclidea tra il vettore da ricercare ed i vettori candidati.

Una variante degli alberi MB+ è rappresentata dagli alberi R.