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

Implementazione di SPIMI per l'indicizzazione di grandi collezioni di testo

Per BSBI, la nostra assunzione era che potessimo tenere il dizionario in memoria. Tuttavia, è importante notare che il dizionario cresce dinamicamente e potrebbe non entrare in memoria per collezioni molto grandi. Ma perché abbiamo bisogno del dizionario? Serve per implementare la corrispondenza tra termine e termID. Quindi, nonostante le eccellenti proprietà di ridimensionamento, BSBI richiede il dizionario.

La soluzione è utilizzare SPIMI, un algoritmo che utilizza direttamente i termini senza utilizzare il termID. Inoltre, SPIMI non mantiene il dizionario in memoria, ma scrive il dizionario di ciascun blocco su disco. Questo perché non abbiamo bisogno di un dizionario che mantenga la corrispondenza tra termini e termID tra i blocchi. SPIMI può indicizzare raccolte di qualsiasi dimensione, purché sia disponibile spazio sufficiente su disco.

Ecco i passaggi dell'algoritmo SPIMI:

1. L'algoritmo analizza i documenti e li trasforma in un flusso di dati.
2. Viene creato un blocco di memoria per contenere i termini e le relative informazioni.
3. I termini vengono estratti dal flusso di dati e inseriti nel blocco di memoria.
4. Se il blocco di memoria è pieno, viene scritto su disco insieme al dizionario del blocco.
5. Il blocco di memoria viene svuotato per poter essere riutilizzato.
6. Questi passaggi vengono ripetuti fino a quando tutti i documenti sono stati analizzati.
7. Infine, i blocchi di memoria vengono uniti e ordinati per creare l'indice finale.

coppie term-docID;

2) Viene chiamata la funzione SPIMI-INVERT sul flusso di token, per ogni flusso, fino a quando l'interaraccolta non viene elaborata.

Dentro SPIMI-INVERT i token vengono elaborati uno alla volta;

Quando un termine si presenta per la prima volta, viene aggiunto al dizionario e viene creato un nuovo elenco di posting per quel termine, altrimenti viene restituito l'elenco di posting per le occorrenze successive del termine in questione. Quindi non abbiamo ancora aggiunto i docID in cui il termine appare alla posting list.

Controlla se la posting list è piena: in pratica, poiché non si sa quanto sarà grande l'elenco di posting di un termine, quando viene incontrato per la prima volta, si alloca inizialmente uno spazio per un breve elenco di pubblicazioni che viene raddoppiato ogni volta che è pieno.

Aggiunge alla posting list il docID del token. SPIMI aggiunge un posting direttamente alla posting list. Invece di raccogliere prima

tutte le coppie termID-docID e poi ordinarle (come in BSBI), ogni elenco di posting è dinamico (ovvero, la sua dimensione viene adattata man mano che cresce). Ciò ha due vantaggi: è più veloce perché non è necessario alcun ordinamento e consente di risparmiare memoria perché teniamo traccia del termine a cui appartiene un elenco di post, quindi non è necessario memorizzare i termID dei post.

Quando la memoria è esaurita, ordiniamo i termini del dizionario per facilitare il passaggio finale di fusione.

Quindi scriviamo l'indice del blocco (che consiste nel dizionario e negli elenchi delle postings) sul disco.

Ogni chiamata di SPIMI-INVERT scrive un blocco su disco, proprio come in BSBI. L'ultimo passo di SPIMI è quindi quello di unire i blocchi nell'indice invertito finale.

Oltre a costruire una nuova struttura di dizionario per ciascun blocco ed eliminare la costosa fase di ordinamento, SPIMI ha un terzo

componente importante: la compressione. Sia la postings list che i termini del dizionario possono essere memorizzati in modo compatto su disco se utilizziamo la compressione. La compressione aumenta ulteriormente l'efficienza dell'algoritmo perché siamo in grado di elaborare blocchi ancora più grandi e perché i singoli blocchi richiedono meno spazio sul disco.

