Indexer Module

I dati contenuti nel page repository vengono analizzati da un modulo Indexer. L’indexer costruisce tradizionalmente due strutture: il text index (o content index ) e il link index. Entrambi gli indici sono fondamentali per fornire un adeguato supporto al query engine. Dal punto di vista delle strutture dati, il text index viene generalmente realizzato come un inverted index.

Un inverted index è un insieme di inverted list, che come si può vedere dalla Fig. 3, è composta da un dizionario, un vettore ordinato alfabeticamente con le parole trovate nel Repository, ognuna delle quali punta alla Posting list (o location entry), cioè la lista dei documenti in cui è presente. Spesso, nel dizionario, ma anche nelle entry della Posting list, può essere memorizzata la frequenza con cui la parola appare rispettivamente nella collezione e nel documento: tale informazione sarà poi utile per le query. Al modulo query è assegnato il compito di rispondere alle richieste pervenute dall’utente interrogando l’indice; in generale i motori di ricerca possono eseguire query booleane (AND, OR, NOT), per proximity, per frase e wildcard.
Per le prime versioni viene in aiuto la struttura della lista invertita: le query in AND (ma lo stesso vale anche per quelle in Or e NOT) vengono risolte scandendo le posting list delle parole cercate e selezionando solo i documenti presenti in entrambe (Fig. 4).

Per quanto riguarda le query per frase e per proximity, è necessario memorizzare nella lista invertita la posizione della parola all’interno del documento, in maniera da poter controllare se i termini appaiono consecutivamente o a distanza predefinita nella stessa pagina. Le query wildcard sono risolte implementando il dizionario in strutture dati particolari, che permettono un accesso veloce a tutti i termini derivati dall’applicazione della wildcard.
Un altro indice costruito dal modulo Indexer è il Link Index, che rappresenta sinteticamente la topologia del Web Graph. Anche questo indice è particolarmente importante perchè alcuni algoritmi di ranking, tra cui Page-Rank [9] e HITS [10], determinano la rilevanza dei documenti in relazione ad una query, anche sulla base di un’analisi di connettività. Accanto al link index, alcuni motori prevedono la costruzione di utility index da parte del collection analysis module. In letteratura, però, sono stati descritti pochi esempi di utility index, perchè queste strutture sono parte integrante dei moduli di ranking, i quali sono oggetto di segreti commerciali. Un possibile impiego di un utility index è quello descritto in [11], dove un motore di ricerca offre un servizio di ricerca limitato all’interno di un dominio. In questo caso l’utility index contiene la mappa di ogni sito da cui sono state prelevate pagine per la collezione, in modo che, escludendo i domini non di interesse, la ricerca sia effettuata in un tempo inferiore.

Lascia un commento

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