I Grid File, struttura a griglia per memorizzare i dati

I file griglia contengono gli indici ai vari bucket con i dati

I Grid file rappresentano un metodo efficiente per la memorizzazione di indici su cui poter eseguire in maniera efficiente ricerche complesse. Per far ciò si suddivide lo spazio n-dimensionale in una griglia composta da tante celle (ipercubo). Ogni cella dei file Grid ha la stessa dimensione e contiene zero o più feature vector (vettori caratteristiche). I Grid file non contengono nessun dato, essi contengono solo i riferimenti ai vari bucket che contengono i dati veri e propri.

L’inserimento di un nuovo valore all’interno di un Grid file è molto semplice grazie all’utilizzo degli indici (ad esempio in una griglia 2D per poter inserire un dato basta specificare la riga e la colonna per identificare la cella in cui inserire il dato). In maniera simile funziona la ricerca in un file Griglia: per una point query si punterà direttamente alla cella della griglia e si scorrerà la lista di vettori puntati; per una range query è necessario trovare tutte le liste di vettori puntate dai puntatori le cui griglie vengono intersecate dal rettangolo descritto dalla query.

I Grid file sono un’ottima struttura dati che offrono buone prestazioni solo se i vettori caratteristiche sono distribuiti abbastanza uniformemente all’interno dello spazio dei valori, altrimenti alcune griglie risulteranno vuote (o quasi) e altre sovraffollate generando una lista di vettori molto lunga. Una lista di vettori molto lunga incide sia sul suo scorrimento in caso di ricerca che per il calcolo della similarità. In questi casi è consigliato l’utilizzo di griglie di diverse dimensioni e non uniformi. Nelle zone dello spazio densamente popolate si utilizzeranno griglie di piccole dimensioni mentre nelle zone scarsamente popolate si utilizzaranno griglie di dimensioni più grandi.

I Grid File, struttura a griglia per memorizzare i dati

I file Grid possono essere visti come un sorta di hashing, dove l’hash tradizionale è sostituito da una griglia contente i vari bucket.

Pubblicato in Sistemi Informativi Taggato con: , ,

Lascia un commento

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

*