Map Reduce - costruzione indice in modo distribuito

Le raccolte sono spesso così grandi che non è possibile eseguire in modo efficiente la costruzione di indici su una singola macchina. Infatti, i motori di ricerca Web utilizzano algoritmi di indicizzazione distribuiti per la costruzione di indici.

Il processo di costruzione è suddiviso su più macchine - in base al termine o in base al documento. Noi parleremo dell'indicizzazione distribuita per un indice partizionato in base al termine, in particolare descriveremo un'istanza dell'algoritmo.

1. Suddivisione: Il master suddivide il lavoro in blocchi, scegliendo la dimensione opportuna in modo da garantire che il lavoro possa essere svolto uniformemente (i blocchi non dovrebbero essere troppo grandi) ed efficientemente (il numero totale di blocchi che
2. Mapping: Il master assegna ogni blocco a un nodo di lavoro e invia il blocco di dati corrispondente a quel nodo. Ogni nodo di lavoro esegue la funzione di mappatura sui dati ricevuti e produce una serie di coppie chiave-valore.
3. Shuffling: Il master raccoglie tutte le coppie chiave-valore prodotte dai nodi di lavoro e le raggruppa in base alla chiave. Questo passaggio è necessario per preparare i dati per la fase di riduzione.
4. Riduzione: Il master assegna ogni gruppo di coppie chiave-valore a un nodo di lavoro e invia il gruppo di dati corrispondente a quel nodo. Ogni nodo di lavoro esegue la funzione di riduzione sui dati ricevuti e produce un risultato finale.
5. Combinazione: Il master combina i risultati finali prodotti dai nodi di lavoro e restituisce il risultato finale dell'algoritmo MapReduce.

dobbiamo gestire non dovrebbe essere troppo grande). 16 o 64 MB sono di buone dimensioni nell'indicizzazione distribuita. 2) Assegnamento: Il master assegna i blocchi in modo continuativo: quando una macchina termina l'elaborazione di una divisione, viene assegnata la successiva. Quindi non sono preassegnati. Se una macchina muore o rallenta troppo a causa di problemi hardware, il blocco su cui sta lavorando viene semplicemente riassegnato a un'altra macchina (parser). 3) Map: Un parser legge un documento alla volta dal blocco e crea le coppie (term, docID). Ogni parser scrive il proprio output in file intermedi locali, il file di segmenti, suddivisi in j partizioni. (es. [a-f, g-p, q-z] qui j=3). Questo lo facciamo perché desideriamo che tutti i valori di una determinata chiave vengano archiviati vicini, in modo che possano essere letti ed elaborati rapidamente. Quindi avremo R parser e R segment files. 4) Reduce: La raccolta di tutti i valori (docIDs) per una determinata

1. chiave (term) in un elenco è l'attività dell'inverter nella fase di Reduce.
2. Il master assegna ogni partizione di termini a un altro inverter (e li riassegna in caso di guasti, come prima).
3. Ogni partizione (corrispondente agli R file segmento, uno su ciascun parser) viene elaborata da un inverter (partiamo dal presupposto che i file di segmento abbiano dimensioni che una singola macchina può gestire).
4. Infine, l'elenco dei valori viene ordinato per ciascuna chiave e scritto nella posting lists.

Osservazioni:

• Parser e inverter non sono insiemi di macchine separati. Il master identifica le macchine inattive e assegna loro attività. La stessa macchina può essere un parser e un inverter nelle diverse fasi.
• Per ridurre al minimo i tempi di scrittura, ogni parser scrive i propri file di segmenti sul proprio disco locale. Nella fase di Reduce, il master comunica a un inverter le posizioni dei relativi segment-file (ad esempio del segment-file della

partizione af). Ogni file di segmento richiede solo una lettura sequenziale perché tutti i dati relativi a un particolare inverter sono stati scritti in un singolo file di segmento dal parser. Questa configurazione riduce al minimo la quantità di traffico di rete necessario durante l'indicizzazione.