Costruzione indice non posizionale - BSBI, SPIMI, MapReduce, Dinamico

Costruzione di un indice non-posizionale

Passaggi di base

1) Prima facciamo un passaggio attraverso la raccolta assemblando tutte le coppie term-docID;
2) Ordiniamo quindi le coppie con il termine come chiave dominante e docID come chiave secondaria;
3) Infine, organizziamo i docID per ciascun termine in un elenco di post e calcoliamo statistiche come termini e frequenza dei documenti.

Per le piccole raccolte, tutto ciò può essere fatto in memoria. Per rendere più efficiente la costruzione dell'indice, rappresentiamo i termini come termID, dove ogni termID è un numero seriale univoco. Possiamo costruire la mappatura da termini a termIDs:

• Al volo mentre stiamo elaborando la raccolta;
• Oppure, in un approccio a due passaggi, compiliamo il vocabolario nel primo passaggio e costruiamo l'indice invertito nel secondo passaggio.

Gli algoritmi di costruzione dell'indice descritti eseguono tutti un singolo passaggio attraverso i dati. Gli algoritmi multipass invece sono preferibili in alcune applicazioni, ad esempio quando lo spazio su disco è scarso.

Osservazione: Con memoria principale insufficiente, dobbiamo usare un algoritmo di ordinamento esterno, ovvero uno che utilizza il disco. Per una velocità accettabile, il requisito centrale di tale algoritmo è che riduca al minimo il numero di ricerche casuali su disco durante l'ordinamento. Tutto questo perché andiamo a preferire le letture sequenziali su disco, che sono molto più veloci di quelle richieste.

BSBI – Blocked Sort-Based Indexing

Ecco i passaggi dell’algoritmo BSBI:

1) Segmenta l’intera raccolta in parti di dimensione uguale in modo tale che entrino in memoria. Nel specifico analizza i documenti trasformandoli in coppie termID-docID e accumula le coppie in memoria fino a quando un blocco è pieno. Un blocco ha dimensione fissa, scelta appositamente per farlo stare comodamente in memoria, proprio per consentire un rapido ordinamento in memoria. Tutto questo viene fatto dalla funzione ParseNextBlock();

2) Ordina in memoria le coppie termID-docID (di ciascuna parte). Il libro dice "Il blocco viene invertito" per riferirsi all’ordinamento delle coppie che avviene in due passaggi (BSBI-Invert(block)):

• Ordina le coppie;
• Raccoglie tutte le coppie termID-docID con lo stesso termID in un elenco di post, dove un posting è semplicemente un docID;

Il risultato, un indice invertito per il blocco che abbiamo appena letto, viene quindi scritto sul disco (WriteBlockToDisk(block, fn)).

3) Nel passaggio finale, l'algoritmo unisce simultaneamente i blocchi in un grande indice unito. Per eseguire l'unione, apriamo tutti i file di blocco contemporaneamente e manteniamo piccoli buffer di lettura per i dieci blocchi che stiamo leggendo e un buffer di scrittura per l'indice finale unito che stiamo scrivendo. In ogni iterazione, selezioniamo il termID più piccolo che non è stato ancora elaborato utilizzando una coda di priorità o una struttura di dati simile. Tutti gli elenchi di post per questo termID vengono letti e uniti e l'elenco unito viene riscritto sul disco. Complessità temporale O(T logT), che è dominata dal passaggio di parsing dei documenti e dal merge finale.

SPIMI – Single Pass in Memory Indexing

Per BSBI la nostra assunzione era che potevamo tenere il dizionario in memoria. Bisogna notare però che il dizionario cresce dinamicamente e per collezioni molto grandi potrebbe risultare problematico.