Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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.

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.

Struttura del nodo di un B-Albero.


Alberi B (esempio)

Albero B: un 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: esempio di inserimento.


Alberi B (esempi di costruzione ed inserimento)

Alberi B: esempio di inserimento.

Alberi B: esempio di inserimento.


Alberi B (Ricerca)

Esempio di attraversamento dalla radice alla foglia.

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+.

Un esempio di confronto Albero B e B+.


Clustering

Tecnica per ottimizzare i tempi di ricerca nello spazio di feature n-dimensionale.

Vettori di features simili vengono raggruppati in cluster in base a misure di similarità.

Ogni cluster è rappresentato dal proprio centroide.

Il calcolo della similarità avviene tra la query ed il centroide di ogni cluster.

I cluster il cui centroide è più simile alla query vengono utilizzati per la ricerca completa sui vettori di features che contengono.

Clustering di documenti.
Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”

Clustering di documenti. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.”


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.”

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.”


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion