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:
- Ogni vettore caratteristico è rappresentato da un punto nella spazio 2D;
- 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);
- Il bounding-box viene diviso in regioni contenenti caratteristiche (feature) simili;
- 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;
- 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:
- L’albero ottenuto da un MB+ dipende dall’ordinamento delle regioni (e non dalle chiavi);
- 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:
- 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.
- 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.
- 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.
