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.

Pubblicato in Sistemi Informativi Taggato con: , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*