Walter Balzano » 13.Strutture dati efficienti per la ricerca della similarità - parte prima

Strutture Dati efficienti per la ricerca della Similarità

• Introduzione
• Alberi B, definizioni
• Alberi B, operazioni
• Alberi B+, definizioni
• Alberi B+, operazioni
• Clustering
• Clustering a più livelli

Introduzione

Per un insieme di oggetti multimediali, la fase di indicizzazione produce un insieme di vettori di caratteristiche (feature vector).

Ciascun vettore V, a seconda della complessità dell’oggetto indicizzato, può contenere un numero grande di componenti (caratteristiche testo, audio, immagini, video, …).

La fase di Retrieving è, pertanto, fondamentalmente caratterizzata da un gran numero di confronti di caratteristiche tra la query Q e le caratteristiche degli oggetti precedentemente memorizzate.

Non è quindi pensabile che questi confronti siano eseguiti in modo “lineare”.

Le strategie proposte sono basate sulla suddivisione dello spazio multidimensionale delle caratteristiche in sottospazi.

Indicizzazione e confronto

Schema generale di indicizzazione dei dati e confronto della query.

Alberi B

Un albero B di ordine m (in cui m rappresenta il massimo numeri di figli che ogni nodo può avere) è un albero di ricerca generico con le seguenti proprietà:

• la radice ha almeno 2 sottoalberi, a meno che non sia una foglia;
• ogni nodo che non sia la radice e che non sia una foglia contiene k – 1 chiavi e k riferimenti a sottoalberi, in cui ^⌈m/2^⌉ ≤ k ≤ m;
• ogni nodo foglia contiene k – 1 chiavi , in cui ^⌈m/2^⌉ ≤ k ≤ m;
• tutte le foglie si trovano sullo stesso livello.

Secondo tali definizioni un albero B è sempre almeno pieno per metà, ha pochi livelli ed è perfettamente bilanciato.

Alberi B (struttura nodo)

Struttura del nodo di un B-Albero.

Alberi B (esempio)

Albero B: un esempio.

Alberi B (Operazioni e proprietà)

Le operazioni fondamentali per gli alberi B sono:

• creazione;
• inserimento;
• cancellazione;
• ricerca.

Principali proprietà strutturali di un albero B:

• è un albero bilanciato;
• prevedibilità per la complessità delle operazioni di ricerca e/o attraversamento dell’albero.

Alberi B (Inserimento)

Per l’inserimento di una nuova chiave K nell’albero B si hanno 3 casi:

• se la foglia F in cui deve essere piazzata K ha ancora spazio allora si piazza K;
• se la foglia F in cui deve essere piazzata K è piena allora:
  • si crea una nuova foglia G e metà delle chiavi di F vengono spostate in G;
  • una chiave di F (per es. l’ultima oppure la mediana) si sposta nel proprio padre P;
  • nel padre P si introducono i puntatori di G;
• se la radice R dell’albero è piena allora si crea una nuova radice S ed un nuovo fratello M della radice R.

Alberi B (esempio di inserimento)

Alberi B: esempio di inserimento.

Alberi B (esempi di costruzione ed inserimento)

Alberi B: esempio di inserimento.

Alberi B (Ricerca)

Esempio di attraversamento dalla radice alla foglia.

Alberi B+

Gli Alberi B+ possono essere considerati come una variante degli alberi B. In particolare, le caratteristiche salienti di un B+ Albero sono:

• in un albero B+ i riferimenti ai dati sono contenuti solo nelle foglie (invece in un albero B i riferimenti ai dati sono contenuti in un nodo qualsiasi dell’albero);
• le foglie di un albero B+ contengono anche un campo puntatore aggiuntivo che permette di “navigare” tra le foglie come una linked list.

Alberi B+ (esempio)

Un esempio di confronto Albero B e B+.

Clustering a più livelli

Cluster a livelli multipli per ridurre il numero di calcoli di similarità. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”