UNIVERSITÀ CA' FOSCARI - VENEZIA

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Scienze dell'Informazione

Tesi di Laurea

Laureando: Riccardo Saccon

Progettazione di un Sistema di

FullText Retrieval Distribuito

Relatore: Chiar.mo prof. Salvatore Orlando

Controrelatore: Dott. Alessandro Roncato

Anno Accademico 2000-2001

A Silvia, Davide e Sara

"Una catena è tanto più forte quanto più forte è il suo anello più debole"

Anonimo

RINGRAZIAMENTI

Il mio primo ringraziamento va senza dubbio alla mia famiglia, che per tutti questi anni mi ha incoraggiato e sostenuto per raggiungere questo traguardo.

Ringrazio il prof. Salvatore Orlando per la sua disponibilità e per preziosi consigli che mi hanno aiutato a terminare questa tesi.

Ringrazio la "potenza" di Internet che mi ha dato la possibilià di reperire informazioni utili e tramite le "mail-list" di valutare i consigli altrui. Ringrazio inoltre "Keith" van Rijsbergen per tutto il materiale che mi ha inviato. Non può mancare un ricordo a W. Richard Stevens e Jon Postel, prematuramente scomparsi.

Infine ultimo, ma non per importanza, un sentito ringraziamento al mio amico Claudio e ai colleghi di lavoro.

INDICE

Introduzione 1

1 Fondamenti di IR 5

1.1 Introduzione 5

1.2 Modelli di Information Retrieval 8

1.2.1 Introduzione 9

1.2.2 Modelli Classici 11

1.2.2.1 Modello Booleano 12

1.2.2.2 Modello Vettoriale 13

1.2.2.3 Modello Probabilistico 19

1.2.3 Modelli Strutturati 22

1.2.3.1 Liste Non Sovrapposte 22

1.2.3.2 Nodi Prossimali 23

1.2.4 Modelli Browsing 25

1.2.4.1 Lineare 25

1.2.4.2 Strutturato 26

1.2.4.3 Ipertestuale 26

1.3 Valutazione del Processo Retrieval 27

1.3.1 Introduzione 28

1.3.2 Recall e Precision 28

1.3.3 Misure Alternative 32

1.4 Metodologie per l'Indicizzazione 33

1.4.1 Introduzione 33

1.4.2 Liste Invertite 34

1.4.3 Signature File 40

1.4.4 Bitmap 42

1.4.5 Concept Index 43

1.4.6 Suffix Tree 44

2 IR in Ambiente Parallelo e Distribuito 47

2.1 Introduzione 47

2.2 Computer Paralleli 48

2.3 Misura delle Prestazioni 49

2.4 Sistemi Paralleli IR 50

2.4.1 Architettura MIMD 51

2.5 Sistemi Distribuiti IR 55

2.5.1 Architettura Distribuita 55

3 Architettura del Sistema Distribuito IR 57

3.1 Introduzione 57

3.2 Flussi di N Partizioni 59

3.3 Flussi di una Partizione 62

3.4 Flussi del Broker 65

3.5 Flussi dell'Agent 66

3.6 Flussi della Query 68

3.7 Vantaggi e Svantaggi del Sistema Distribuito 70

4 Architettura del Broker 75

4.1 Introduzione 75

4.2 Disegno del Broker 76

4.2.1 Parte I: Inizializzazione come Demone 76

4.2.2 Parte II: Lettura dei Parametri 77

4.2.3 Parte III: Ricerca Topologia di Rete 79

4.2.4 Parte IV: Richieste del Client e del Broker 80

4.2.5 Parte V: Invio Dati all'Agent 82

4.3 Descrizione Strutture 83

4.3.1 Struttura Ricevuta dal Client e dal Broker 83

4.3.2 Struttura Inviata all'Agent 84

4.3.3 Strutture Dati Configurazione 84

4.4 Algoritmo del Broker 85

4.4.1 Diagramma dell'Algoritmo 88

5 Architettura dell'Agent 89

5.1 Introduzione 89

5.2 Disegno dell'Agent 90

5.2.1 Inizializzazione come Demone 90

5.2.2 Lettura dei parametri 91

5.2.3 Attesa Richiesta dal Broker 93

5.2.4 Esecuzione Query Distribuita 94

5.2.5 Aggregazione dei Dati 95

5.2.6 Invio Dati al Client o all'Agent 96

5.3 Descrizione Strutture 97

5.3.1 Struttura ricevuta dal Broker 97

5.3.2 Struttura inviata agli altri Broker 98

5.3.3 Struttura ricevuta dalla Query_Db 98

5.3.4 Struttura Ricevuta dagli altri Agent 98

5.3.5 Struttura Inviata al Client 98

5.4 Algoritmo dell'Agent 99

5.4.1 Diagramma dell'Algoritmo 103

6 Architettura del Dbase Full Text 105

6.1 Introduzione 105

6.2 Disegno del Dbase 106

6.3 Struttura dei File 107

6.4 Moduli: Builder e Retrieve 110

6.5 Algoritmo di Ranking 113

7 Risultati Sperimentali 117

7.1 Introduzione 117

7.2 Piattaforma di Test 118

7.2.1 Collezione di Test 118

7.2.2 Piattaforma Hardware 119

7.3 Test I : Query Locali al Dbase 120

7.4 Test II: Query Distribuite al Dbase 127

8 Conclusioni e Sviluppi Futuri 139

A Figure 1

B Listati 5

B.1 Descrizione Sintetica dei Moduli 6

B.2 Listati dei Moduli 9

C The GNU General Public License 241

D Abstract 253

E Lucidi 255

Bibliografia 275

INTRODUZIONE

Il problema del reperimento di informazioni corrette e precise, affonda le radici negli albori della storia quando, però, riguardava solamente pochi dotti cattedratici, che si dovevano districare tra papiri, rotoli e pergamene, mentre il popolo, affacendato in ben altre questioni, non si poteva di certo porre il problema dell'istruzione. La disponibilità di testi scritti, alquanto limitata prima dell'invenzione della stampa, complicava ulteriormente il reperimento e, di conseguenza, la fruizione delle informazioni.

Il continuo miglioramento dell'istruzione di base, almeno per quanto riguarda la società industrializzata occidentale, ha portato ad un aumento esponenziale della richiesta di informazioni; negli ultimi anni, per di più, la nascita della rete telematica nota come Internet, ha permesso a milioni di fruitori di tutto il mondo, di reperire quantità inimmaginabili di documenti, testi e informazioni riguardanti tutto lo scibile umano. Proprio questa crescita parallela, fruitori da una parte e disponibilità di documenti dall'altra, ha posto un problema di difficile soluzione: il reperimento di informazioni corrette, disperse nell'oceano, sempre più vasto, della rete telematica.

Per ovviare a questo problema, Internet propone alcuni motori di ricerca che utilizzano metodiche diverse nel reperimento delle informazioni; le ricerche, attraverso questi motori, danno spesso dei risultati frustranti, proprio a

causa della quantità enorme di informazioni circolanti. Una ricerca semplice e veloce, che porti ad un risultato ottimale, a disposizione di chiunque, consente, a nostro avviso, un passo in avanti importante da molti punti di vista: didattico, scientifico, ludico e, non ultimo, sociale.

L'avanzamento sociale è il concetto che sta alla base dei progetti Open Source e Free Software: rendere pubblico il codice sorgente di qualsiasi programma, impedisce che il mondo dell'informatica cada nelle mani di una ristretta cerchia oligarchica e monopolistica di uomini potenti. Un rischio di questo genere fu paventato da Richard Stallman, iniziatore del progetto GNU¹, che vedeva minacciato quel concetto irrinunciabile e fondamentale, su cui si basa il progresso della conoscenza scientifica: la condivisione delle informazioni. La GNU permette a chiunque di copiare e distribuire il software, a patto, però, che non si impedisca ad altri di fare lo stesso.

Condividere le informazioni, significa testare una scoperta (nel nostro caso, un nuovo programma software) e quindi, porre al riparo la società da quella strana ma assai diffusa materia scientifica, che lo storico Federico Di Trocchio [77] chiama "imbrogliotica". Risulta evidente anche a un profano, infatti, che la condivisione dei dati, impedisce lo sbandieramento di false scoperte scientifiche e, di conseguenza, l'innalzamento e la glorificazione di ricercatori interessati più alla fama che alla genuinità e validità delle proprie idee. Alla luce di tutto questo, assume un'importanza rilevante il progresso creativo legato ad una scoperta scientifica, progresso che verrebbe inevitabilmente isterilito dalla segretezza dei dati.

Concludendo questa breve introduzione, non possiamo che ribadire il senso della nostra scelta, volta a dare un contributo, anche se piccolo, allo sviluppo e alla circolazione delle idee.

STRUTTURA DELLA TESI

L'elaborato tratta, inizialmente, dei concetti fondamentali di Information Retrieval (IR), illustrandone i principali tipi di modelli (classici, strutturati e browsing), la valutazione dell'efficacia del sistema tramite i basilari parametri di stima (Recall e Precision) e le metodologie per l'indicizzazione. La parte teorica, continua illustrando le varie architetture di Information Retrieval, in Ambiente Parallelo e Distribuito.

Ultimata la parte teorica, viene illustrata l'architettura del nostro Sistema Distribuito IR, Network Search Engine (NSE), specificando i flussi delle varie fasi; quest'ultima parte, si addentrerà fino ad interessare i mattoni fondamentali del Sistema (il Broker e l'Agent).

Una particolare attenzione è rivolta alla struttura complessa del Dbase FullText e ai relativi moduli che lo implementano (Builder e Retrieve). I risultati sperimentali concludono l'elaborazione della tesi, illustrando, con tabelle e grafici, l'utilizzo del Sistema Distribuito IR e valutandone l'efficacia e l'efficienza.

Le conclusioni e gli sviluppi futuri, poste al termine della tesi, interpretando lo spirito con il quale questo lavoro è stato svolto, invitano esplicitamente altri (hobbisty, ricercatori, appassionati) a continuare su questa strada, per migliorare e ampliare i già buoni risultati ottenuti.

Capitolo 1

Fondamenti di IR

1.1 Introduzione

Per Information Retrieval (IR) si intende "classicamente" quell'insieme di tecniche che consentono un accesso mirato ed efficiente a grandi raccolte di oggetti. Attualmente la IR riguarda tecniche applicabili in modo algoritmico a computer in grado di accedere agli oggetti di una raccolta o di una collezione. Ogni oggetto è riassunto nei suoi attributi da "descrittori", che tipicamente consistono di un testo.

Un IR è implementato tramite un Sistema Information Retrieval; esso è, essenzialmente, uno strumento che "cerca" di recuperare quei documenti che corrispondono, anche se parzialmente, a quelli richiesti mediante una query; successivamente, si occupa di selezionare, tra questi, un sottoinsieme formato dai risultati che meglio corrispondono alle aspettative dell'utente che aveva formulato la query.

Vediamo ora, in dettaglio, come viene implementato il processo di retrieval e tutti i suoi sottoprocessi. L'architettura del processo retrieval, descritta di seguito, è rappresentata [16] nella Figura 1.1.

Essa è suddivisa in tre parti: indicizzazione dei documenti, ricerca dei documenti, raffinamento della ricerca.

Prima che il processo di retrieval possa iniziare, bisogna definire il "Text DataBase". Esso contiene i documenti che verranno usati, le operazioni che possono essere fatte nei documenti e il modello del testo (le strutture testo e quali elementi possono essere ricercati).

Il "Text Operations" trasforma il documento in una vista logica. Un semplice esempio di una vista logica: estrarre da un documento tutte le sue parole. La Figura 1.2 mostra le varie fasi attraverso le quali un documento diventa una vista logica.

Dopo che la vista logica del documento è stata definita, il database manager, usando il "DB Manager Module", costruisce, tramite il sottoprocesso di indicizzazione "Indexing", gli indici "Index". Gli indici sono delle strutture dati che permettono una veloce ricerca su grandi volumi di dati. Possono essere creati molti tipi di indici (in figura vediamo l'indice "Inverted Index"). Nel Capitolo 1.4, Metodologie per l'Indicizzazione, vedremo con maggior dettaglio tali tecniche.

Dopo l'indicizzazione, passiamo al reperimento dei documenti.

L'utente, tramite "User Interface", inserisce i dati, "User Need" necessari per formulare la query. Tali dati vengono trasformati dal sottoprocesso "Text Operations", in una vista logica; la vista logica, a sua volta, è passata al sottoprocesso "Query Operations" che ottimizza e riformula i dati in modo conforme con il disegno del sistema IR, operazione che assicura all'utente una visione compatibile con le sue conoscenze, senza dover conoscere la struttura interna del sistema IR.

Dopo aver creato la query, il sottoprocesso "Searching" lo processa usando gli indici "Index". La velocità del processo è resa possibile dalla struttura ad indice precedentemente costruita. Il processo di "Searching" produce una serie di documenti "Retrieved Docs", che prima di essere inviati all'utente, sono ordinati secondo una probabilità di rilevanza "Ranking". Il Ranking è la parte più importate, a nostro avviso, di un sistema IR, i cui algoritmi verranno analizzati più in dettaglio nel Capitolo 1.2, Modelli di Information Retrieval.

A questo punto la ricerca dei documenti tramite la query è terminata, ma l'utente può raffinare il reperimento di dati, usando il ciclo "User Feedback". In questo ciclo, l'utente modifica i parametri della query, tramite "User Interfaces", per ottenere dei risultati che meglio corrispondono alle sue aspettative.

1.2 Modelli di Information Retrieval

In linea teorica, il processo di retrieval (ricercare delle informazioni in una grande collezione di oggetti), è di semplice risoluzione. Con i sempre più potenti computer, sebbene le collezioni aumentino esponenzialmente, i tempi di elaborazione diminuiscono sempre più. Il problema principale è fornire un modello di ordinamento secondo una probabilità di rilevanza (Ranking). In questo capitolo illustreremo alcuni algoritmi di Ranking.

1.2.1 Introduzione

Possiamo classificare in tre classi i modelli di Information Retrieval: Booleani, Vettoriali e Probabilistici. Nel modello Booleano si utilizza la teoria degli insiemi: i documenti e le query sono rappresentati come un insieme di termini indicizzati. Nel modello Vettoriale si utilizza l'algebra: i documenti e le query sono rappresentati come vettori in uno spazio n-dimensionale. Nel modello Probabilistico si utilizza la teoria delle probabilità (principalmente il teorema di Bayes): i documenti e le query sono basati su una probabilità teorica.

Con gli anni altri modelli sono stati proposti; la Figura 1.3 ne mostra una classificazione di massima. Prima di illustrare i vari modelli di IR, diamo una definizione formale [16] di un modello generico di IR.

Definizione del Modello di IR

Un modello di Information Retrieval è una quadrupla dove:

• D è un insieme composto dalle viste logiche dei documenti della collezione;

• Q è un insieme composto dalle viste logiche della query che possono essere sottomesse dall'utente;

• F è la funzione che serve a trasformare un documento o una query nella rappresentazione logica;

• è la funzione di ranking che associa un valore numerico ai due parametri, query e documento, ed è utilizzata per ordinare i documenti in base alla loro presunta rilevanza.

1.2.2 Modelli Classici

In questa sezione vengono rappresentati i tre modelli classici di IR: Booleano, Vettoriale, Probabilistico [16][17]. I modelli classici di IR considerano che ogni documento è descritto da una serie di parole e chiavi, chiamate "index terms".

Un termine indice è semplicemente una parola che, tramite la semantica, aiuta a ricordare l'argomento del documento. È da notare che gli "index terms" di un documento non sono tutti uguali: infatti, i termini contenuti all'interno degli indici, associano un peso che in fase di recupero serve a ordinare i documenti secondo un coefficiente denominato rank. Prima di analizzare le caratteristiche di alcuni modelli classici, introduciamo una nomenclatura che useremo in seguito.

Sia t il numero di termini contenuti in un sistema e siaun generico termine indice.è l'insieme di tutti i termini indice. Con si indica il peso del termineall'interno del documento. Se un termine non appare nel documento si pone, per definizione, . Il vettore , associato al documento , rappresenta il contenuto informativo di tale documento. La funzione calcola il peso dell'index term .

Esistono altri modelli, oltre a quelli illustrati nei prossimi capitoli. Nel modello booleano "Fuzzy Set Theory", l'idea chiave è quella di associare un'insieme di funzione con gli elementi della classe. Il modello statistico, "Inference Network", generalizza il modello statistico considerando il problema dell'IR come una "inferenza" o processo basato sul regionamento. Il modello algebrico "Neuronal Network", invece di usare due vettori (query, documenti), sfrutta le reti neuronali, grafi molto complessi usati per calcolare la funzione di somiglianza.

1.2.2.1 Modello Booleano

Il modello Booleano, è un semplice modello di IR basato sulla teoria degli insiemi e dell'algebra booleana, e per la sua semplicità, è alla base della maggior parte dei servizi commerciali di retrieval. Generalmente è considerato difficile da utilizzare, in quanto le espressioni booleane hanno una precisa semantica; di norma, non è semplice inserire le informazioni necessarie per la query all'interno di un'espressione booleana. Inoltre, non classificando i documenti, il modello booleano ottiene bassi risultati di recall e precision (per questi due parametri, vedere Paragrafo 1.3).

Nel modello booleano, si considera che i termini indice siano presenti o assenti nel documento. Questo porta ad assumere che il peso dell'index term sia di tipo booleano . Vale 1 se il termine è presente, vale 0 se il termine è assente.

Se consideriamo le formule come disgiunzioni di congiunzioni di termini, (DNF, Disjunctive Normal Form), possiamo definire la seguente funzione di similarità.

Per un modello booleano, le variabili dei pesi degli index term sono binarie. Una query q, è una convenzionale espressione booleana. La è la query posta in forma normale disgiunta, e sia una qualsiasi fra le componenti congiunte di . La similarità [16] del documento è data da :

Formula 1.1 Similarità Modello Booleano

Se , allora il modello booleano indica che è rilevante rispetto alla query q (ma può anche non esserlo); altrimenti il modello indica che il documento non è rilevante.

Uno dei maggiori svantaggi del modello booleano, è di non poter fornire risposte in ordine di rilevanza. Per ovviare a ciò, esiste una semplice soluzione: oltre a considerare il peso di un index term, il quale valore può essere o zero o uno, al modello viene associato anche un altro peso, .

Il peso di tipo binario serve per determinare, con il modello booleano, se il documento è rilevante. Il secondo peso, , viene utilizzato per "classificare" in ordine di rilevanza.

1.2.2.2 Modello Vettoriale

Il modello vettoriale (Vector-Space Model), è un modello di IR basato sulla teoria algebrica [1][18] che utilizza un vettore caratteristico.

I documenti e le query sono rappresentati da due vettori di lunghezza k a valori reali, nei quali ogni elemento costituisce un peso. Possono essere utilizzate varie tecniche per determinare i pesi, ma comunemente ci si basa sulla frequenza di un termine in un singolo documento e nell'intera raccolta. Il confronto fra documenti e query, avviene utilizzando una funzione di somiglianza (ad esempio coseno dell'angolo tra i vettori).

Per un modello vettoriale, il pesoassociato ad una coppia è positivo; inoltre, anche i termini index della query hanno un peso. Assegnamo come peso associato alla coppia. Il vettore associato alla query q, è così definito:, dove t è il numero totale di termini indice del sistema. Il vettore associato a un documento . Una funzione di similarità è data da una correlazione tra i due vettori; facciamo un esempio di quest'ultimo caso:

Formula 1.2 Similarità Modello Vettoriale Forma (Forma A)

Formula 1.3 Similarità Modello Vettoriale (Forma B)

Questo valore può essere visto come il coseno dell'angolo fra i due vettori q e . Per decidere se è rilevante o meno, si fissa un valore di soglia k e in base a questo si scartano i documenti in cui

Il modello basato sui "cluster" (grappoli) [42][44], rappresenta un' interessante alternativa ai modelli che tengono conto della somiglianza fra i documenti.

Fondamento del modello è la "Cluster Hypothesis", la quale afferma che documenti simili sono conformi ad uno stesso fabbisogno informativo (un interesse specifico dell'utente). Vediamo a grandi linee come è basata questa variazione del modello vettoriale.

Invece di paragonare le rappresentazioni dei singoli documenti alla rappresentazione del fabbisogno informativo, viene effettuata una prima catalogazione dei documenti, suddividendoli in "cluster" (in base a qualche funzione di somiglianza) e per ogni cluster si crea un documento "medio" che rappresenta i documenti corrispondenti. Il precesso di retrieval, restituisce tutti quei documenti appartenenti al "cluster" che soddisfano la query; quindi, saranno considerati nella funzione di somiglianza solo i documenti rappresentativi o "medi".

É da notare come questo modello non fornisca una definizione standard della rilevanza, dipendendo quest'ultima dai "cluster" utilizzati. Infine, esistono diversi criteri per identificare i "cluster" da recuperare, specie se si ricorre a tecniche di strutturazione che permettono la navigazione nella gerarchia dei "cluster"; inoltre, a suo vantaggio, questa estensione ha una maggior giustificazione teorica rispetto al modello "vector-space model".

Fino ad ora abbiamo parlato di peso di un termine. Illustriamo ora due tecniche popolari, per calcolare il peso in un termine indice.

La prima tecnica, considerata la più classica, è la "Inverse Document Frequecy"; essa afferma che, la frequenza di un termine tende ad essere inversamente proporzionale alla sua importanza.

Questo significa che: il peso di un termine t, può essere calcolato come:

Formula 1.4 Peso di un termine t (Forma A)

La Formula 1.4, la più semplice, non è l'unica possibile; altre ne sono state proposte e vanno tutte sotto il nome di IDF (Inverse Document Frequency).

Forniamo ora la lista delle formule più usate nei modelli vettoriali e booleani pesati:

Formula 1.5 Peso di un termine t (Forma B)

Formula 1.6 Peso di un termine t (Forma C)

Formula 1.7 Peso di un termine t (Forma D)

Formula 1.8 Peso di un termine t (Forma E)

dove :

• N è il numero totale di documenti;

• è la frequenza dei documenti che contengono il termine t;

• è il massimo valore didella collezione

Si usa la funzione logaritmo nelle formule, per aumentare la gradualità del valore del peso, con il variare del numero delle parole.

Similmente, il componente , "Relative Term Frequency", (RTF), può essere calcolato in differenti modi, tutti in funzione di , frequenza del termine all'interno del documento.

Formula 1.9 Frequenza relativa di un termine t (Forma A)

Formula 1.10 Frequenza relativa di un termine t (Forma B)

Formula 1.11 Frequenza relativa di un termine t (Forma C)

Formula 1.12 Frequenza relativa di un termine t (Forma D)

Il metodo migliore per assegnare il peso al documento, è dato: ; quindi si ha chee uguale al peso assegnato al documento relativamente ad un termine t è dato da :

Formula 1.13 Peso assegnato al documento relativo al termine t

Con queste considerazioni possiamo dare la formula del "coseno", nel suo dettaglio, per il calcolo del ranking.

Formula 1.14 Regola del coseno

Formula 1.15 Regola del coseno per il ranking

Formula 1.16 Peso del Documento e della Query

in forma completa :

Formula 1.17 Similarità del Modello Vettoriale

La seconda tecnica, "Link Popularity", [16] è basata sul principio che le informazioni dei link all'interno di un documento, influenzano il peso dello stesso. Tale principio è implementato dall'algoritmo PageRank^TM.

L'algoritmo "PageRank" [45] può essere visto come un algoritmo che simula il comportamento di un generico utente che, navigando ipertestualmente, arriva in un documento e poi se ne va in un'altro, con probabilità q; oppure, segue un "link" casuale con probabilità 1-q. I link sono visti come archi orientati e non possono essere attraversati in senso inverso; i documenti, invece, sono visti come nodi di un grafo diretto.

Sia p un generico documento puntato dalle pagine e che presenta C(p) link verso altri documenti, il "PageRank", la probabilità, PR(p), di p sarà definita come:

Formuale 1.18 Probabilità PageRank

dove q è una costante positiva (alla quale viene normalmente assegnato il valore 0.15). Da notare che il ranking delle altre pagine, è normalizzato rispetto al numero di link contenuti nella pagina.

Il processo viene normalizzato tramite una catena di Markov, alla quale si associa un grafo dove i nodi sono rappresentati dalle pagine e gli archi sono link che le collegano. La probabilità stazionaria [29] associata a tale catena, viene ottenuta con un algoritmo iterattivo che calcola l'autovettore principale della matrice di adiacenza relativa alla catena di Markov.

1.2.2.3 Modello Probabilistico

Il modello probabilistico [1][20] (Probabilistic Ranking Principle), è il modello di IR basato sul calcolo della probabilità. Esso afferma che la migliore efficacia di retrieval si raggiunge quando i documenti sono classificati in ordine decrescente, in base alla probabilità di rilevanza.

Il documento e il fabbisogno informativo , vengono rappresentati da un vettore booleano a k dimensioni. Detto F l'insieme delle rappresentazioni per i fabbisogni informativi e D l'insieme delle rappresentazioni dei documenti, si definisce una spazio degli eventi . L'obiettivo è quello di determinare le coppie rilevanti, cioè stimare la probabilità

In pratica, si fanno delle supposizioni sull'indipendenza della distribuzione, dalle caratteristiche dei documenti e delle query. Successivamente si effettua una stima delle probabilità che le singole caratteristiche siano assegnate a documenti rilevanti o non rilevanti, e si utlizza il teorema di Bayes per derivare una funzione di classificazione che calcoli in termini di queste probabilità. Esistono differenti modelli probabilistici, ciascuno caratterizzato da un particolare insieme di supposizioni di indipendenza, e quindi da differenti funzioni di classificazione.

Entrando nel dettaglio, il modello probabilistico, si basa sulla seguente assunzione fondamentale (Principio Probabilistico):

data una query q e un documento della collezione, il modello probabilistico tenta di fornire una stima della probabilità che l'utente trovi il documento rilevante nei confronti della query e della rappresentazione del documento. Inoltre, il modello parte dall'assunto che esista un sottoinsieme di tutti i documenti che l'utente considera da preferirsi come insieme da fornire in risposta all'interrogazione q. Questo insieme ideale, è denominato R, dovrebbe massimizzare la probabilità di rilevanza per l'utente. I documenti che non appartengono a tale insieme, si dicono "non rilevanti".

L'assunzione non fornisce un modo per calcolare la probabilità di rilevanza di un documento e neppure lo spazio in cui è definita tale probabilità.

Il modello probabilistico assume che, data una query q, venga assegnato ad ogni documento, come misura di similarità , il rapporto Formula 1.19

Formula 1.19 Similarità nel Modello Probabilistico (Forma A)

Il rapporto è dato tra la probabilità che sia rilevante dispetto a q e la probabilità che non lo sia. Valutare l'importanza di un documento utilizzando tale valore, minimizza la probabilità di un giudizio errato.

Nel modello probabilistico, il peso di un termine indice (per i documenti e per le query), viene scelto nell'insieme binario {0,1}. Una query q è un sottoinsieme di termini indice; ponendo R come insieme di documenti conosciuti (o inizialmente supposti) rilevanti, pongo come complementare di R, assegno alla probabilità che il documento sia rilevante nella query q, e alla probabilità che il documento non sia rilevante nella query q,. La funzione di similarità di un documento , rispetto ad una query q, è così definita (Formula 1.20):

Formula 1.20 Similarità nel Modello Probabilistico (Forma B)

Usando il teorema di Bayes e l'indipendenza dei termini, dopo alcuni passaggi matematici si arriva alla formula finale così definita:

Formula 1.21 Similarità nel Modello Probabilistico (Forma C)

Non conoscendo a priori l'insieme R, è necessario trovare un metodo per calcolare le probabilità Un modo molto semplice consiste nell'assegnare , ove è il numero di documenti che contengono il termine indice ed N è il numero totale di documenti nella collezione. Esistono molti altri modi più complessi che tralasciamo.

Si noti, infine, che i vari modelli probabilistici e quello dello spazio vettoriale, possono essere considerati delle estensioni del modello booleano, in quanto fanno ricorso al vettore caratteristico e consentono ricerche in termini di corrispondenza parziale (partial matching) delle caratteristiche tra query e documenti.

1.2.3 Modelli Strutturati

Poniamo il caso che volessimo ricercare un documento nel quale appaiono le parole "distruzione monumenti" e nel testo circostante ci fosse una figura con una didascalia che contiene la parola "statue": con i classici modelli di IR non sarebbe possibile. L'esempio illustrato ricorre a un linguaggio di query che permette di combinare specifiche stringhe con specifiche strutture di documenti. I modelli IR che combinano informazioni sul testo contenuto con informazioni sulla struttura del documento, sono chiamati "Strutctured Text Models".

Esistono diversi modelli che risolvono tale problematica. Vedremo ora i due più rappresentativi, il modello basato su liste non sovrapposte, "Non-Overlapping Lists" e il modello basato sui nodi più vicini, "Proximal Nodes".

1.2.3.1 Modello a Liste Non Sovrapposte

L'idea del modello a liste non sovrapposte [16], "Non-Overlapping Lists", è quella di dividere l'intero testo di ogni documento in regioni non sovrapposte. Ogni regione è rappresentata tramite una lista e per ogni documento esistono liste multiple.

Per esempio (vedi Figura 1.4), possiamo avere una lista di tutti i capitoli del documento, una seconda lista di tutte le sezioni del documento, una terza lista che comprenda tutte le sottosezioni del documento e così via. La separazione delle liste è mantenuta da strutture dati diverse. Le regioni di testo, nella stessa lista, non possono sovrapporsi, mentre regioni di testo di differenti liste possono sovrapporsi.

Avendo suddiviso il documento in liste multiple non sovrapposte, ogni lista rappresenta una struttura dati con una sua struttura indice (ad esempio "inverted file"). Ora possiamo eseguire delle query per ogni documento con riferimenti a strutture diverse, quello che nei modelli tradizionali non poteva essere fatto.

Figura 1.4 Modello a Liste non Sovrapposte

1.2.3.2 Modello a Nodi Prossimali

L'idea del modello a Nodi Prossimali, "Proximal Nodes", più vicino all'asse mediano, sta nel definire una struttura a indici (non-flat) con una gerarchia indipendente sullo stesso documento di testo.

Il modello "Proximal Nodes" è un ampliamento del modello precedente, "Non-Overlapping List", in quanto, tramite una struttura ad indice, lo stesso crea una gerarchia di relazioni tra le varie liste. Per ogni parola viene associata la posizione su ogni lista non sovrapposta (vedi Figura 1.5).

Figura 1.5 Modello a Nodi Prossimali

Un modello a Nodi Prossimali, in definitiva, sarà composto da N liste non sovrapposte e da una lista invertita che lega ogni parola alle varie liste; si crea, così, una struttura ad albero.

Il vantaggio di avere questa struttura si ha quando si vuole ricercare per ogni sezione un termine indice. Con il modello a liste non sovrapposte, questo tipo di ricerca si compie per ogni lista; nel modello a nodi prossimali, invece, una volta trovato il termine indice in una sezione, si scandisce la lista che mantiene la gerarchia e il termine verrà individuato anche nelle altre liste. La complessità computazionale è ridotta di N volte.

1.2.4 Modelli Browsing

Nel caso in cui l'utente non abbia interesse a porre una specifica query al sistema, ma voglia, invece, esplorare lo spazio dei documenti con lo scopo di trovare dei riferimenti che lo interessano, la modalità di reperimento delle informazioni non sarà espletata mediante una ricerca, ma tramite "Browsing".

Sia la ricerca che il "Browsing", [19][28] devono fornire i dati desiderati dall'utente, ma è innegabile che trovare i documenti tramite ricerche, è sicuramente più dispersivo che tramite "Browsing".

Distinguiamo tre tipi di modelli "Browsing" di IR:

• "Flat", basato su un'organizzazione lineare;

• "Strutturato", che presenta un'organizzazione tramite strutture (ad esempio, tramite directory);

• "Ipertestuale", dove le informazioni sono legate attraverso collegamenti logici (link).

1.2.4.1 Modello Lineare

L'idea alla base del modello lineare è la seguente: l'utente esplora lo spazio dei documenti tramite delle strutture lineari (flat). Per esempio, un documento può essere rappresentato con punti in un piano o con elementi in una lista (singola dimensione), oppure è possibile vedere una lista di parole correlate a dei documenti; l'utente non vede il documento visitando la lista, ma può capire se tale documento lo può interessare. Interagendo in questo modo, è possibile ricercare gli elementi rilevanti raffinando le ricerche di volta in volta; questi metodi sono detti "relevance feedback".

Lo svantaggio principale di tale modello è che una volta reperita tale informazione dalla lista "flat", non è chiaro in quale contesto essa sia inserita. Possiamo fare un paragone come esempio: se apriamo un libro in maniera casuale, non possiamo sapere di quale capitolo fa parte la pagina in cui ci troviamo.

1.2.4.2 Modello Strutturato

La navigazione attraverso i documenti (senza consultare delle liste "flat"), può essere facilitata quando i documenti stessi sono strutturati in directory. Le directory sono gerarchie di classi, le quali raggruppano documenti con relazioni comuni. Un esempio calzante può essere rappresentato da un testo di informatica: il primo livello sarà il capitolo del libro, il secondo livello i paragrafi, e così via; l'ultimo livello sarà il testo stesso (flat). Altro esempio: il motore di ricerca Yahoo, partiziona tutti i documenti in categorie (sport, società, scienze), ognuna delle quali, a sua volta, è ulteriormente suddivisa, fino ad arrivare ad una lista flat di documenti.

Lo svantaggio di questo modello è che l'utente deve trovare il filo conduttore, attraverso le categorie proposte, per recuperare i documenti attinenti alla ricerca. In ogni caso, se si riesce a "trovare la strada", il reperimento è veloce e non è dispersivo.

1.2.4.3 Modello Ipertestuale

È fondamentale capire il concetto di sequenza, usato dai due modelli precedenti. Dopo una navigazione flat o strutturata, si arriva al documento; leggendolo, ci si accorge che è interessante approfondire un argomento in esso contenuto. Con i modelli "Flat" o "Strutturato", dobbiamo ricominciare l'esplorazione dall'inizio; ciò può essere un limite in certe situazioni. Con il modello Ipertestuale possiamo "saltare" direttamente all'argomento da approfondire; questo è permesso dai link che si trovano nel documento.

Il modello ipertestuale è un insieme strutturato di informazioni unite fra loro da rinvii a collegamenti logici, i "direct links", ed ha un alto livello di navigazione interattiva, che permette un movimento non sequenziale fra i documenti. Il modello è costituito da nodi, i quali sono correlati da links diretti su di una struttura a grafo.

Ogni nodo è associato ad una regione di testo (un capitolo di un libro, una sezione di un articolo, una pagina web). Due nodi, A e B, possono essere collegati tramite un "direct link lab", mediante una correlazione associata al testo.

Nella forma convenzionale, un ipertesto link lab, è associato come una specifica stringa all'interno del testo del nodo A.

Riassumendo:

• il modello flat è rappresentato da una lista

• il modello gerarchico è rappresentato da una struttura ad albero

• il modello ipertestuale è rappresentato da un grafo.

1.3 Valutazione del Processo Retrieval

Le prestazioni degli "Information Retrieval Systems", [18][30] vengono solitamente valutate tramite una serie di fattori, tra i quali i più rilevanti sono:

• La precisione nel recupero del testo da parte del sistema

• La velocità di recupero da parte del sistema

• La dimensione degli indici creati dal sistema

Questi fattori sono di primaria importanza, perciò nessuno di essi va sottovalutato; per questo motivo, sui suddetti fattori, le case produttrici di software ed i ricercatori, rivolgono i propri studi, sia per ottenere dei risultati più soddisfacenti di quelli tuttora ottenuti, sia per cercare di creare nuove metodologie che aumentino l'efficienza e l'efficacia dei sistemi per il recupero dati.

1.3.1 Introduzione

I fattori di velocità di recupero e dimensione degli indici, dipendono dal disegno del sistema IR e verranno trattati successivamente.

Ora, invece, consideriamo il fattore di precisione del recupero dati.

Essendo il compito di un sistema IR, quello di estrarre da una raccolta di documenti la più grande quantità di informazioni su un dato argomento e niente altro, generalmente il processo di "retrieval", viene valutato in base a due fattori: "recall" (richiamo, ricordo) e "precision" (precisione).

1.3.2 Recall e Precision

Prima di definire "Recall" e "Precision", dobbiamo chiarire cosa si intende per efficienza ed efficacia di un sistema. Diremo, allora, che un sistema è definito efficiente, se riesce a soddisfare gli obiettivi per i quali è stato progettato. Lo stesso sistema risulta efficace, quando raggiunge gli obiettivi seguendo le migliori strategie, ottimizzando le risorse e lavorando nella maniera migliore.

Se applichiamo questi concetti a un sistema IR, possiamo dire che un sistema IR efficiente riesce a recuperare il testo desiderato dall'utente, diventando efficace nel momento in cui riesce a recuperare tale testo seguendo la migliore strategia di lavoro; ad esempio, ottimizzando la velocità o la memoria della macchina occupata.

Le grandezze con cui viene stimata la "bontà" dei risultati forniti in risposta ad una query, sono Precison e Recall. Per completezza, diamo anche la definizione del parametro Fallout.

Definizione di "Precision"

Si definisce "Precision" di un insieme di risultati, il rapporto tra il numero di documenti rilevanti recuperati e il numero di documenti recuperati.

Definizione di "Recall"

Si definisce "Recall" di un insieme di risultati, il rapporto tra il numero di documenti rilevanti recuperati ed il numero di documenti rilevanti presenti nella collezione.

Definizione di "Fallout"

Si definisce "Fallout" di un insieme di risultati, il rapporto tra il numero di documenti non rilevanti recuperati ed il numero di documenti non rilevanti presenti nella collezione.

Un esempio ci aiuterà a chiarire questi concetti.

Disponiamo di una raccolta di 10 documenti, 4 dei quali hanno per argomento le torte di mele, mentre gli altri 6 contengono ricette per cucinare il pesce.

Effettuando una ricerca sulle torte, il processo di "retrieval" restituisce 5 documenti, 3 riguardanti le torte di mele, 2 inerenti la cottura della trota; avremo allora un "recall" pari a 3/4 (75%), ed un "precision" pari a 3/5 (60%).

In definitiva, un buon modello di "retrieval" sarà in grado di massimizzare "recall" e "precision", vale a dire, minimizzare rispettivamente il "silenzio" (assenza di informazione) e il "rumore" (deterioramento dell'informazione, informazioni non pertinenti).

Tali fattori possono essere visti nelle Figure 1.6 -1.7 e nelle Formule 1.22-1.24

Figura 1.6 Recall e Precison

Figura 1.7 Contingenza

Formula 1.22 Precision

Formula 1.23 Recall

Formula 1.24 Fallout

1.3.3 Misure Alternative

I parametri di stima Recall (R), Precision (P) e Fallout (F), malgrado siano i più popolari, non sempre rappresentano i migliori metodi per valutare l'efficienza di una ricerca. Tra i parametri alternativi [16][17][18], vediamo la cosiddetta media armonica, "Harmonic Mean" (F), che è data da:

Formula 1.25 Media Armonica

Una variazione di F è il parametro "E misura"; in tale formula, si introduce un parametro b che serve per dare più importanza al valore di P rispetto a R o viceversa.

Formula 1.26 E misura

Altre composizioni di Precision, Recall e Fallout sono date dalle formule sottostanti, usate per valutare l'efficienza di retrieval di un sistema IR.

Formula 1.27 Meadow

Formula 1.28 Heine

Formula 1.29 Vickery

Formula 1.30 Rijsbergen

1.4 Metodologie per l'Indicizzazione

Fino a questo punto abbiamo parlato dei modelli di un sistema IR e della valutazione del processo di reperimento dati; ora parleremo della composizione delle strutture dati [15][25] che costituiscono il dbase fulltext e delle varie tecniche per comprimere ed ottimizzare le strutture. È da notare che la scelta del modello di IR utilizzato, non ha particolari implicazioni nella scelta della struttura dati e nella sua relativa compressione.

1.4.1 Introduzione

In questo capitolo parleremo delle organizzazioni più usate, come:

• Liste Invertite

• Signatur File

• Bitmap

• Suffix Tree

• Concept Index

Per quanto riguarda le liste invertite, vengono approfondite anche le tecniche per la loro compressione, algoritmi che hanno reso l'utilizzo delle liste invertite, in maniera quasi esclusiva, nei maggiori sistemi di information retrieval.

Di seguito, vengono descritte anche le tecniche per limitare la crescita dei termini indice:

• l'esclusione dei termini contenenti parole non "pertinenti" (stopwords), mediante "Stop List";

• l'esclusione di parole mediante la tecnica detta "Stemming" [78], consistente nell'individuazione di tutti quei termini che hanno la stessa radice.

La riduzione dei termini indice, porta a limitare le strutture dati del dbase fulltext e quindi a ridurre i tempi di esecuzione delle query.

1.4.2 Liste Invertite

Un indice è un meccanismo per ricercare un dato termine in un testo. Esistono diversi metodi per archiviare un indice; nelle applicazioni che coinvolgono del testo, un metodo usato è quello mediante liste invertite o comunemente detto "inverted file" o "posting file".

La struttura a liste invertite è composta principalmente da due elementi: il Vocabolario e le Occorrenze.

Il Vocabolario L (lessico), è una struttura che contiene, in modo univoco, tutte le differenti parole contenute nella collezione di documenti.

Si definisce posting, relativo ad un termine t, una coppia formata da due valori numerici, e , dove, è l'ID del documento che contiene il termine t e è il peso che il termine t assume in .

Possiamo quindi dare la definizione di lista dei posting.

Sia L un Vocabolario; la lista dei posting (riferimenti) per un termine , è una sequenza di posting relativi al termine t.

Si definiscono Occorrenze, l'insieme di tutte le liste di posting:

occorrenze = , dove N è il numero di parole distinte (tutti i termini del vocabolario |L|) e è la lista dei posting associata al termine i-esimo.

Concludendo: le liste invertite sono composte da un vocabolario e da una struttura che contiene tutte le occorrenze (vedi Figura 1.8). È importante notare che lo spazio richiesto per memorizzare il vocabolario, è abbastanza contenuto: l'ordine di grandezza è dato da , dove alfa è una costante compresa tra 0 ed 1 e dipende dal testo (tale costante, in pratica, è compresa tra 0.4 e 0.6). Le occorrenze, al contrario, richiedono molto più spazio (ordine di grandezza pari a O(N)). Attuando delle opportune tecniche di compressione, lo spazio occupato viene ridotto notevolmente. Vediamo ora come vengono costruiti gli indici e, successivamente, le tecniche di compressione delle loro strutture.

Figura 1.8 Inverted File Index

Questo metodo è basato sulla scomposizione del testo da indicizzare in singoli termini, nel nostro caso le parole. Il testo da indicizzare, viene suddiviso in singole parole che vengono analizzate e filtrate in modo da eliminare i duplicati e i termini più comuni presenti nel documento. Questa operazione viene effettuata analizzando la frequenza associata ad ogni termine presente nel documento (quante volte lo stesso termine viene ripetuto nel testo). Finita questa prima operazione di filtraggio, si avrà una tabella del tipo:

In questa tabella, ad ogni parola è associata una frequenza che indica quante volte la parola è presente nel documento; poi si deve individuare una soglia di frequenza al di sopra della quale si devono eliminare le parole. Solitamente la soglia è del 25%-30%; in altri termini, una parola viene eliminata dall'indice se è ripetuta più del 25% di volte del totale delle parole presenti nel documento. In questa maniera si crea una lista di termini ripulita da tutte le parole comuni, come articoli, avverbi, congiunzioni, ecc. Tale metodo è anche detto eliminazione per "Stop List Dinamiche"².

Una ulteriore scrematura, può essere effettuata utilizzando quella che viene definita la "Stop list". In questa lista vengono inserite tutte quelle parole che non si vogliono indicizzare perché, o troppo comuni o di scarso significato ai fini del recupero; tali parole sono definite "Stopwords".

Dopo aver compiuto queste operazioni, si otterrà una lista di parole ripulita da tutti i termini duplicati, dalle parole comuni e dalle parole volutamente eliminate tramite la stop list. Nella lista finale, saranno presenti solo i termini rappresentativi del documento utili ai fini della ricerca.

A questo punto, in teoria, il metodo "inverted index" passa alla determinazione delle "Stems" [78], cioè all'individuazione di tutti quei termini che hanno la stessa radice e che possono essere recuperati tramite essa. In questa maniera si riesce a diminuire ulteriormente il numero di parole che l'indice dovrà trattare. Bisogna comunque sottolineare come quest'ultima operazione, in pratica, non viene quasi mai effettuata vista la sua complessità: infatti, solo sistemi molto sofisticati riescono a classificare correttamente i termini che hanno le stesse stems, ma significati diversi, come ad esempio le parole "importante" - "importate".

L'ultimo passo che permette di creare l'indice, è quello che associa alle parole selezionate, le precedenti fasi di locazione. In questa fase si stabilisce la relazione (Parola, Locazione), che fa corrispondere ad ogni parola il file o la linea di testo contenente il termine cercato.

Vediamo più in dettaglio come viene implementata la compressione sulle strutture ad indice.

Comprimere le strutture ad indice ha molti vantaggi, il più rilevante dei quali, è la riduzione delle operazioni su disco; inoltre, nei sistemi con molta memoria, gli indici compressi potrebbero essere mantenuti nella memoria stessa eliminando completamente I/O su disco. Lo svantaggio è che si devono eseguire calcoli aggiuntivi per decomprimere i dati, ma questo non è un problema con le attuali velocità di elaborazione, considerato che l'overhead maggiore per una query è I/O su disco.

Per comprimere le liste invertite, esistono numerose tecniche, le più comuni ed efficienti delle quali si basano sulla rappresentazione costruita sui cosiddetti "d-gap". Definiamo il concetto di "d-gap".

Definizione di "d-gap"

Consideriamo una generica lista invertitaassociata ad un termine t, che compare nella collezione con una frequenza ,dove, è l'identificativo del documento in cui appare il termine t. La lista è ordinata secondo il "document-id",, per cui . Si definisce d-gap, la differenza traconsecutivi. d-gaps =

Per esempio, consideriamo la lista invertita :

<8; 3,5,20,21,23,76,77,78>

dopo una trasformazione in d-gap la nuova lista diventa:

<8; 3,2,15,1,2,53,1,1>

Le sequenze di d-gap sono un altro modo di vedere le liste dei posting; il numero di bit necessari per codificare ogni elemento, utilizzando una rappresentazione binaria semplice, è sempre , con N pari al numero dei documenti della collezione. Considerare ogni lista come una sequenza di d-gap, limitata superiormente da N, permette di utilizzare le tecniche di compressione studiate appositamente per questo tipo di rappresentazione. La Tabella 1.1 mostra vari modelli per la compressione delle liste di d-gap.

I metodi "Globali" utilizzano informazioni cumulative raccolte su tutte le liste, quelli "Locali" si "adattano" ai dati contenuti singolarmente in ogni lista, mentre i metodi "Parametrizzati" utilizzano coefficenti forniti dall'esterno, che servono all'algoritmo per realizzare una migliore compressione.

Senza dilungarci a descrivere i vari metodi, mostriamo una tabella comparativa di performance, considerando la collezione conosciuta come TREC [48][30].

Concludendo: in un sistema IR, per indicizzare grandi quantità di testo, è opportuno usare un indice a liste invertite con compressione dei posting, rappresentando l'alfabeto con un Avl [52] compresso matematicamente con algoritmi come il Bzip2 [54]; è proprio questo il metodo che viene utilizzato nel sistema di information retrieval distribuito (NSE) che vedremo in seguito.

1.4.3 Signature File

Il metodo "Signature File", utilizzato per creare gli indici, è del tipo probabilistico e usa una funzione hash (signature, firma) che ha la funzione di mappare le parole con una maschera di B bit. Il documento viene diviso in blocchi di b parole; per ogni blocco di testo di lunghezza b, viene assegnata una maschera di B bit. Questa maschera viene ottenuta facendo OR di tutte le "firme" delle parole contenute nel blocco, quindi, la "signature file" non è altro che una sequenza di maschere di bit per tutti i blocchi, ciascuno con il relativo puntatore. Il metodo si basa sul seguente assunto: una parola, presente nel blocco di testo, avrà tutti i bit posti ad 1 nella sua signature e, di conseguenza, anche nella maschera associata al blocco.

La Figura 1.9 mostra il concetto.

Figura 1.9 Signature File

La scelta di questo metodo tende, evidentemente, a creare indici di modeste dimensioni, facilmente consultabili e molto veloci nel recupero delle informazioni. D'altra parte, all'alta velocità si contrappone una bassa precisione di recupero, legata proprio alla scarsa precisione e alla quantità dei termini indicizzati con i quali soddisfare le query dell'utente.

Inoltre, la funzione hash può far corrispondere una stessa signature a parole differenti; questo non si può evitare, ma aumentando la dimensione dei bit della signature e scegliendo opportunamente la funzione hash, si può ridurre di molto questo effetto di ambiguità. Un ulteriore svantaggio del metodo, è insito nella scansione lineare degli indici (riducibile in sublineare), motivo che rende il "Signature File" non applicabile a collezioni di grandi dimensioni. Per questo motivo, il "signature index" viene utilizzato per creare sistemi di recupero che lavorano su banche dati contenenti articoli, pubblicazioni, ed in genere tutte le informazioni nelle quali è presente un abstract che riassume le parti essenziali del testo vero e proprio. Nell'abstract, la parte che noi indicizziamo, sono presumibilmente contenute tutte le parole "significative" che permettono il recupero del documento.

Anche per questo metodo, essendo basato su sequenze di bit molto efficienti, esistono tecniche di compressione; inoltre, esistono tecniche di rappresentazione della lista in matrice, "bitsliced signature files", che rendono più efficiente la sua scansione.

1.4.4 Bitmap

Il metodo "bitmap" [1], utilizzato per creare gli indici, è molto semplice. Tale metodo associa per ogni parola, , una sequenza di bit, V, il cui i-esimo bit, , viene posto ad 1 se, e solo, se il termine è contenuto nel documento i-esimo.

Per una collezione di N documenti e di T termini indice distinti, si avrà una dimensione della bitmap pari abit. Considerando una collezione di 1.500.000 di documenti e 300.000 termini indice distinti, si avrà una occupazione di memoria pari a 1.500.000*300.000 bit, che corrispondono a circa 450Mb, una quantità di memoria enorme. Anche attuando opportune tecniche di compressione, le dimensioni rimangono enormi rispetto alle liste invertite.

Il vantaggio dell'indice "bitmap", consiste nel permettere implementazioni efficienti di query di tipo booleano: basterà applicare l'operatore di congiunzione logica alle sequenze di bit legati ad ogni parola della query, per ottenere, immediatamente, la lista dei documenti.

1.4.5 Concept Index

Il metodo d'indicizzazione Concept Index, si basa sulla conoscenza di concetti chiave con i quali costruire una rete di relazioni fra i termini del documento indicizzato [41][44]. La navigazione in questa rete permetterà, per gradi, di andare ad individuare il termine e quindi il documento da recuperare (vedi Figura 1.10).

Figura 1.10 Concept Index

Questo metodo, anche se in alcuni casi è molto efficiente, specie per particolari classi di documenti che si riferiscono ad una stessa terminologia, non è molto utilizzato, in quanto è complesso da implementare. Inoltre, i sistemi che utilizzano il concept index, dipendono in maniera significativa dal modo in cui sono espressi i concetti alla base della rete relazionale.

Per migliorare l'efficienza del metodo, intervengono nel processo di recupero ed indicizzazione, vocabolari e sinonimi che accrescono la base di conoscenza (i concetti), affinché possano essere soddisfatte anche quelle query non direttamente riconducibili all'indice creato. I limiti del metodo emergono nel confronto con testi di carattere generale, per i quali l'utilizzo dei tesauri non è sufficiente.

Va comunque sottolineato il pregio di questo metodo, che permette di ottenere, come risultato della ricerca, oltre che il testo direttamente collegato alla query, anche altri testi che possono essere equivalenti o "vicini" alla query richiesta. L'utente, nel peggiore dei casi, avrà in risposta una serie di documenti comunque attinenti all'argomento d'interesse.

Il concept index è tuttora in via di sviluppo grazie all'utilizzo delle reti neuronali, all'intelligenza artificiale ed alle tecniche di lavoro collaborativo, che stanno diventando sempre più diffuse tramite Internet e l'utilizzo delle reti di computer.

1.4.6 Suffix Tree

Gli indici presentati fino ad ora, assumono che il testo possa essere visto come una sequenza di parole. Questa assunzione limita la granularità del problema (l'elemento minimale è la parola), restringendo le possibili interrogazioni alle parole presenti nella collezione di documenti, legate da operatori booleani indicati esplicitamente od implicitamente nella query.

Il metodo d'indicizzazione Suffix Tree [16], considera il testo come un'unica stringa. Ogni posizione del testo è considerata come un suffisso del testo stesso, come si vede in Figura 1.11 (una stringa che inizia da una posizione qualsiasi e termina alla fine del testo).

In base a quanto sopra, definiamo le due, seguenti, conseguenze:

• Due suffissi che iniziano a partire da posizioni differenti, sono lessico-graficamente differenti.

• Ogni suffisso è univocamente identificato dalla sua posizione.

Figura 1.11 Esempio di Suffissi

La struttura dati utilizzata per memorizzare i Suffix Tree, è detta "Patricia Tree". In questa struttura, i suffissi sono memorizzati utilizzando il minor numero possibile di nodi, cifra che dipende in modo lineare (O(n)), dal numero di suffissi. La Figura 1.12 mostra la struttura Suffix Tree.

Figura 1.12 Suffix Tree

Gli svantaggi di questo metodo sono principalmente due: il costo computazionale del processo di costruzione degli indici, molto elevato, e il testo indicizzato che deve essere disponibile quando si esegue una query.

Il Suffix Tree, quindi, viene usato nei casi in cui le query richiedono la complicata implementazione descritta sopra. Una precisazione importante: se si reperiscono i dati con il metodo "liste invertite" e successivamente si aprono i documenti, l'esecuzione delle ricerche sequenziali (con metodologie di BF, KMP, String Matching, Regular Expression), sarà in molti casi più efficiente, in termini di tempo e di spazio, rispetto all'utilizzo del metodo Suffix Tree.

Capitolo 2

IR in Ambiente Parallelo e Distribuito

2.1 Introduzione

Nel capitolo precedente, Fondamenti di IR, abbiamo fornito informazioni sui vari modelli di IR e sulle metodologie per la loro indicizzazione. Al crescere delle dimensioni della collezione, però, le performances cominciano a decadere. Per ovviare a questo inconveniente, è opportuno usare architetture distribuite e parallele [69] per i sistemi di information retrieval.

Nei paragrafi seguenti, descriveremo come vengono adattati i modelli di IR nella architetture distribuite e parallele [21][22], oltre ai vari metodi di partizionamento delle collezioni, per poter rendere scalabile il sistema senza dover perdere in performance e in trasparenza.

2.2 Computer Paralleli

L'elaborazione parallela si ha quando un'applicazione, per risolvere un singolo problema, usa simultaneamente N processori: ognuno di questi processori, lavora su di una differente parte del problema.

In questo modo, i tempi di elaborazione vengono ridotti al tempo necessario per la soluzione di ogni singola parte del problema, portando una "scalabilità elaborativa" dell'applicazione.

Il parallelismo può apparire a diversi livelli; è quindi utile classificarlo nelle diverse alternative [73]:

• Flusso singolo di istruzioni e flusso singolo di dati (SISD)

• Flusso singolo di istruzioni e flusso multiplo di dati (SIMD)

• Flusso multiplo di istruzioni e flusso singolo di dati (MISD)

• Flusso multiplo di istruzioni e flusso multiplo di dati (MIMD)

Il calcolatore SISD è il classico computer che esegue sequenzialmente il programma, usando un unico processore.

Il calcolatore SIMD opera su un vettore di dati; per esempio, quando una singola istruzione richiede una somma di N numeri, la macchina simd manda N flussi di dati a N ALU per effettuare N somme nello stesso ciclo di clock.

Il calcolatore MISD usa N processori su di un singolo flusso di dati, su di una memoria condivisa.

Il MIMD è la più popolare classe di archittetture parallele. Il calcolatore mimd opera con N processori, su N flussi di istruzioni ed N flussi di dati; possiamo rappresentare il mimd, come una serie di sistemi sisd, con una "hardware cache coerenza" delle memorie, condivisa.

I sistemi mimd usano la memoria condivisa o comunicazione attraverso la rete, per interagire tra di loro; i processori di questi sistemi, possono lavorare in modo separato o possono cooperare per risolvere un singolo problema, aumentando la flessibilità.

Un sistema mimd con un alto grado di interazione fra processori, è chiamato "tightly coupled", come, ad esempio, i sistemi SMP (Symmetric Multiprocessors).

Un sistema mimd con un basso grado di interazione fra processori, è chiamato "loosely coupled", come ad esempio le architetture distribuite di computer o Cluster.

La principale differenza fra un sistema mimd di computer paralleli e un sistema mimd di computer distribuiti, è il costo della comunicazione fra processi, molto maggiore nel sistema distribuito rispetto al parallelo. A seconda delle applicazioni e del loro costo, è preferibile l'uno o l'altro, o la loro unione.

2.3 Misura delle Prestazioni

Quando usiamo elaborazioni parallele, ci accorgiamo che le performance migliorano. Vediamo in che proporzione avviene questo miglioramento.

Se il tempo di elaborazione di una procedura su un sistema SISD è K, ipoteticamente, su di un sistema di MIMD con N processori, dovrebbe essere K/N. Vedi Formula 2.1

Formula 2.1 Misura Performance in Sistemi Paralleli

Idealmente, quando elaboriamo un algoritmo parallelo su N processori, dovremmo ottenere un aumento di velocità, "Speedup", pari a S=N; in pratica, il problema deve essere suddiviso in N sottoproblemi, dato che l'architettura parallela impone un overheads dovuto a sincronizzazione e a schedulazione dei sottoproblemi, oltre alla possibilità di avere componenti sequenziali che non possono essere parallelizzate. Considerando tali situazioni, si ottiene la seguente Formula 2.2, che ci dà la massima "Speedup" in relazione con f (frazione del problema che deve essere elaborato sequenzialmente).

Formula 2.2 Massimo Speedup ottenibile

La misura dell'efficienza di un sistema parallelo viene data come rapporto di S (incremento di velocità) ed N (numero di processori del sistema parallelo); vedi Formula 2.3.

Formula 2.3 Efficienza sistema Parallelo

2.4 Sistemi Paralleli IR

In questo capitolo sviluppiamo algoritmi di Information Retrieval su architetture parallele MIMD.

Uno dei problemi fondamentali di un sistema di IR, consiste nel fornire, in breve tempo, le risposte che l'utente richiede. Gli ostacoli, principalmente, sono costituiti dalle molte richieste contemporanee e dalle dimensioni sempre più ampie delle collezioni di documenti.

Vedremo, di seguito, le tecniche di multitasking e di parallelismo per elaborare le query, oltre ai metodi di scomposizione delle collezioni che consentono di sfruttare il parallelismo.

2.4.1 Architettura MIMD

L'architettura MIMD offre i migliori vantaggi per sfruttare il parallelismo; un semplice modo tra questi, per esempio, è l'implementazione del multitasking [16] (vedi Figura 2.1).

Figura 2.1 Multitasking Parallelo su macchine MIMD

In questo modo, le query verranno elaborate non da un unico processo, ma da N processi; come conseguenza, ad ogni processo verrà assegnato un processore, aumentando la velocità di elaborazione di query concorrenti. Più processori avremo, più query contemporanee elaboreremo velocemente.

È da notare che, tale implementazione, non aumenta la velocità di eleborazione di una singola query.

Un altro metodo usato per sfruttare il parallelismo, si fonda sul partizionamento di ogni processo di query in sottoprocessi, che verranno, successivamente, elaborati in parallelo (vedi Figura 2.2).

Figura 2.2 Partizionamento Parallelo dei processi su macchine MIMD

Con questo processo, ogni singola query viene scomposta in N sottoquery elaborate parallelamente e successivamente inviate al Broker, che le unirà e ne invierà il risultato. È importante considerare, che l'implementazione riduce il tempo di elaborazione di una singola query.

Unendo i metodi di multitasking e partizionamento, si ha il massimo del parallelismo per l'implementazione del processo di Retrieval su di un sistema IR. I due metodi possono essere applicati ad altri processi, come quello di reperimento dati ("Spider") e di indicizzazione.

La struttura indice della collezione, infatti, costituisce un altro problema nei sistemi IR; essendo, questo tipo di struttura, di grandi dimensioni, per ragioni di efficienza essa viene suddivisa mediante vari metodi, due dei quali, "Documention Partitioning" e "Term Partitioning", verranno descritti di seguito. Nel "Documention Partitioning", l'intera collezione dei documenti viene suddivisa in varie partizioni, ed ognuna di esse viene assegnata ad un particolare elemento di calcolo all'interno del sistema (vedi Figura 2.3); ogni processore, quindi, avrà un proprio indice contenente soltanto i documenti della partizione ad esso assegnata.

Figura 2.3 Modalità di Partizionamento: Documention Partitioning

Con il metodo "Term Partitioning", si costruisce, in una prima fase, l'intero indice e, successivamente, si partiziona il lessico e le liste associate ai termini che compaiono in ogni partizione (vedi Figura 2.4).

La suddivisione dell'indice può essere fatta anche per altre classificazioni (ad esempio, suddividendo per data il documento indicizzato).

Figura 2.4 Modalità di Partizionamento: Term Partitioning

Su ambedue i modi di suddivisione, sono stati condotti numerosi studi e varianti, per sfruttare al massimo le configurazioni hardware (sistemi Paralleli e Clustering).

2.5 Sistemi Distribuiti IR

In questo capitolo svilupperemo algoritmi di Information Retrieval su architetture distribuite, simili alle architetture parallele di tipo MIMD viste precedentemente.

L'elaborazione distribuita è un'applicazione che consta di molti computer connessi attraverso una rete, adatti a risolvere un singolo problema.

Un sistema di computer distribuiti può essere visto come una serie di processori paralleli di tipo MIMD (con un alto costo di comunicazione tra processori); inoltre, tale sistema si serve di una collezione di computer diversi fra loro.

2.5.1 Architettura Distribuita

Un Sistema Distribuito consiste in una collezione di computer autonomi collegati attraverso una rete e con un software di base distribuito. Il software ha il compito di coordinare le attività e di condividere le risorse (hardware, software, dati) fra i vari computer, detti comunemente nodi.

In un Sistema Distribuito IR, i vari nodi svolgono un'attività ben precisa, mentre le varie attività comunicano tra di loro attraverso una rete. Il protocollo di comunicazione tra nodi, in genere, è il TCP/IP, ma se il numero di nodi è molto alto, l'overhead del TCP/IP non è più sostenibile; si usano, allora, altri protocolli più specifici.

Come si vede dalla Figura 2.1, ogni entità può essere vista come un nodo o come una serie di nodi. Questo per avere un bilanciamento di carico e un alto grado di affidabilità e disponibilità dei servizi.

In un Sistema Information Retrieval su di una architettura distribuita, i problemi di carico possono essere "eliminati" aumentando i nodi (i quali possono essere clusterizzati per ottenere un'alta affidabilità HA). L'aumento deve comprendere tutti gli aspetti del sistema, per non creare colli di bottiglia.

Un ulteriore problema è rappresentato dalle grandi dimensioni delle strutture indice. Anche in questa situazione si possono applicare i metodi precedentemente illustrati, "Document Partitioning" e "Term Partitioning".

A nostro avviso, un sistema parallelo clusterizzato ha lo stesso grado di affidabilità, bilanciamento e disponibilità dei servizi di un sistema distribuito equivalente, ma comporta costi di gran lunga inferiori, aspetto che assume una notevole rilevanza; per di più, se usiamo sistemi operativi OpenSource, come Linux, riduciamo notevolmente anche i costi del software.

Molte applicazioni commerciali, derivate dall'Opensource, sono equivalenti alle Opensource stesse; la sola differenza, individuabile nelle OpenSource commerciali, sta nella riunione di tutti i "pezzi di software" e nella creazione di una semplice interfaccia di configurazione ed installazione.

Capitolo 3

Architettura del Sistema Distribuito IR

3.1 Introduzione

Gli obiettivi principali di tale architettura, sono: Flessibilità, Concorrenza, Scalabilità, Affidabilità, Trasparenza e Bilanciamento [69][74].

La "Flessibilità" consente al sistema di essere composto da macchine disomogenee; infatti, i nodi del sistema possono essere su piattaforme differenti. L'unica discriminante che deve accomunare i vari nodi del sistema, è la possibilità di comunicare, attraverso network, tramite protocolli TCP/IP [68]. Il linguaggio usato, il C, rende flessibile la portabilità su molti ambienti operativi. In definitiva, possiamo implementare un sistema su piattaforme disomogenee, che utilizza, in altre parole, hardware e sistemi operativi differenti.

La "Concorrenza" è data dal fatto che ogni richiesta viene polverizzata su N nodi, cioè, molti processi vengono eseguiti simultaneamente. Questo porta al massimo della concorrenza, in quanto per ogni richiesta di query tutti gli N nodi lavorano in parallelo.

La "Scalabilità" è la possibilità di potenziare o aumentare il numero di nodi, senza dover riconfigurare il sistema; nel nostro caso, quando viene aggiunto un nodo, il sistema lo identifica automaticamente attraverso il rilevamento della topologia di rete. La nostra potenza di calcolo aumenta linearmente.

L'"Affidabilità" è il funzionamento corretto del sistema, anche in caso di errore. Come vedremo in seguito, il disegno del sistema è fatto in modo da essere ridondante, sia dal punto di vista hardware che software. Se un nodo non dovesse rispondere, il sistema, dinamicamente, lo escluderebbe dalla sua topologia; nel caso che il nodo dovesse tornare attivo, il sistema lo includerà automaticamente nella topologia. In genere, esistono due metodi per avere sistemi ad alta affidabilità: nel primo, ad una macchina attiva, si associa una macchina in standby, che si attiverà solo in caso di blocco della principale; nel secondo, il sistema sarà composto da più macchine sempre attive, che gestiranno alternernativamente le richieste, per mezzo di un software specifico. In quest'ultimo caso, non avremo mai macchine in standby e, di conseguenza, potremo utilizzare contemporaneamente tutti i nodi della rete e non avremo spreco di risorse.

Il sistema, disegnato secondo le nostre esigenze, può avere un grado di "fault tolerance" differente, questo perchè maggiore è il grado, maggiore è il costo.

La "Trasparenza" consiste nel nascondere la complessità del sistema; infatti, il client che invia una query al sistema, non deve preoccuparsi di come esso sia strutturato e questo vale anche per i processi Agent. I Broker, dal canto loro, modificano dinamicamente la topologia del sistema, se avviene qualcosa di anomalo. La trasparenza del sistema, quindi, raggiunge un grado abbastanza elevato che si potrebbe aumentare, come vedremo nel capitolo Conclusioni e Sviluppi Futuri.

Il "Bilanciamento" è la possibilità di usare tutte le risorse in modo equo. I Broker, infatti, lavorando con una politica RR (Round Robin), riutilizzano la stessa risorsa solo dopo aver usato tutte le altre almeno una volta. Anche i client possono usare tale accorgimento. Con questo modus operandi, si ha un bilanciamento "perfetto". Il bilanciamento è statistico e non calcolato in base al carico del sistema, in quanto, avendo macchine dedicate, la responsabilità del carico è del Sistema Distribuito IR e quindi già ponderato in fase di disegno.

Come vedremo in seguito, il Sistema Distribuito IR è suddiviso in N Partizioni, ove ogni Partizione è una parte distinta del dbase distribuito (il dbase è fisicamente diviso in N Partizioni). Ogni partizione è autonoma e disgiunta rispetto alle altre partizioni; i processi che la gestiscono hanno anche il compito di gestire i Faults.

3.2 Flussi di N Partizioni

Tutto il nostro Sistema Distribuito IR, è stato scomposto in N partizioni (vedi Figura 3.1); in ogni partizione abbiamo una parte del dbase distribuito.

Il tipo di partizionamento scelto è quello fisico, cioè ogni partizione è disgiunta con tutte le altre; questo ha il vantaggio di eliminare le analisi sul tipo di query, anche se, ad ogni richiesta di informazioni, tutte le partizioni dovranno essere interrogate.

Ogni partizione sarà composta da N Brokers e da K Agent.

Il Broker riceve le query dal Client e le assegna ai suoi Agent, i quali gestiranno le richieste, inviandole successivamente al Client.

Gli Agent, che come abbiamo visto ricevono le query dal proprio Broker, reperiranno le informazioni atte a soddisfare le richieste, dal dbase distribuito.

Il Client invia una query ad un Broker che risiede in una partizione. Il Broker attiva un Agent (che chiameremo "concentratore"), che si libererà solo a query completata. L'Agent "concentratore" contatterà i Broker delle altre partizioni per farsi inviare i risultati della query distribuita e, quindi, rimarrà impegnato più a lungo rispetto agli altri processi in corso. Dopo aver ricevuto i dati, l'Agent "concentratore" si assumerà il compito di inviare il risultato della query al Client. I dati ricevuti dall'Agent "concentratore", provengono dagli Agent delle altre partizioni, i quali lavorano in modalità "locale"; in altre parole, gli Agent "locali", reperiscono i dati localmente e li inviano all'Agent che ha richiesto la query.

Le interazioni tra partizioni, avvengono attraverso il Broker o L'Agent:

• nel caso del Broker, ciò avviene per l'aggiornamento della topologia di rete.

• nel caso dell'Agent in modalità "concentratore", l'interazione avviene per inviare le richieste di query ai Broker delle altre Partizioni.

• nel caso dell'Agent in modalità "locale", l'interazione avviene per inviare il risultato della query all'Agent "concentratore".

Come vediamo in Figura 3.1, la "Nuvola" Client è distinta in due casi: nel primo, il Client sceglie di inviare le query ad un Broker (se il Broker non dovesse rispondere, il Client ne dovrà scegliere un altro), mentre, nel secondo caso è la "Black-Box" ("smistatore") che sceglie, con una sua logica, il Broker adatto. È facile dedurre che, nel primo caso il Client deve, obbligatoriamente, gestire una situazione che, in alcuni casi, può rendere meno trasparente il sistema; nel secondo caso, invece, il Client, sfruttando il lavoro dello "smistatore", rimarrà semplicemente in attesa della risposta alla propria query.

3.3 Flussi di una Partizione

Analizzando in modo sempre più dettagliato il sistema, vediamo com'è costruita una Partizione. Al minimo, una partizione può essere costituita da un Broker e da un Agent, il quale avrà l'ennesima parte del dbase distribuito (vedi parte (A) in Figura 3.2).

L'esempio mostrato in Figura, indica che ogni Partizione è divisa in due parti, Replica A e Replica B che, come dice chiaramente il nome, sono speculari e servono per gestire i Faults, sia Hardware che Software. In ogni replica ci sono N Agent, ognuno dei quali ha un dbase (l'ennesima parte del dbase distribuito) collegato tramite VFS (Virtual File Systems). Tutti gli Agent della replica, vengono gestiti solo dal relativo Broker di replica, che gestirà anche i Faults e l'occupazione degli Agent.

A seconda della modalità di lavoro dell'Agent, esso invierà i dati della Query ai Broker o al Client.

Il Broker assegna in modo ciclico le richieste pervenute dal Client o da un Agent di un'altra partizione, selezionando il successivo Agent attivo.

Chiaramente, se un Agent "cade", sarà il Broker corrispondente a gestirlo; ma cosa succede se cade un Broker?

È il Client che dovrà farsi carico della caduta del Broker, bilanciando il carico e distribuendo le query su tutti i Broker della Partizione (vedi, in figura 3.2, "Broker Replica A" e "Broker Replica B"). Tale "ping-pong" tra i Broker, in ogni modo, è gestibile esternamente, per esempio, utilizzando un DNS. Esistono anche altre tecniche e software specifici più efficienti, che però esulano da questa trattazione.

Partendo dal presupposto che, nelle partizioni, le repliche sono completamente indipendenti e i dbase associati agli Agent sono clonati; che ogni Agent con il suo dbase è indipendente e che una Replica dentro una partizione è gestita da un Broker, possiamo dire che un Agent riceverà richieste solo dal proprio Broker e invierà le risposte al Client o ad un Broker di un'altra Partizione, mentre il Broker riceverà richieste dai Client o dagli Agent di altre Partizioni. Teniamo presente che tutti i Broker si scambiano informazioni in tempo reale sulla topologia di rete.

Il massimo dell'Efficienza è avere un processore dedicato per ogni Agent e per ogni Broker, in modo da non avere nessun tipo di overhead. Facendo lavorare un PC, rispettivamente, per ogni Agent e per ogni Broker, la nostra partizione sarà composta (come si vede in figura 3.2), da otto PC.

Il vantaggio di avere delle repliche nella nostra partizione, oltre a rendere trasparente i Faults, consiste nella possibità di aggiornare il Dbase e contemporaneamente, soddisfare le query; vediamo come questo avviene.

Disattivando il Broker viene bloccata la sua replica; l'attività, comunque, continua regolarmente anche utilizzando solo l'altra replica (chiaramente, le repliche possono essere due, come nel nostro esempio, o più). Una volta concluso l'aggiornamento, si riattiva la partizione riattivando il Broker e poi si reitera la stessa operazione per ogni replica e il gioco è fatto.

Possiamo aggiungere che le repliche lavorano in parallelo e che non esiste una replica attiva e un'altra (o altre) in standby. Nella figura 3.2, gli agenti che smaltiscono le richieste, sono sei: se ogni query viene evasa in tre secondi (posto come esempio), con sei Agent verranno "smaltite" sei query ogni tre secondi. Di conseguenza, posso inviare una query distinta, ogni mezzo secondo. È palese il risultato che si raggiungerà con questa modalità: aumentando il numero delle repliche, aumenterà, proporzionalmente, il numero delle query distinte per unità di tempo, che si possono evadere.

Tutte le comunicazioni di cui abbiamo trattato poc'anzi, avvengono tramite rete TCP/IP [68], per cui fisicamente i nodi possono essere localizzati in ambienti separati, in modo da aumentare il grado di sicurezza. Per esempio, nel caso la nostra partizione fosse composta di due repliche, site in due ambienti diversi (ad esempio, al Gazzettino sede di Mestre e al Gazzettino sede di Padova), un qualsiasi incidente che in uno dei due ambienti comporti la inagibilità del locale e quindi il mancato funzionamento della nostra replica, non avrebbe alcuna ripercussione sul funzionamento dell'altra replica.

3.4 Flussi Del Broker

Il Broker gestisce tre flussi distinti: i flussi del Client, dell'Agent e del Broker, come si vede in Figura 3.3

Il flusso del Client, interagisce solo con una partizione. Il client invia una richiesta al Broker (A1) ed il Broker assegna l'Agent che la deve evadere, inviandogli tale richiesta (B1).

In questo caso, l'Agent lavorerà nella modalità "Concentratore", ossia, riceverà tutte le query locali di ogni partizione e le invierà al Client che ha formulato la richiesta.

Il flusso dell'Agent proviene da una delle altre partizioni. Il Broker, di fatto, riceve una richiesta da un Agent che risiede su di un'altra partizione e l'assegnerà ad un proprio Agent (A2). In questo caso, l'Agent lavorerà nella modalità "Locale", eseguendo una query locale destinata all'Agent che ha inviato la richiesta al Broker. Tale Agent, ovviamente, lavora nella modalità "concentratore".

L'ultimo flusso interagisce con tutte le altre partizioni, per il ricalcolo della topologia di rete: allo scadere di un certo tempo prefissato, il flusso invia a tutti gli altri Broker, una richiesta di "Keep-Alive" e, a seconda delle risposte, crea una topologia di rete. È importante rilevare che, dal grafo dei Broker, il flusso estrae un albero ogni volta differente, per aumentarne il bilanciamento.

Figura 3.3 Flussi del Broker

3.5 Flusso dell'Agent

L'Agent, sebbene lavori in due modalità, "Locale" o "Concentratore", ha un solo flusso. Ogni Agent viene gestito da un solo Broker, per cui, se un Agent va Down, sarà compito del Broker che lo gestisce rilevarlo ed escluderlo dalla sua lista. Per tutti gli altri nodi del Sistema Distribuito IR, questa situazione è trasparente. Premesso ciò, ogni Agent riceverà la richiesta di query dal proprio Broker (A).

L'Agent analizza la richiesta, dopo averla ricevuta e controllata; se la richiesta è corretta, l'Agent distingue i due casi, Locale e Concentratore. Se la richiesta ricade nel primo caso, l'Agent esegue la Query Locale (B1), e successivamente invia la risposta all'Agent concentratore (D), mentre se si ricade nel secondo caso, l'Agent esegue la Query Locale (B1) ed invia la richiesta agli N-1 Broker (B2) (dove N è il numero di partizioni del dbase distribuito). Dopo questa operazione, il sistema attende le risposte dagli Agent (C). Quando tutte le risposte saranno pervenute o quando è scaduto il tempo di ricezione, verrà conclusa la fase di acquisizione delle informazioni, le quali saranno inviate al Client (D) (vedi Figura 3.4).

Figura 3.4 Flussi dell'Agent

3.6 Flusso della Query

A questo punto, dopo aver spiegato l'architettura del Sistema Distribuito IR, vediamo cosa avviene quando un Client invia una query (vedi Figura 3.5).

Il Client invia la query al Broker (A), la analizza e, se è corretta e completa, seleziona un proprio Agent attivo, con politica RR (Round-Robin), e gli invia (B), oltre alla query, gli indirizzi degli altri Brokers e del Client che ha formulato la richiesta.

L'Agent scelto, va in modalità "occupata", non risponde più alle richieste del Broker, esegue la Query Localmente (C1) e invia la richiesta di query (C2) a tutti gli altri Brokers.

L'Agent in modalità "occupata", rimane in attesa dei dati (D) che riceverà dagli Agent delle altre partizioni e riterrà completa la query, solo quando avrà ricevuto tutte le risposte o per timeout; successivamente preparerà i dati da inviare al Client (E) e poi ritornerà in modalità "libero", in attesa che il Broker gli invii un'altra richiesta.

Il processo "scatenato" da una query, coinvolge N Agent e N Broker; per questo motivo, si è deciso di avere tutti i processi sempre attivi per non doverli caricare ad ogni richiesta, in quanto, l'overhead di start del processo, o thread, avrebbe aumentato il tempo di risposta alla query in maniera considerevole (lo spreco temporale, in percentuale, sarebbe altissimo).

Come mostrato dalla Figura 3.6, dopo che il Client invia una query, riceve i dati in questa forma:

• URL (indirizzo HTTP dove risiede l'oggetto trovato) [33]-[36]

• Sommario (una sintesi del contenuto dell'oggetto trovato)

• Rank (il peso, in ordine di rilevanza, assegnato all'oggetto trovato)

• Data (la data di creazione dell'oggetto trovato)

Quindi, per ogni oggetto trovato, si avrà una entry fatta in tale modo. Successivamente il Client dovrà contattare uno o più HTTP server per recuperare le informazioni.

È da precisare che i dati possono risiedere su filesystem del server HTTP oppure in un Dbase. A nostro avviso, il Dbase dovrebbe essere del tipo ad oggetti e non del tipo relazionale, vista la natura disaggregata dei dati memorizzati. L'argomento in questione, dbase ad oggetti e relazionali, essendo vastissimo, ci porterebbe a discutere di problematiche non inerenti alla trattazione di questa tesi.

Figura 3.5 Flusso della Query

Figura 3.6 Flusso del Client

3.7 Vantaggi e Svantaggi del Sistema Distribuito IR

L'obbiettivo principale del nostro lavoro, è quello di rendere il Sistema Distribuito IR, il più veloce possibile. I tempi di risposta ad una qualsiasi query, devono essere brevi, nell'ordine di qualche secondo e, proprio per questo motivo, sono stati creati dei moduli specializzati. Vediamo ora i vantaggi.

L'interfaccia tra il Client e il Sistema, è abbastanza semplice e può essere implementata attraverso un Browser Internet. Attraverso uno script PHP, Perl o una Servlet, il Client può inviare la query; successivamente, lo script visualizzerà i dati ottenuti a seconda dell'esigenza dell'utilizzatore, caso per caso.

Il costo per costruire il nostro Sistema Distribuito IR, può essere contenuto, visto che ormai abbiamo PC con potenze di calcolo elevatissime (CPU 1.5 Ghz, Bus 400 Mhz, GByte di Ram, ecc ...) e costi molto bassi, nell'ordine di pochi milioni di lire. Il vantaggio è evidente: anche costruendo il nostro sistema con decine di PC, il costo sarà comunque irrilevante, rispetto ad un'unica macchina di pari potenza.

La possibilità di avere servizi sempre attivi, è una conquista rilevante. I disservizi causati dai nodi inattivi, interrompono la dinamicità del lavoro; nel nostro sistema, per un qualsiasi nodo in "caduta", ce ne sarà sempre un altro pronto a sostituirlo e questo, senza dover pagare lo scotto di avere nodi in standby. La rendita del nostro sistema, quindi, dal momento che tutti i nodi lavorano senza rimanere in standby, sarà "doppia".

È possibile integrare il dbase distribuito, mentre i Client inviano query. Questo è molto importante su Dbase che hanno necessità di essere dinamici, cioè di indicizzare dati giornalmente; naturalmente, tale operazione è trasparente al Client e non degrada le performances.

Il sistema bilanciato porta a dei tempi di risposta costanti: in qualsiasi situazione, la stessa query impiegherà sempre lo stesso tempo ad essere evasa, questo perché, ogni query viene polverizzata in N nodi a lei dedicati.

Se una partizione degrada nel tempo la velocità delle risposte, possiamo agire in due modi: o potenziando le macchine che costituiscono la partizione, oppure dividendo la partizione in due o più parti. Questo porta a rimanere efficienti non solo inizialmente, ma anche nel tempo. La Scalabilità può essere ottenuta usando le due possibilità e quindi adattando il sistema alle esigenze della situazione, senza perdere di trasparenza.

Un altro vantaggio del sistema, è che nel dbase non risiedono dati, ma solamente i loro "puntatori", (URL). I "puntatori" ci danno la massima versatilità su dove vogliamo far risiedere i dati e, in aggiunta a questo, un minor traffico di rete per il trasferimento dei risultati.

Dopo aver analizzato i lati positivi del nostro sistema, passiamo ai risvolti negativi.

Il Dbase Distribuito è suddiviso in partizioni fisiche, in altre parole, disgiunte tra di loro; quindi avremo, in ogni partizione, K Nodi ognuno con una copia identica del dbase. La situazione sopra esposta, necessaria per aumentare l'efficienza, porta, però, ad avere duplicazioni di dati e quindi spreco di risorse e richiede una certa accortezza nel renderle sempre congruenti tra di loro.

All'Agent che lavora nella modalità "concentratore", pervengono tutti i dati delle altre partizioni; ciò può essere visto come un "collo di bottiglia". I dati che "girano", però, sono solo URL e la quantità di traffico è abbastanza limitata. Il problema è stato gestito in maniera efficiente, considerando anche il fatto che, la velocità delle reti nei sistemi odierni, è molto alta. Facciamo l'esempio di una configurazione con 15 partizioni che inviano 200 entry (una entry occupa 256Byte): l'Agent riceverà circa 750Kb. Per le reti odierne, il tempo necessario a trasferire 750Kb, è nell'ordine di pochi millisecondi e quindi, irrisorio. Il problema del "collo di bottiglia", risolto brillantemente, ci pone, però, un limite fisico: il numero delle partizioni possibili del nostro sistema, non potrà essere superiore a 50/60. Il limite, dovuto alla comunicazione mediante TCP/IP, può essere superato usando protocolli orientati alla comunicazione nelle topologie di reti con un numero di nodi elevato.

Un sistema costituito da un unico Computer, è il sogno di ogni gestore, ma purtroppo non è attuabile. Nel nostro caso, il compromesso ideale è insito nel rapporto tra potenza del Nodo e numero di Nodi; comunque, la gestione informatica di un Sistema Distribuito di N nodi è maggiore che in un sistema centralizzato. Lo svantaggio gestionale è attenuabile rendendo il più possibile identici i Nodi e gestendoli con procedure automatiche, ma questa, forse, è una chimera irraggiungibile.

La molteplicità dei componenti aumenta la probabilità di guasto e di conseguenza anche il tempo di manutenzione e sostituzione delle parti non più funzionanti. Questo inconveniente è incomprimibile, però il sistema rende trasparente al Client i guasti e, di conseguenza, le rotture dei componenti raramente porteranno disagi e disservizi al Client stesso.

Capitolo 4

Architettura del Broker

4.1 Introduzione

La parola stessa, Broker (mediatore commissionario), ci dà un'idea della sua funzione: è un modulo che si interfaccia con il Client aspettando le richieste (in seguito vedremo come) e, successivamente, inoltrandole a chi realmente le dovrà evadere [31][32].

Il modulo³ è stato scritto con il linguaggio C e la sua compilazione è stata fatta con GCC, il compilatore del progetto GNU OpenSource.

È stato scelto il linguaggio C, usando solo istruzioni standard Posix.1 e Svr4, per essere portabile in quasi tutti gli ambienti Unix^TM.

Dopo la compilazione, il modulo diventa un Demone; nel gergo Unix, un demone è un programma (che non ha né standard input, né standard output) che rimane in attesa che qualche evento lo attivi.

Tutto il codice scritto nel suo interno, è orientato ad essere il più efficiente possibile.

Per ottenere ciò, abbiamo usato il più possibile funzioni di sistema e preallocato, in modo statico, tutta la memoria che dovrà essere usata. Le variabili di tutti i cicli, per quanto possibile, sono state definite di tipo "register"; in altre parole, viene usato un registro per contenere il loro valore e non una locazione di memoria. Inoltre, le istruzioni all'interno dei cicli sono state ridotte ai minimi termini e la compilazione è stata ottimizzata in velocità, per avere una maggiore efficienza.

L'unica cernita mirata, si riduce alla scelta della funzione Select rispetto alla "compagna" Pool, in quanto, in ambiente Linux, la prima è più efficiente.

4.2 Disegno del Broker

Il disegno del Broker è suddiviso in cinque parti:

• inizializzazione come demone;

• lettura dei parametri di configurazione;

• ricerca della topologia di rete;

• attesa delle richieste dai Client,Agent o dai Broker;

• rinvio delle richieste ai propri Agent.

Analizziamo in dettaglio queste cinque parti.

4.2.1 Inizializzazione come Demone

La scelta di far operare il Broker in modalità demone, dipende da ragioni di efficienza, stabilità e sicurezza.

Innanzitutto, è necessario associare il demone ad un gruppo di processi; tutti i programmi del sistema fanno parte dello stesso gruppo, cosicchè, quando è necessario, si possono inviare messaggi a tutti i processi che appartengono allo stesso gruppo, con un'unica Syscall (chiamata di sistema).

Successivamente, viene eseguita una syscall per far diventare il Broker leader della sessione, svincolando il demone dal processo che lo ha attivato (normalmente una shell).

Per problemi di sicurezza, viene eseguita per due volte la syscall Fork, disabilitando il segnale di SIGHUP, per evitare che il demone vada in Core e creando, così, un file che contiene l'immagine della memoria del processo, prima di uscire in modo forzato.

Alla fine ci si posiziona in radice, si assegna zero alla variabile "setmask" e si chiudono tutti i descrittori che il processo può aprire.

4.2.2 Lettura dei parametri

Come ogni programma che si rispetti in ambienti Unix, anche il disegno del Broker accetta parametri in ingresso come argomenti. Essendoci molti parametri da fornire, si è scelta la via di un file di configurazione, il quale è assegnato come unico argomento al nostro modulo.

In caso di mancata acquisizione dei parametri, il processo, per default, ricercherà il file di configurazione in "localhost:/etc", con il nome del processo ed estensione "conf"; per esempio, se il processo si chiama "brokera0", il file di configurazione si chiamerà "brokera0.conf".

Il file di configurazione è di tipo testo; ogni riga può contenere un solo parametro e verranno considerate tutte le righe che non iniziano con il "#" o "/n".

La sintassi delle righe che contengono i parametri è: NOME = #VALORE oppure NOME = STRINGA. Le stringhe devono essere racchiuse tra apici e l'ordine di inserimento non ha importanza.

Commentiamo i vari possibili parametri che possono essere configurati.

Il parametro DEBUG è un flag che, se settato ad 1, invia messaggi al SYSLOGD (demone Unix che raccoglie tutti i messaggi dei vari processi e li scrive su diversi file di log; descriveremo in seguito, più in dettaglio, come il modulo si interfaccia con il demone syslogd); se, invece, è settato a zero o se viene omesso, non vengono inviati messaggi di esecuzione al syslogd.

Il parametro HOST_NAME, memorizza il nome della macchina, e nel caso in cui si avessero più schede di rete, indica con quale interfaccia vorremmo comunicare. Se tale parametro viene omesso, eseguiamo una syscall per acquisire l'hostname e di conseguenza la scheda di rete associata.

Il terzo parametro, AGENT_XX, è obbligatorio, di conseguenza, se viene omesso, il programma termina inviando un messaggio di errore attraverso il syslogd (i messaggi di errore vengono invariabilmente scritti attraverso syslogd). Tale parametro identifica quanti Agent sono gestiti dal Broker; per ogni agent è necessaria una riga di questo tipo: AGENTE_XX = "Addr_Ip:Port". Addr_Ip è l'indirizzo Ipv4 [49][50] del relativo agente e la Port è la porta (TCP) che l'agente mette in ascolto per ricevere i messaggi dal proprio Broker.

Facciamo un esempio. Se il nostro broker gestisce quattro agent, divisi su due macchine, occorreranno quattro righe stilate nel seguente modo:

agente_1 = "192.9.168.10:2001"

agente_2 = "192.9.168.11:2001"

agente_3 = "192.9.168.10:2101"

agente_4 = "192.9.168.11:2101"

È da rilevare che gli Agenti sono sempre in coppia (1 con il 2, 3 con il 4), questo per motivi di "fault tollerance", come visto nel capitolo Architettura del Sistema Distribuito IR.

Infine, l'ultimo parametro, anch'esso obbligatorio, rappresenta il pool di Broker che cooperano assieme nella rete distribuita.

Anche in questo caso, per ogni Broker ci serviamo di una riga di questo tipo: BROKER_XX = "Addr_Ip:Port:PortT".

Addr_Ip è l'indirizzo Ipv4 del relativo Broker e la Port è la porta del Broker in ascolto per le richieste dei Client; la seconda porta, PortT, è invece la porta in ascolto per ricevere informazioni, inerenti alla topologia di rete, dagli altri Broker.

Facciamo un esempio. Se il sistema fosse composto da quattro Broker, occorreranno quattro righe per ogni Broker, fatte in questo modo:

broker_0 = "192.9.168.10:4001:3001"

broker_1 = "192.9.168.11:4001:3001"

broker_2 = "192.9.168.12:4001:3001"

broker_3 = "192.9.168.13:4001:3001"

Anche in questo caso, come per gli Agent, i Broker sono sempre in coppia.

4.2.3 Ricerca Topologia di Rete

Per il modulo Ricerca Topologia di Rete, progettato per lavorare in modo distribuito, è indispensabile per sapere dinamicamente come è realizzata la rete e quali nodi sono attivi. Lo scambio dei messaggi, tra i vari nodi della rete, avviene, ovviamente, tramite il protocollo IP, mentre, nella fase di analisi, si possono prevedere vie differenti, mediante trasporti di tipo TCP o UDP; in quest'ultimo caso, è possibile usare modalità Multicasting o Broadcasting [68].

Abbiamo scelto di usare TCP, in quanto questo protocollo comporta un trasporto di tipo connesso, tralasciando, invece, UDP che è di tipo non connesso. Il programma, per problemi di performance, non può controllare se il messaggio che ha inviato è arrivato a destinazione e non può ritrasmetterlo nel caso il messaggio stesso fosse andato perso.

L'algoritmo in argomento, è molto semplice ma, nello stesso tempo, efficace per il nostro utilizzo. Dalla lettura dei parametri, abbiamo tante coppie di Broker, ognuna delle quali gestisce un gruppo di agent, i quali, a loro volta, gestiscono una partizione del dbase distribuito. L'obiettivo da raggiungere, consiste nel selezionare un Broker attivo per gruppo e creare quindi una lista di Broker, ognuno dei quali gestisce una partizione distinta del dbase distribuito.

La ricerca viene attivata, in principio, nel momento in cui il demone viene eseguito, e successivamente dopo che per un tempo prefissato il Broker non ha richieste dai Client.

La scelta di un Broker al posto di un altro, nello stesso gruppo, viene fatta con la regola RR (Round Robin o Time-Sharing), scegliendoli distintamente, uno dopo l'altro. A nostro parere, questa regola offre un maggiore bilanciamento di carico in modo statistico, con un tempo computazionale "nullo". La scelta, ovviamente, avviene solo tra i Broker attivi. Nella sventurata situazione che nessuno dei Broker fosse attivo, viene segnalato, attraverso syslogd, che la relativa partizione è "down".

Riassumendo: la Ricerca Topologia di Rete ha come svantaggio una maggiore elaborazione, ma offre, a nostro avviso, un bilanciamento ottimale di carico statistico e una più affidabile connessione a tutte le partizione del dbase distribuito.

4.2.4 Richieste Client Broker

Il programma rimane in attesa che i Client/Agent o i Broker inviino delle richieste: è questa la sua funzione principale. Per fare ciò, abbiamo usato la syscall Select mettendola in ascolto (nel gergo informatico, in Listen), su due porte, rispettivamente, la porta per i Client e la porta per i Broker.

Il numero di porta, viene assegnato in fase di lettura dei parametri visti precedentemente.

La scelta di usare due porte anzichè una, situazione "identica" a livello computazionale, ci permette di risparmiare i controlli necessari a suddividere i messaggi del Client da quelli del Broker; sarà il Kernel, infatti, il responsabile dello smistamento.

Suddividiamo il loop, sulla syscall Select, in quattro situazioni:

• A) timeout della Select;

• B) richiesta di connessione da parte di un Client/Agent;

• C) richiesta di connessione da parte di un Broker;

• D) errore in Select.

Nel caso A, timeout della select, abbiamo una mancanza di richieste protratta per lungo tempo; di conseguenza, attendendoci una situazione analoga nei secondi successivi, si attiva la ricerca topologica e si ricrea la lista Broker-partizione. Se un Client o un Broker richiede una connessione, avrà un ritardo di risposta pari al tempo di ricerca topologica, e quindi lineare rispetto al numero di partizioni.

Nel caso B, viene attivata la connessione con il Client/Agent e messa in ascolto, attraverso la select, anche la nuova connessione per ricevere successivamente i dati.

Nel caso C, viene attivata la connessione con il Broker e messa in ascolto, attraverso la select, anche la nuova connessione che riceverà la conferma che, il Broker stesso, è attivo.

Nel caso D, si presenta una situazione anomala, ma comunque gestibile. Per poter riprendere il normale funzionamento, è necessario un restart della syscall select, segnalato attraverso syslogd.

4.2.5 Invio Dati all'Agent

Rimaniamo nell'argomento "loop" della select. Una volta connesso, il Client inizierà a trasferire la sua query: i dati inviati, creeranno una struttura che comprenderà:

• i parametri per scegliere il tipo di query;

• i termini della query;

• l'indirizzo al quale dovrà essere spedito il risultato della query;

• la lista dei Broker che gestiscono le altre partizioni.

La domanda che ci si pone, è la seguente: avendo per ogni Broker diversi Agent, quale di questi ultimi verrà scelto?

Anche in questo caso, la selezione è di tipo RR (Round Robin o Time-Sharing), non per motivi di bilanciamento di carico, ma per riuscire a gestire molte query contemporanee, senza trovare l'Agent occupato. Se tutti gli Agent saranno occupati, ciò verrà segnalato attraverso syslogd "Risorse Occupate" e la query non verrà effettuata.

4.3 Descrizione Strutture

Esistono quattro strutture principali:

• la struttura ricevuta dal Client;

• la struttura inviata all'Agent;

• la struttura che memorizza la topologia di rete;

• la struttura che memorizza i parametri di configurazione.

Di seguito, vediamo le tabelle che illustrano le strutture principali.

4.4 Algoritmo del Broker

È venuto il momento di descrivere l'algoritmo del broker; i punti visti precedentemente sono utili per capire il flusso che ora descriveremo.

Il modulo inizia con la memorizzazione del nome del programma in una variabile "progname"; inoltre, esegue una funzione "discard_stupid_environment", che elimina variabili d'ambiente che non servono e occupano spazio prezioso (questo vale specialmente in ambiente Linux). L'algoritmo continua leggendo i parametri dell'ambiente, e prosegue solamente se, i parametri stessi, sono corretti.

Dopo questa prima inizializzazione, avviene la trasformazione in un demone, usando la funzione "daemon_init". A questo punto, il demone vive di vita propria, svincolato dalla shell che lo ha lanciato.

Non avendo né standard input, né standard output, utilizziamo il demone syslogd, per scrivere i messaggi di log (sia errori che messaggi di debug); ciò avviene sfruttando la funzione "openlog" e usando una "facility" riservata per usi locali. Il "daemon_init", scrive immediatamente, attraverso syslogd, lo start del processo ed esegue la funzione "logpid" che scrive, in un file, il numero (PID) del processo.

A questo punto, il modulo esegue la funzione "readconfigfile", la quale memorizza, in strutture appropriate, tutti i parametri che serviranno in seguito. Tali parametri sono stati descritti nel paragrafo 4.3.

Dopo tutte queste operazioni, si entra nella funzione "mainloop", che tiene il demone in loop; essa è composta da un ciclo infinito che racchiude due funzioni, la prima delle quali, "req2snd", verrà descritta successivamente, mentre la seconda, "sleep", ci eviterà che, in caso di errore, la CPU si blocchi.

La funzione "req2snd" (diminutivo di "richieste da trasmettere"), che rappresenta il nocciolo del demone assieme alla funzione "scelta_broker", che verrà chiamata nel suo interno, comincia con una serie di inizializzazioni di variabili e strutture, che verranno usate successivamente. La funzione, poi, si pone in ascolto (listen) su due porte, la prima per ricevere richieste dal Client o dall'Agent, trattandoli in maniera differente, la seconda per ricevere le richieste di aggiornamento topologico dagli altri Broker.

Dopo aver messo in listen queste due porte, eseguiamo la funzione "scelte_broker" per creare la lista che associa ad ogni partizione un Broker che la gestisce; la funzione, dalla lettura dei parametri, memorizza, per ogni partizione, i Broker che la gestiscono, e a questo punto, si attua la scelta sul Broker da considerare. Si opererà in modo alternato, testando, con un tentativo di connect se quello da noi scelto è attivo; nel caso che nessuno dei Broker sia attivo, segnaliamo attraverso syslogd (se siamo in debug), che la partizione "k" è down. Entriamo, a questo punto, in un loop "infinito" e ci mettiamo in attesa di connessioni usando la syscall "SELECT".

Dobbiamo far notare che, prima di entrare in select, i segnali SIGHUP e SIGALARM sono attivati, mentre quando gestiamo gli eventi, gli stessi segnali vengono bloccati: in questo modo non si perdono dati. Le funzioni che permettono l'attivazione e il blocco dei segnali sighup e sigalarm, sono "sig_unblock" e "sig_block". Esistono anche altre funzioni di supporto per la gestione degli eventi che tralasceremo per non complicare la descrizione.

La syscall select uscirà dal suo loop se appaiono i seguenti eventi, che verranno gestiti caso per caso:

• Il primo evento è l"errore generico"; in questo caso si resettano tutte le variabili e si chiudono tutti i descrittori aperti ritornando, con lo stato uguale a "-1", al mainloop. Tale reinizializzazione del programma, viene segnalata come errore attraverso syslogd.

• Il secondo evento è il "timeout delle select"; in questo caso, per precauzione, si chiudono tutti i descrittori e si azzerano le aree dati. Dal momento che nessuno sta richiedendo dati, si riaggiorna la lista che associa ad ogni partizione il Broker che la gestisce, usando sempre la stessa funzione "scelta_broker".

• Il terzo evento è la "richiesta di connessione dal Client o dall'Agent"; la richiesta viene accettata e si memorizzano i descrittori in aree predefinite.

• Il quarto evento è la "richiesta di connessione dal Broker"; come nel precedente evento, la richiesta viene accettata e si memorizzano i descrittori in aree predefinite.

• Il quinto evento lo definiamo "dati da leggere dalle code del kernel"; essi possono arrivare da un Broker, da un Agent o da un Client e verranno memorizzati in aree distinte.

Alla chiusura da parte dell'Agent o del Client, il Broker sceglie, con il metodo RR (Round Robin o Time-Sharing), l'Agent che deve gestire la richiesta di query, inviando la struttura che la memorizza.

Gli eventi sono stati elencati nell'ordine sopra esposto, per comodità, dato che, essendo il kernel ad amministrare tutto, la sequenza degli eventi potrebbe cambiare.

4.4.1 Diagramma di Flusso

Lettura argomenti

Trasformazione in Demone

Apertura con Syslogd

Scrittura PID su File

Lettura file configurazione

MainLoop

Req2Snd

Init Parametri

Listen porta Broker

Listen Porta Agent / Client

Scelta_Broker

Loop

Signal_UnBlock

Select

Signal_Block

Errore Select

Timeout Select

New Connect Client / Agent

New Connect Broker

Check all Client / Agent for READ

Check all Broker for READ

Check all Client / Agent for WRITE

Goto Loop

Sleep

Goto MainLoop

CAPITOLO 5

Architettura dell'Agent

5.1 Introduzione

L'Agent, svolgendo il lavoro più oneroso, è il più importante tra tutti i componenti del Sistema Distribuito.

Il modulo⁴ è scritto in linguaggio C ed è compilato, ottimizzando la velocità, con GCC, il compilatore del progetto GNU OpenSource. Le funzioni usate nel modulo sono standard Posix.1 e Svr4.

Il modulo Agent è scritto per essere eseguito come Demone e tutte le funzioni nel suo interno sono orientate alla velocità, penalizzando, a volte, l'occupazione di memoria.

Il funzionamento dell'Agent è semplice: esso riceve una query dal proprio Broker, recupera i dati della sua partizione e demanda agli altri Broker di recuperare i dati delle proprie partizioni, dopo di che, attende i risultati che arriveranno dagli altri Agent, ordinati secondo l'ordine di Ranking. I dati, infine, vengono inviati al Client [51] che aveva fatto la richiesta. Vedremo in seguito, più in dettaglio, questa modalità di funzionamento.

5.2 Disegno dell'Agent

Il disegno dell'Agent è suddiviso in sei parti:

• inizializzazione come demone;

• lettura dei parametri;

• attesa di una richiesta dal Broker;

• esecuzione della query distribuita;

• aggregazione dei dati ricevuti;

• invio al Client o all'Agent che aveva richiesto i dati.

L'Agent lavora nelle due seguenti modalità, "Collettore" e "Locale". Nella modalità "Collettore", l'Agent riceve dati da altri Agent, i quali lavoreranno nella modalità Locale; le risposte delle query distribuite, verranno inviate al Client. Nella modalità Locale, l'Agent esegue la query Locale e la invia all'Agent "collettore".

Per ogni query ci saranno N-1 Agent locali e un Agent Collettore (N è il numero delle partizioni del Dbase Distribuito).

Analizziamo in dettaglio questi sei punti.

5.2.1 Inizializzazione come Demone

La scelta di far operare il Agent in modalità demone, dipende da ragioni di efficienza, stabilità e sicurezza.

Innanzitutto, si associa il demone ad un gruppo di processi; tutti i programmi del sistema fanno parte dello stesso gruppo, cosicchè, quando è necessario, è possibile inviare messaggi a tutti i processi che appartengono al medesimo gruppo, con un'unica syscall (chiamata di sistema). Successivamente, viene eseguita una syscall per far diventare l'Agent leader della sessione, svincolandolo dal processo che lo ha attivato (normalmente una shell).

La syscall Fork, che per problemi di sicurezza viene eseguita due volte, disabilita il segnale di SIGHUP, per evitare che il demone vada in Core, e crea, nel contempo, un file che contiene l'immagine della memoria del processo, prima di uscire in modo forzato.

Infine, ci si posiziona in root, si assegna zero alla variabile "setmask" e vengono chiusi tutti i descrittori che il processo può aprire.

5.2.2 Lettura dei parametri

L'architettura dell'Agent, come ogni programma che si rispetti in ambienti UNIX, accetta parametri in ingresso come argomenti. Essendo molti i parametri da passare, si è scelta la via di un file di configurazione, il quale è passato come unico argomento al nostro modulo. Se non viene passato nulla, il processo ricercherà, per default, il file di configurazione in "localhost:/etc", con il nome del processo ed estensione conf. Ad esempio: se il processo si chiama AGENTA1, il file di configurazione si chiamerà AGENTA1.CONF.

Il file di configurazione, di tipo testo, potrà contenere un solo parametro per riga; inoltre, verranno considerate tutte le righe che non iniziano con il '#' o "/n".

La sintassi delle righe che contengono i parametri, sarà la seguente: NOME = #VALORE oppure NOME = STRINGA. L'ordine di inserimento delle stringhe, che devono essere racchiuse tra apici, non ha importanza.

Descriviamo ora, brevemente, i vari possibili parametri che possono essere configurati.

Il parametro DEBUG è un flag che, se settato ad 1, invia messaggi al syslogd (demone Unix che raccoglie tutti i messaggi dei vari processi e li scrive su diversi file di log; più avanti, descriveremo in dettaglio, come il modulo si interfaccia con il demone syslogd); se è settato a zero o se viene omesso, non invia messaggi di esecuzione al syslogd.

Il parametro HOST_NAME, memorizza il nome della macchina e l'interfaccia con la quale vorremmo comunicare, nel caso in cui si avessero più schede di rete. Se il parametro viene omesso, eseguiamo una syscall per acquisire l'hostname e di conseguenza la scheda di rete associata.

Il parametro COLLECTION_PATH, essendo obbligatorio, comporta, in caso di omissione, la scrittura di un messaggio di errore, attraverso syslogd, da parte del programma, che ne spieghi il motivo. Il parametro COLLECTION_PATH, identifica la posizione nel VFS (Virtual File System), dove risiedono i file del Dbase associato al nostro Agent.

Il parametro AGENT_PORT, è la porta tcp con cui l'Agent rimane in ascolto per ricevere i dati delle query distribuite che gli pervengono dagli altri Agent. AGENT_PORT non è obbligatorio e il suo default è 3001.

Il parametro BROKER_PORT, è la porta tcp con la quale l'Agent rimane in ascolto per ricevere la richiesta di query da parte del proprio Broker. Il parametro non è obbligatorio e il suo default è 2001.

Il parametro MAXOBJ, è il numero massimo di oggetti che l'Agent può estrarre con una query; se il Dbase avesse, per quella query, un numero di oggetti superiore al parametro, verrebbero considerati solo i |MAXOBJ| con Ranking maggiore. Facciamo un esempio: se la query dà un risultato di 1000 oggetti e il parametro |MAXOBJ| = 100, verranno considerati i 100 oggetti con ranking maggiore.

5.2.3 Attesa Richiesta dal Broker

Dopa la fase di inizializzazione, il modulo rimane inattivo fino al momento in cui perviene una richiesta di query da parte del Broker corrispondente. Quando ciò avviene, inizia tutto il meccanismo di recupero dei dati; il modulo rimane in attesa attraverso una Select messa in ascolto sulla porta tcp, BROKER_PORT, fino a quando il proprio Broker non invia la richiesta di query.

Il numero di porta viene assegnato in fase di lettura dei parametri visti in precedenza.

Suddividiamo il loop della syscall Select in tre punti:

• A)Timeout della Select

• B) Richiesta di connessione

• C) Errore della Select

Il primo caso si verifica quando una mancanza di richieste si protrae per molto tempo: la select andrà in timeout. Di conseguenza, vengono chiuse le eventuali socket rimaste appese e si ritorna nel loop della select. Mentre si eseguono tali istruzioni, vengono disattivati i segnali che impediscono al kernel di inviare dati.

Nel caso B, viene attivata la connessione con il Broker e messa in ascolto, attraverso la stessa select, anche la nuova connessione, per ricevere successivamente i dati che verranno memorizzati in una struttura AGENTI (struttura che verrà descritta nel paragrafo Descrizione Strutture, di questo stesso capitolo), che poi servirà per la query distribuita.

Una volta stabilita una connessione con il Broker, tutti gli altri tentativi di connessione, nel frangente di tempo in cui l'Agent riceve i dati, vengono rifiutati; questo perché, ogni Agent gestisce una sola richiesta per volta. Abbiamo già visto, nel capitolo Archittettura del Sistema Distribuito IR, che questa situazione si può evitare.

Il Caso C rappresenta una situazione anomala, che comunque viene gestita; per poter riprendere il normale funzionamento, l'Agent necessita di un "restart" che verrà segnalato attraverso syslogd.

5.2.4 Esecuzione Query Distribuita

L'Esecuzione Query Distribuita è la parte centrale dell'Agent; essendo la più complicata da spiegare, la suddividiamo in tre punti.

• A) Query Locale

• B) Connessione con i Broker

• C) Loop con la select

La query locale, il primo punto in esame, è molto semplice: se nella struttura AGENTI viene specificata l'esecuzione di una query locale, viene eseguito il modulo Query_DB, il quale memorizza su di una struttura statica DATI_OUT, il risultato della query stessa (il modulo Query_DB è molto complesso e per questo gli è stato dedicato un capitolo a sè stante, Archittettura del Dbase FullText). Come query locale, si intende considerare la collezione localizzata in COLLECTION_PATH. La struttura DATI_OUT è stata definita statica per evitare la syscall Malloc, che penalizza il tempo di esecuzione.

Nel secondo punto il modulo esegue una connessione con tutti i Broker che gestiscono le altre partizioni del Dbase Distribuito. La lista dei Broker è contenuta nella struttura AGENTI.

Se per qualche motivo un Broker non risponde, il modulo ritenta la connessione dopo 500 ms; nel caso che, dopo il nuovo tentativo, il Broker sia ancora "down", il modulo continuerà con gli altri Broker e, al termine, segnalerà al Client che le risposte non sono complete, utilizzando la variabile Daticompleti.

Nel terzo punto, attraverso la Select, rimaniamo in attesa di poter mandare la query ai Broker, e di ricevere le risposte dagli Agent selezionati dai Broker stessi. Sfruttando in questo modo la select, possiamo avere il massimo dell'efficienza sulla risposta delle nostre query distribuite, in quanto, sarà il Kernel a gestire il traffico in uscita e in entrata. L'Agent sarà avvisato dal Kernel nel caso in cui ci siano dati in arrivo ovvero ci sia la possibilità di inviare delle risposte; ovviamente, in questo modo possiamo ricevere risposte ancor prima di avere inviato tutte le richieste, ma questo per noi non è un problema.

Un'importante notazione: in ambienti OpenSource, come Linux, possiamo aumentare le performances, variando la dimensione, il numero delle code ed altri parametri, semplicemente ricompilando il modulo IPV4. La documentazione bibliografica, a questo proposito, è vastissima.

Il loop della select terminerà all'arrivo di tutti i dati o per timeout; i dati verranno memorizzati nella struttura DATI_OUT.

5.2.5 Aggregazione dei Dati

Il modulo Aggregazioni dei Dati non necessita di spiegazioni articolate; i dati memorizzati in DATI_OUT, vengono riordinati in modo da avere N code ordinate secondo un "Ranking Distribuito".

Inizialmente, per ogni partizione abbiamo una coda ordinata secondo un "Ranking Locale"; successivamente, vengono ricalcolati alcuni parametri e variato, per ogni documento, il nuovo valore di Ranking, e infine viene rifatto l'ordinamento per ogni coda, in moda da avere le N code ordinate secondo un nuovo Ranking, che tenga conto del Dbase completo e non solo della parte locale (per l'algoritmo di Ranking usato, vedere il capitolo Architettura del Dbase FullText).

Questo tipo di aggregazione, avviene solo quando l'Agent deve spedire i dati al Client e non quando deve spedire i dati ad un altro Agent, quindi, nell'ultimo stadio della nostra Query Distribuita, un attimo prima di inviare la richiesta al Client.

5.2.6 Invio Dati al Client o all'Agent

In questo modulo, possiamo distinguere due casi:

• A) Invio dati all'Agent

• B) Invio dati al Client

Nel caso A, il Broker richiede di eseguire una semplice query locale e di inviarla ad un Agent, il quale sarà il collettore di tutte le altre richieste.

La nostra struttura DATI_OUT, conterrà solo una coda, ordinata per Ranking in modo decrescente, la quale verra inviata all'Agent così com'è.

Nel caso B, il Broker richiede l'esecuzione di una query distribuita, utilizzando gli altri Broker.

La nostra struttura DATI_OUT, conterrà tante code quante sono le partizioni del Dbase, le quali verranno inviate al Client che aveva fatto la richiesta.

L'algoritmo di invio è diverso dal precedente caso A, in quanto non abbiamo solo una coda, ma ne abbiamo N.

L'algoritmo, di complessità lineare, è un classico: date N code ordinate, crearne l'unione, anch'essa ordinata.

5.3 Descrizione Strutture

Esistono cinque strutture principali:

• struttura ricevuta dal Broker;

• struttura inviata ai Broker;

• struttura ricevuta dalla Query Dbase Locale;

• struttura ricevuta dagli altri Agent;

• struttura inviata al Client.

Di seguito, vediamo le tabelle che illustrano le strutture principali.

5.4 Algoritmo dell'Agent

È venuto il momento di descrivere l'algoritmo dell'Agent; i punti visti precedentemente sono utili per capire il flusso che verrà descritto.

Il modulo inizia con la memorizzazione del nome del programma, in una variabile "progname", e poi esegue una funzione, "discard_stupid_environment", che elimina variabili d'ambiente che non servono e occupano memoria preziosa (questo vale specialmente in ambiente Linux). L'algoritmo continua leggendo i parametri passati dall'ambiente e prosegue solo se i parametri stessi sono corretti.

Dopo questa prima inizializzazione, avviene la trasformazione in un demone usando la funzione "daemon_init". A questo punto, il demone vive di vita propria, svincolato dalla shell che lo ha lanciato.

Non avendo né standard input, né standard output, il modulo utilizza il demone syslogd per scrivere i messaggi di log (sia errori che messaggi di debug) e questo avviene usando la funzione "openlog" tramite una "facility" riservata per usi locali, "LOG_LOCAL0".

Il modulo scrive, attraverso syslogd, lo start del processo ed esegue la funzione "logpid" che scrive in un file il numero (PID) del processo. Dopo queste operazioni, il modulo esegue la funzione "readconfigfile", la quale memorizza in strutture appropriate tutti i parametri (che sono stati descritti nel paragrafo 5.2.2), che serviranno in seguito.

Il processo entra, poi, nella funzione "mainloop", che tiene il demone in loop. "Mainloop" è una funzione composta da un ciclo infinito che racchiude le seguenti quattro istruzioni:

• req_broker, l'istruzione che attende le richieste dal broker;

• query_dist, l'istruzione che recupera i dati dal Dbase Distribuito;

• aggreg_data, l'istruzione che aggrega i dati;

• snd_client, l'istruzione che invia la risposta al client.

Prima delle quattro istruzioni viste sopra, la variabile "daticompleti" viene settata a zero, ad indicare che tutte le partizioni vengono coinvolte nella query; precauzionalmente, viene inserita l'istruzione "sleep", per assicurare che un loop stretto non porti in saturazione la CPU.

Vediamo in dettaglio, punto per punto, le quattro istruzioni della "mainloop".

Per la prima procedura, "req_broker", viene inizializzata e riconfigurata la gestione dei segnali adatta per tale Agent; successivamente, vengono inizializzate alcune altre strutture, la più importante delle quali, "agentdb", memorizzerà la query passata dal Broker, che verrà usata in seguito. Fatto ciò, l'istruzione si mette in ascolto sulla porta preposta per ricevere la query dal Broker e rimane in attesa fino al momento in cui perviene una richiesta; quando questa arriva, la riceve e nel frattempo non permette altre richieste.

Una volta ricevuto tutto il messaggio, "req_broker" lo considera completo solo se il carattere di start e di stop coincidono e, se il test è affermativo, esce da questa funzione e passa alla successiva, altrimenti ritorna in ascolto e aspetta un'altra richiesta.

La funzione successiva, "query_dist", come evidenziato dal nome stesso, ha il compito di eseguire la query in tutto il dbase distribuito.

Nella struttura "agentdb", oltre alla query al dbase distribuito, viene memorizzata la topologia dei Broker che gestiscono le altre partizioni.

Inizialmente, la funzione "query_dist" può lavorare in due modalità: la prima esegue solo la query locale, la seconda, oltre ad eseguire la query locale, richiede agli altri Broker, che gestiscono le altre partizioni del dbase, di eseguire tale query.

La prima modalità è semplice, in quanto "query_dist" richiama la funzione "query_db", la quale ricerca i dati nella partizione locale e li memorizza in una struttura "dati_out" e poi termina.

Nella seconda modalità, oltre ad eseguire la "query_db", la funzione in esame si predispone ad inviare le richieste e a ricevere le risposte, usando sempre la syscall select; cerchiamo di spiegare come questo avviene.

La select è in ascolto sulla porta predisposta per ricevere le risposte dagli Agent e per inviare le richieste ai Broker; ciò significa che la select in ascolto ha dei descrittori di "socket" in lettura, per le richieste ricevute dagli Agent e descrittori di "socket" in scrittura, per le richieste inviate ai Broker.

Questo susseguirsi di letture e scritture da parte degli Agent e dei Broker, rende il più efficiente possibile la richiesta distribuita. È da notare che la sequenzialità non esiste, in quanto potremmo ricevere risposte dagli Agent ancor prima di aver completato tutte le richieste ai Broker. Le informazioni non possono essere perse, in quanto precedentemente sono stati riprogrammati i segnali, fermo restando che il Kernel riesca a gestire, in modo corretto, le code associate alle socket.

La struttura inviata ai Broker è "agentdbsend"; essa è identica alla struttura "agentdb", ma la destinazione della risposta, in questo caso, è verso l'Agent e la query deve essere fatta solo localmente.

La struttura che memorizza i dati ricevuti dagli Agent, è sempre "dati_out".

Tutta questa fase di query distribuita, termina in due modi: nel primo, che è il modo corretto, arrivano i dati da tutte le partizioni (il numero di chiusure dei descrittori di input è pari al numero di chiusure dei descrittori di output), mentre il secondo modo, non corretto, finisce per timeout. In quest'ultimo caso, assegniamo la variabile "daticompleti" a 1, che indicherà tale situazione.

In definitiva, avremo nella struttura "dati_out[I]", tutte le risposte: con I=0 avremo quella locale, mentre se I>0 avremo le risposte delle altre partizioni.

La funzione successiva, "aggreg_data", non ancora completamente implementata, ha il compito di riaggregare i dati tenendo conto della loro globalità distribuita e di riordinare le N code della struttura "dati_out", secondo un ranking distribuito.

L'ultima istruzione, "snd_client", invia i dati ai richiedenti, il Client o l'Agent "concentratore". Inizialmente, la funzione si connette alla sorgente destinazione, che viene specificata dalla struttura "agentdb"; se la connessione non riesce, la funzione riprova dopo un tempo prefissato e se il tentativo fallisce nuovamente, termina con una segnalazione di errore tramite il syslogd.

Le N code mantenute nella struttura "dati_out[I]", sono ordinate con un "Ranking Distribuito"; in questo modo l'algoritmo diventa il Merge delle N code ed invia a destinazione un'unica coda ordinata, chiude i descrittori aperti e termina la funzione.

Una volta completata questa ultima funzione, si rientra nel "mainloop", dopo di che viene resettata la variabile "daticompleti" a zero, viene eseguita la funzione "sleep", per ridurre schedulazioni troppo strette e si rientra nella funzione "req_broker", per attendere una nuova richiesta da parte del Broker.

5.4.1 Diagramma dell'Algoritmo

Lettura argomenti

Trasformazione in Demone

Apertura con Syslogd

Scrittura PID su File

Lettura file configurazione

MainLoop

daticompleti=0

Sleep

Req_Broker

Init Parametri

Listen porta Broker

Loop

Signal UnBlock

Select

Signal_Block

Errore Select: EXIT

Timeout Select: Reset; CONTINUE

New Connect Broker

Check Broker for READ

Close Broker: EXIT LOOP

Goto Loop

Query_Dist

Query_Locale

Init Parametri

Connect All Broker

Listen porta Agent

Loop

Signal_UnBlock

Select

Signal_Block

Errore Select: EXIT

Timeout Select: daticompleti=1; EXIT LOOP

New Connect Client

Check All Agent for READ

Check All Broker for WRITE

if (#Close_Broker == #Close_Agent) EXIT LOOP

goto Loop

Aggreg_Data

Ricalcolo Ranking

Snd_Client

Init Parametri

Connect to Client

Merge and Send to Client

Goto MainLoop

CAPITOLO 6

Architettura del Dbase FullText

6.1 Introduzione

Il disegno del seguente Dbase FullText, è stato realizzato analizzando varie architetture preesistenti⁵, ed estraendo da esse le migliori funzionalità; inoltre, sono state aggiunte delle estensioni, a nostro avviso indispensabili, come l'aggiunta di un documento su di una preesistente collezione di oggetti, le modifiche nell'algoritmo di ranking, la compressione delle strutture e la predisposizione ad essere utilizzato in ambiente distribuito.

Il Dbase FullText è, essenzialmente, un indicizzatore di testo, ma come vedremo in seguito, può gestire qualsiasi tipologia di oggetto, utilizzando dei filtri appropriati.

Le principali caratteristiche del Dbase Full Text possono essere raggruppate nei seguenti punti:

• scansione ricorsiva dei documenti;

• utilizzo dei filtri per poter indicizzare qualsiasi tipo di oggetto;

• la parola come elemento minimale, con la possibilità di usare lo "stemming";

• struttura disegnata per grandi collezioni di oggetti, prestando attenzione alla compressione degli indici, all'ottimizzazione nell'allocazione di memoria e all'I/O su disco;

• supporto delle funzioni di OR ed AND nella query, con la possibilità di utilizzare il termine esatto o parziale;

• utilizzo del Ranking per avere risultati in ordine di importanza, tramite un algoritmo adattato per essere sfruttato anche in ambiente distribuito;

• utilizzo delle tecniche statiche e dinamiche per eliminare le "stopwords";

• software ottimizzato per l'ambiente Linux;

• software con archittettura modulare di facile ampliamento;

• politica di marketing Free Software, mediante distribuzione sotto licenza GPL.

6.2 Disegno del Dbase

Il disegno del Dbase Full Text, permette di indicizzare una struttura dati in modo ricorsivo, per cui, usando link e dischi condivisi, i dati possono essere distribuiti nella rete. Ogni file è considerato un oggetto e la sua estensione, basandosi sul Mime [37][38], ne identifica il tipo. Per ogni tipo di oggetto, esiste un relativo filtro che estrae le parole che verranno indicizzate; inoltre, vengono memorizzate determinate caratteristiche quali la sua locazione (tramite un indirizzo URI [35]), il titolo, l'autore, un riassunto, la dimensione, la data di creazione e altre ancora.

L'estrazione delle caratteristiche sopra citate, è possibile solo per i file di tipo XML o HTML [33][34]; in caso contrario, devono essere gestite dal filtro. Il programma costruttore estrae i relativi campi per HTML, sfruttando dei tag fissi e, per quanto riguarda XML, sfruttando un DTD [33] prefissato. Per effettuare questa analisi, nel testo è stata integrata una libreria standard Libxml [53] del consorzio W3C.

Una volta estratto il flusso di parole da indicizzare, si eliminano alcuni termini secondo i criteri di "stemming" e di "stopword" [78][27] dinamiche o statiche.

Ogni parola viene inserita nell'indice implementato con un AVL; per limitare i seek su disco, partizioni AVL vengono memorizzate in forma compressa (Bzip2 [54]).

Ogni nodo dell'AVL ha l'offset al file che contiene la lista dei documenti associati ad una determinata parola. Anche questa struttura, detta comunemente Posting, è memorizzata in forma compressa. Gli algoritmi di compressione, usati per tale struttura, sono: Unary Encoding, Gamma Encoding, Local Bernoulli tramite Golomb Coding [1].

Per i file di tipo XML e HTML, è possibile una suddivisione interna in paragrafi usando i tag, per cui le parole indicizzate saranno associate ai paragrafi che a loro volta saranno associati ai file.

In tutta la fase di costruzione del Dbase, vengono memorizzari dei valori che permetteranno di calcolare il Ranking, il cui algoritmo è abbastanza complesso e verrà successivamente spiegato.

6.3 Struttura dei File

L'implementazione è strutturata in diversi file che memorizzano tutte le informazioni. Si fa notare, che se un singolo file ragruppa N documenti, verranno creati N records nei file DBASE.DOCS e DBASE.DOCPTRS, tutti i records faranno riferimento ad un unico record nel file DBASE.FILES.

Ogni documento è associato ad un numero sequenziale che inizia da zero.

Per ogni documento viene creato un record in DBASE.DOCPTRS; questo record contiene il puntatore al file DBASE.DOCS o al file DBASE.FILES e il peso del documento.

Ogni documento può essere un file, o parte di un file: se il documento è un file, si crea un record in DBASE.DOCPTRS e uno in DBASE.FILES, i quali si collegano tramite un puntatore; se il documento, invece, è parte di un file, si creano dei record in DBASE.DOCPTRS e in DBASE.DOCS per ogni parte del file. Ogni record di DBASE.DOCPTRS è collegato con un puntatore al relativo record in DBASE.DOCS; inoltre, viene creato un record in DBASE.FILES per ogni file.

Ogni record in DBASE.DOCS ha un puntatore al record in DBASE.FILES.

Struttura di un record del file DBASE.BTREE

I termini sono memorizzati in ordine alfabetico, insieme alla frequenza (numero di documenti in cui il termine ricorre) e ad un offset all'interno del file DBASE.POSTINGS.

Ogni nodo nel file DBASE.BTREE (un file con una struttura ad albero), contiene una struttura di entry; una entry è formata da una chiave, un valore e un contatore associato al documento. Il termine è la chiave, il valore è l'offset nel file DBASE.POSTINGS, il contatore è la frequenza del termine nel documento.

6.4 Moduli: Builder e Retrieve

L'implementazione del dbase è costituita da due moduli principali, il costruttore del dbase, Builder e il modulo che permette la sua interrogazione, Retrieve.

Builder è un programma a sé stante che costruisce il Dbase FullText.

I parametri che esso accetta come argomenti, sono i seguenti:

• Il path dove verranno creati i file del Dbase.

• La root path che verrà associata ai file che verranno indicizzati.

• La memoria massima che può usare il programma.

• L'abilitazione ad usare lo stemming e le stopwords.

• Le directory da indicizzare.

• Il topo di compressione da utilizzare.

Prima di fornire maggiori dettagli sul modulo di costruzione del dbase, spieghiamo in dettaglio il funzionamento di un suo sottomodulo, il Filtro.

L'implementazione del filtro è specificata nel file DBASE.CONFIG.

Il filtro sarà composto da una riga per ogni estensione che vogliamo gestire. La sintassi è la seguente: {ext}.filtro={tipo};{comando}, dove {ext} è l'estensione di un particolare tipo di documento, {comando} è il programma per convertire questo tipo di documento, {tipo} può essere XML, TEXT o PIPE.

Se il tipo è XML o TEXT, la funzione di filtro termina passando al Builder il flusso di dati; se il formato del documento è XML, potranno essere estratte le caratteristiche del documento; se il tipo è PIPE, viene riapplicato il filtro. Il filtro in esecuzione, legge determinate variabili nell'ambiente creato dal Builder:

Esempio di file DBASE.CONFIG

# File di configurazione

txt.gz.filter=xml;gunzip -c $DBASE_FILENAME | txt2xml.awk

gz.filter=pipe;gunzip -c

xml.filter=xml;cat

txt.filter=xml;txt2xml.awk

doc.filter=text;catdoc

L'ordine di riga è prioritario. La prima riga indica che se un file ha come estensione txt.gz, viene applicato il filtro (gunzip -c $DBASE_FILENAME | txt2xml.awk), il quale decomprime il testo e lo trasforma in formato XML. Le righe 3,4,5 sono equivalenti ma con filtri differenti.

Se il file considerato è Test.doc.gz, il filtro applica, in teoria, prima la seconda riga e poi la quinta riga, in realtà crea un unico comando unendo le due righe.

Con questa tecnica possiamo indicizzare "qualsiasi" tipo di file, estraendo o associando del testo.

Per esempio, se abbiamo un file in formato JPG, possiamo estrarre i campi IPTC indicizzandoli. In un file POSTSCRIPT^TM, invece, possiamo estrarre le parole in esso contenute.

Spieghiamo ora come funziona il Builder.

In primo luogo, se il Builder accerta che il Dbase esiste, aggiunge ad esso i file da indicizzare e non lo inizializza. Per ogni file da indicizzare, il Builder controlla se dev'essere applicato un filtro: in caso affermativo, sarà il filtro a passare il flusso di dati al Builder, in caso contrario, leggerà il file. Non tutte le parole verranno considerate, a seconda delle regole di stemming e stopwords.

Verrà usata il più possibile la memoria, per ridurre le scritture su disco molto più onerose in termini di tempo. Le tecniche utilizzate per l'allocazione di memoria, ottimizzano e riducono i tempi di esecuzione.

Il modulo che permette di fare una query al Dbase, il Retrieve, aspetta determinati parametri, che ora vedremo, e restituisce la lista dei documenti trovati (vedi Tabella 6.8, Parametri query).

In questo caso, viene utilizzata un'interfaccia utente che permette di interrogare il dbase tramite linea di comando o CGI, usando il metodo get.

6.5 Algoritmo di Ranking

Quando si invia una query, ci si aspetta di ricevere i documenti in ordine di rilevanza; gli algoritmi di ranking fanno proprio questo, cercando di dare un peso ad ogni documento e ordinandolo in modo decrescente rispetto al peso stesso.

L'algoritmo usato è matematico ed ha le seguenti caratteristiche⁶.

• Ad ogni termine indicizzato è assegnato un peso, il quale riflette la relativa importanza all'interno della collezione. Il peso del termine è inversamente proporzionale alla sua popolarità, così che ad un termine che appare molte volte, viene assegnato un peso minore rispetto ad un termine che appare poche volte.

• La frequenza del termine, all'interno del documento, ha effetto nel calcolo del ranking. Se un termine ricorre molte volte, il ranking del documento aumenta in modo logaritmico.

• Si cerca di equilibrare frequenza del termine e lunghezza del documento: se un grande documento ha una frequenza elevata di un termine, non viene considerato migliore di un piccolo documento con una frequenza minore dello stesso termine.

• Viene considerato anche il numero di volte che il termine appare nella query: se un termine è presente più volte nella query, il suo peso è incrementato logaritmicamente.

• quando viene assegnato un peso ad un termine, non viene considerata la sua posizione all'interno del documento, per cui, se il termine appare nel titolo o in qualsiasi altro posto del documento, la rilevanza rimane la stessa.

Prima di descrivere l'algoritmo vero e proprio, diamo alcune definizioni che utilizzeremo in seguito.

Termine (T): una parola indicizzata nel dbase. Ogni documento è considerato come una lista di parole, anche se alcune parole possono essere state eliminate dai procedimenti di stemming e stopwords.

I seguenti parametri vengono calcolati in fase di indicizzazione:

Frequenza Termine (TF): il numero di documenti in cui il termine appare.

Frequenza Termine nel Documento (DTF): il numero di volte che il termine appare all'interno del particolare documento.

Grandezza della Collezione (N): il numero di documenti indicizzati nel dbase.

Frequenza inversa del documento (IDF): è calcolata nel seguente modo: LOG(1+N/TF) e rappresenta il peso del termine.

Peso del Termine nel documento (DTW): il peso del termine all'interno del documento, così calcolato: (1+LOG(DTF))*IDF .

Peso del Documento (DWT): il peso calcolato con la radice quadrata della somma di (DTW*DTW), per tutti i termini del documento. DWT rappresenta la "lunghezza" del documento ed è usato per normalizzare il ranking.

I seguenti parametri vengono calcolati in fase di ranking:

Frequenza del Termine della Query (QTF): è il numero di volte che il termine della query appare nel testo.

Frequenza massima del Termine della query (QMF): la massima frequenza di ogni termine della query all'interno del testo.

Peso del Termine della Query (QTW): il peso dato per ogni termine della query, calcolato nel seguente modo: ( (0.5+ ( 0.5 * (QTF)/(QMF) ) )*(IDF)).

Algoritmo:

Il calcolo del ranking procede nel seguente modo.

1. Per ogni termine della query è calcolato QTW.

2. Il termine viene ricercato nell'indice; se viene trovato, tutti i documenti in cui il termine appare, vengono recuperati. Per ogni documento, il rank è memorizzato come somma del prodotto di DTW e QTW (DTW*QTW) per ogni termine della query trovato nel documento.

3. Quando tutti i termini sono stati ricercati, si ha una lista di rank associata ad ogni documento. Tale rank viene normalizzato dividendolo per il relativo DWT del documento.

4. I documenti, infine, vengono ordinati in modo decrescente rispetto al rank.

Le frequenze calcolate nell'elaborazione del ranking, vengono memorizzate nel dbase, permettendo, in fase di query, di non dover leggere i documenti e portando, quindi, ad un notevole risparmio in fase di elaborazione.

La seguente tabella elenca i dati che sono memorizzati nei file indice del Dbase.

CAPITOLO 7

Risultati Sperimentali

7.1 Introduzione

Il questo capitolo esporremo i risultati di alcuni test ottenuti con il Sistema Distribuito IR, Network Search Engine.

Il primo esperimento è stato condotto con l'intento di testare le prestazioni del Dbase FullText.

Si è verificato che, sempre con i mezzi limitati a nostra disposizione, aumentando la complessità della query o aumentando la grandezza del Dbase, (entro un certo limite, ovviamente), le prestazioni tendono ad essere costanti.

Il secondo test, invece, è incentrato sul Sistema Distribuito IR. Si è cercato di verificare se, con l'aumentare delle partizioni e di conseguenza con la moltiplicazione del numero di processi cooperanti, le prestazioni rimangano costanti: e la risposta è senz'altro affermativa.

In definitiva, possiamo aumentare il Dbase, aumentando gli oggetti indicizzati, e mantenere pressochè constante il tempo di risposta alle query.

Abbiamo anche considerato che, i tempi aggiuntivi dovuti alla comunicazione tra processi, tende ad essere trascurabile con l'aumentare delle dimensioni del Dbase.

7.2 Piattaforma di Test

Per poter rendere più veritieri i nostri test, abbiamo cercato di usare dati reali per il nostro Dbase FullText, nel particolare, usando articoli di giornale del quotidiano Il Gazzettino.

Per quanto riguarda l'Hardware, abbiamo usato PC, in quanto, questo sistema cerca di dare una soluzione alla problematica del reperimento di informazioni in breve tempo, usando macchine il cui rapporto qualità-prezzo, sia molto conveniente; il miglioramento esponenziale della tecnologia odierna, rende ottimale l'uso del PC, rispetto ad altri sistemi.

Descriviamo con dati tecnici la collezione di test.

7.2.1 Collezione di Test

Come già accennato nel precedente paragrafo, la collezione di test è stata "alimentata" con articoli reali di quotidiano. Sono stati usati 1.500.000 di articoli distinti, ognuno dei quali, per comodità di formato, è stato trasformato in HTML. Gli articoli occupano circa 9Gb sul filesystem, mentre, il numero di parole distinte indicizzate, è di circa 500.000.

Il Dbase FullText ha un indice delle parole di circa 30Mb e una dimensione della lista di postings di 500Mb.

Tutto questo è una partizione del Dbase, mentre, per comodità, le altre partizioni sono replicate: in realtà, per come è strutturato il Dbase Distribuito, le partizioni dovrebbero essere disgiunte.

7.2.2 Piattaforma Hardware

La piattaforma Hardware è composta da PC collegati fra di loro attraverso uno Switch Cisco Catalist 550X, concentratore con una banda passante in grado di permettere lo scambio effettivo di 100Mb tra le varie macchine.

I PC sono identificati con un nome: pc-rik, pc-gra, pc-fra, pc-mar, pc-lor, pc-www1 (vedi Figura 7.1).

Tutti le macchine, tranne pc-www1, hanno la stessa struttura Hardware, ossia: 256Mb di Ram, un processore Pentium da 600Mhz su motherboard INTEL e una scheda di rete da 100Mb.

Il pc-www1 ha 2 processori AMD da 800Mhz su di una motherboard ASUS, una scheda di rete da 100Mb e 512Mb di RAM.

Tutti questi PC hanno come sistema operativo Linux. Le caratteristiche di Linux sono identiche, Kernel 2.4.3 e Glibc 2.2.2, tranne che per il pc-www1 che ha la versione di Kernel 2.2.18, con Glibc 2.2.1.

Figura 7.1 Ambiente usato per i Test

7.3 Test I : Query Locali al Dbase

Il test è stato svolto sul Pc-Rik, nel quale interagiscono i processi che andremo a descrivere.

Il Clisnd (il processo che invia la query), invia la richiesta al Broker, che a sua volta la invia ad un suo processo Agent. Dopo aver evaso la query, estraendo i dati dalla collezione, l'Agent la invia al Clircv (il processo che riceve la risposta). In questa simulazione, il Clisnd e il Clircv, sono stati distinti, ma, in realtà, le due entità corrispondono ad un unico Client.

Nel nostro esperimento sono state usate due collezioni, una di 300.000 oggetti, l'altra di 1.500.000; per ognuna delle collezioni, sono state eseguite query con 1,2,3,4 e 5 parole messe in OR o in AND; i termini, usati per le query, sono stati scelti attraverso un programma che li selezionava casualmente. I risultati medi ottenuti sono stati raggruppati in Prova A e Prova B. È da notare che gli Agent avevano MAXOBJ=100, (solo i primi 100 oggetti con rank maggiore venivano considerati).

L'esperimento, lavorando in maniera Debug, ha tracciato il flusso e i tempi di esecuzione per ogni prova. Vediamo, nelle pagine seguenti, una tabella riepilogativa e i grafici ottenuti.

Dalla lettura dei grafici, deduciamo che:

• anche con risposte contenenti un numero di oggetti sempre maggiore;

• anche con query sempre più complesse (aumentando, in altre parole, la complessità della richiesta);

• anche con l'aumento delle dimensioni del Dbase (sempre entro certi limiti),

le risposte rimarranno, in termini di tempo, pressochè costanti, e comunque, mai oltre i 500ms.

Grafico 7.1Tempi Elaborazione Query

Grafico 7.2 Tempi Elaborazione Query

Grafico 7.3 Tempi Elaborazione Query

Grafico 7.4 Tempi Elaborazione Query

Grafico 7.5 Tempi Elaborazione Query

7.4 Test II: Query Distribuite al Dbase

Per questo test, abbiamo usato 6 PC, come si vede nella figura 7.1. L'interazione fra processi è un po' più complessa, rispetto al test precedente. Vediamo in dettaglio la configurazione in esame.

Per semplificare la complessità del test, rimanendo, comunque, nell'ambito di una prova attendibile, i demoni Clisnd, i cinque Broker e il Clircv, lavoreranno nel pc-rik. Negli altri PC viene fatto girare, in ognuno, un demone Agent, che gestirà una partizione del Dbase Distribuito.

Il flusso avviene nel seguente modo. Il demone Clisnd invia la richiesta ad un Broker, il quale la invia al proprio Agent, che fisicamente risiede nel Computer pc-gra. L'Agent, avendo ricevuto sia la query che la tolopogia di rete, invia al resto dei Broker, che risiedono nel pc-rik, le richieste alle altre partizioni che verranno gestite dagli Agent che risiedono negli altri PC.

Tutti i dati confluiscono, tramite gli agenti che lavorano in modalità "locale", nell'Agent che risiede nel pc-gra, che lavora in modalità "concentratore", il quale lo trasferirà al demone Clircv che risiede nel pc-rik.

L'insieme dei processi, che lavorano in maniera Debug, traccia il flusso e i tempi di esecuzione per ogni prova. Le tabelle riepilogative e i grafici da esse ottenuti, sono illustrate di seguito.

Dai grafici ottenuti, possiamo dedurre che, anche con Dbase Distribuiti sempre più grandi, si hanno risposte, in termini di tempo, pressochè costanti, inferiori, in ogni modo, ai 2000ms.

Anche in questo test, come nel precedente, i termini, usati per le query, sono stati scelti attraverso un programma che li selezionava casualmente.

CAPITOLO 8

Conclusioni e Sviluppi Futuri

Dando per scontato l'assioma che qualunque lavoro può essere migliorato e corretto, riteniamo doveroso dare una panoramica dei punti che, in un lavoro inevitabilmente parziale come questo, sono stati, non volutamente, tralasciati.

• La memorizzazione dei dati già aggregati, richiesti precedentemente già da altre query, permette di eliminare i tempi necessari alla risposta. La gestione della cache potrà essere affidata sia all'Agent che al Broker, a seconda della modalità di funzionamento del Sistema in questione.

• Il Sistema Distribuito IR può essere potenziato e migliorato in efficienza, per quanto riguarda l'hardware, ma, dato che la correttezza dei dati ricevuti dipende dall'algoritmo del Ranking, l'aumento della velocità sarà ininfluente rispetto alla correttezza delle risposte. Algoritmi innovativi di Ranking, pur mantenendo costante la velocità di risposta, forniranno risultati molto più corretti alle richieste di informazioni.

• La segretezza, a volte indispensabile, delle informazioni che si richiedono, necessita di particolari meccanismi di autentificazione e autorizzazione, che possono essere implementati sui protocolli di comunicazione tra il Client, il Broker, e l'Agent. Per regolare e ottimizzare il flusso di informazioni, d'altro canto, può essere necessario usare delle tecniche di accounting, che memorizzano le caratteristiche delle richieste, per poter migliorare la funzionalità in base all'utilizzo del sistema.

• Il Sistema NSE non può distinguere dati e informazioni provenienti da differenti linguaggi; il limite non è trascurabile, data la globalizzazione informatica in atto nel mondo da ormai molti anni. La creazione di dbase paralleli e di meccanismi che permettono di codificare in un unico linguaggio i termini degli idiomi differenti, permetterà lo sfruttamento dell'NSE a Client di differente lingua madre.

• La modifica dei documenti indicizzati dal nostro dbase, comporterà un ricalcolo dei parametri statistici usati dall'algoritmo di Ranking, per cui, si utilizzerà un modulo che aggiornerà i dati del Dbase FullText, in base alle modifiche apportate al documento.

• Il miglioramento del Sistema in termini di "Trasparenza", darà un ulteriore stimolo creativo a quanti vorranno continuare lo sviluppo dell'NSE.

Appendice A

Figure

Elenco Figure

1.1 Schema di un Sistema Information Retrieval (IR) 6

1.2 Vista Logica di un Documento 7

1.3 Modelli di Information Retrieval 10

1.4 Modelli Liste non Sovrapposte 23

1.5 Modelli Nodi Prossimali 24

1.6 Recall e Precison 30

1.7 Contingenza 31

1.8 Inverted File Index 36

1.19 Signature File 41

1.10 Concept index 43

1.11 Esempi di suffissi 45

1.12 Suffix Tree 45

2.1 Multitasking Parallelo su macchine MIMD 51

2.2 Partizionamento Parallelo dei processi su macchine MIMD 52

2.3 Modalità di Partizionamento: Document Partitioning 53

2.4 Modalità di Partizionamento: Term Partitioning 54

3.1 Architettura di N Partizioni 61

3.2 Architettura di una Partizione 66

3.3 Flussi del Broker 66

3.4 Flussi dell'Agent 67

3.5 Flusso della Query 69

3.6 Flusso del Client 70

7.1 Ambiente usato per i Test 119

Elenco Grafici

7.1 Tempi Elaborazione Query (300.000 Oggetti in OR) 122

7.2 Tempi Elaborazione Query (300.000 Oggetti in AND) 123

7.3 Tempi Elaborazione Query (1.500.000 Oggetti in OR) 124

7.4 Tempi Elaborazione Query (1.500.000 Oggetti in AND) 125

7.5 Tempi Elaborazione Query (1.500.000 Oggetti Trovati) 126

7.6 Query Distribuita rispetto ai Byte trasferiti 137

7.7 Query Distribuita rispetto agli Oggetti trovati 138

Elenco Formule

1.1 Similarità Modello Booleano 11

1.2 Similarità Modello Vettoriale (Forma A) 14

1.3 Similarità Modello Vettoriale (Forma B) 14

1.4 Peso di un termine t (Forma A) 15

1.5 Peso di un termine t (Forma B) 15

1.6 Peso di un termine t (Forma C) 16

1.7 Peso di un termine t (Forma D) 16

1.8 Peso di un termine t (Forma E) 16

1.9 Frequenza relativa di un termine t 16

1.10 Frequenza relativa di un termine t 17

1.11 Frequenza relativa di un termine t 17

1.12 Frequenza relativa di un termine t 17

1.13 Peso assegnato al documento relativo al termine t 17

1.14 Regola del coseno 17

1.15 Regola del coseno per il ranking 18

1.16 Peso del Documento e della Query 18

1.17 Similarità del Modello Vettoriale 18

1.18 Probabilità PageRank 19

1.19 Similarità nel Modello Probabilistico (Forma A) 20

1.20 Similarità nel Modello Probabilistico (Forma B) 21

1.21 Similarità nel Modello Probabilistico (Forma C) 21

1.22 Precision 31

1.23 Recall 31

1.24 Fallout 31

1.25 Media Armonica 32

1.26 E misura 32

1.27 Misura di Meadow 32

1.28 Misura di Heine 32

1.29 Misura di Vickery 33

1.30 Q misura 33

2.1 Misura Performance in Sistemi Paralleli 49

2.2 Massimo Speedup ottenibile 50

2.3 Efficienza Sistema Parallelo 50

Elenco Tabelle

1.1 Alcuni metodi di compressione per d-gap 39

1.2 Comparazione tra i metodi di compressione 39

4.1 Parametri del Broker 79

4.2 Struttura Ricevuta dal Client 83

4.3 Struttura Inviata all'Agent 84

4.4 Struttura Topologia di Rete 84

4.5 Struttura che Memorizza Configurazione Agent 84

4.6 Struttura che Memorizza Configurazione Broker 84

5.1 Parametri dell'Agent 93

5.2 Struttura Ricevuta dal Broker 97

5.3 Struttura inviata ai Brokers 98

5.4 Struttura Ricevuta dalla Query_Db 98

5.5 Struttura Ricevuta dagli Agent 98

5.6 Struttura Inviata al Client 98

6.1 Descrizione dei File che Costituiscono il Dbase 108

6.2 Record Creati per Ogni Documento 108

6.3 Struttura del File DOCPTRS 109

6.4 Struttura del File FILES 109

6.5 Struttura del File DOCS 109

6.6 Struttura del file POSTINGS 110

6.7 Variabili d'Ambiente 111

6.8 Parametri query 113

6.9 Dati Statistici Memorizzati nel Dbase 116

7.1 Traccia Flusso Query Locale 121

7.2 Caratteristiche Query Distribuita con 1 Partizione 128

7.3 Traccia Flusso Query Distribuita con 1 Partizione 128

7.4 Caratteristiche Query Distribuita con 2 Partizioni 129

7.5 Traccia Flusso Query Distribuita con 2 Partizioni 130

7.6 Caratteristiche Query Distribuita con 3 Partizioni 131

7.7 Traccia Query Distribuita con 3 Partizioni 132

7.8 Caratteristiche Query Distribuita con 4 Partizioni 133

7.9 Traccia Query Distribuita con 4 Partizioni 134

7.10 Caratteristiche Query Distribuita con 5 Partizioni 135

7.11 Traccia Query Distribuita con 5 Partizioni 136

Appendice B

Listati

I programmi che formano il Sistema Information Retrieval Distribuito, (NSE), sono il Broker e l'Agent; inoltre, sono stati creati altri programmi di supporto per creare il Dbase, fare le simulazioni e il debug di tale sistema.

Il Programma "Builder" crea il Dbase FullText, il programma "Retrieve" viene richiamato come cgi dal file "search.html", il quale usando il metodo Get, esegue una query al Dbase FullText.

Per la simulazione, sono stati creati due programmi che emulano N Client: il "Clisnd" serve per inviare le richieste di query al NSE, mentre il "Clirvc" riceve le risposte delle query inviate dal "Clisnd". Qui di seguito vengono descritte, per i vari programmi, tutte le funzioni più significative e successivamente ne viene dato il loro listato scritto in linguaggio C.

B.1 Descrizione Sintetica dei Moduli

Elenco funzioni del Broker e dell'Agent

mainloop() - Corpo principale del demone

readconfigfile() - Legge il file di configurazione e memorizza i suoi parametri

req2snd() - Aspetta le richieste dai Client e le invia ai propri Agent

scelta_broker() - Ricerca la topologia di rete

req_broker() - Aspetta le Richieste dal Broker

aggreg_data() -Aggregazione dei risultati della query

snd_client() - Invio dei dati ai Client o agli Agent

query_dist() - Retrieval dati sul dbase fulltext distribuito

query_db() - Esegue query nel dbase fulltext locale

discard_stupid_environment() - Elimina variabili di ambiente inutili

daemon_init() - Trasforma il processo in un processo demone

logpid() - Scrive in un file di lock il numero di processo del demone

err_sys() - Gestisce gli errori inviandoli al sysglod

sig_close() - Chiude il mascheramento dei segnali

sig_init() - Riassegnamento e mascheramento segnali

sig_block()- Blocco segnali tramite una maschera precedentemente assegnata

sig_unblock() - Sblocca alcuni segnali precedentemente bloccati

sig_wait() - Mette in attesa i segnali

sig_preexec() - Ripristino default interrupt SIGPIPE

sig_alrm() - JMP dopo un allarme

sig_close() - Chiusura del programma e rilascio socket

readn() - Leggo N byte dal descrittore specificato (tipo socket)

writen() - Scrivo N byte sul descrittore specifato (tipo socket)

getip2name() - Determino l'IP dato il nome della macchina

microsleep() - Sospensione del processo per un tempo espresso in millisecondi

Elenco principali funzioni dbase fulltext

locate_documents()- Trova i documenti da indicizzare ricorsivamente

getword() - Estrae le parole dai documenti trovati

queryoutput() - Formatizza le entry della query, assegnandole alla struttura

queryinput() - Legge i parametri della query passati dal modulo Agent

create_database() - Crea la struttura del dbase fulltext

foreachposting() - Aggiusta la lista dei posting per ogni termine

btree_create() - Crea il btree index

btree_dump_blocks() - Scrivi blocchi compressi dell'index

btree_open() - Apri il btree index

btree_close() - Chiudi il btree index

btree_foreach() - Posizionamento nel btree index

open_collection() - Apri tutti i file del dbase fulltext

close_collection() - Chiude tutti i file del dbase fulltext

query_evaluate() - Valuta la query

dbopen() - Apre il database

dbclose() - Chiude il database

dbaddfile() - Aggiunge un file nel database

dbadddoc() - Aggiunge un documento nel database

B.2 Listati dei Moduli

/***************************************************************************

broker_ftrd.h - description

-------------------

begin : Mon Set 11 2000

copyright : (C) 2000 by Riccardo Saccon

email : riccardo.saccon@gazzettino.it

***************************************************************************/

/***************************************************************************

* *

* This program is free software; you can redistribute it and/or modify *

* it under the terms of the GNU General Public License as published by *

* the Free Software Foundation; either version 2 of the License, or *

* (at your option) any later version. *

* *

***************************************************************************/

#ifndef broker_ftrd_h

#define broker_ftrd_h

#ifdef DEBUG

#define _PATH_BROKERCONF "./broker_ftrd.conf"

#endif

#ifndef DEBUG

#define _PATH_BROKERCONF "/etc/broker_ftrd.conf"

#endif

#define MAXGRP 1

#define _PATH_PROCESSPID "/var/run/broker_ftrd.pid"

#define MAXFD 256

#define TIMESLEEP 2

#define MAXPATH 128

#define LISTENQ 1024

#define MAXPARTDB 64

#define MAXTERM 1024

#define MAXAGENTI 32

#define MAXCLI 32

#define MXWAITRD 20

#define BUFF 2048

#define MAXLINE 2048

#define SELECTIMEOUTQUERY 300L

#define LOCAL "127.0.0.1"

#define AGENTE "SEND2AGENT"

#define M_BROKER "broker_"

#define M_BROKER_LEN 7

#define M_AGENT "agente_"

#define M_AGENT_LEN 7

#define M_HOST_NAME "host_name"

#define M_HOST_NAME_LEN 9

#define M_DEBUG "debug"

#define M_DEBUG_LEN 5

#define M_SELECT_TIMEOUT "select_timeout"

#define M_SELECT_TIMEOUT_LEN 14

Appendice C

C The GNU General Public License

GNU GENERAL PUBLIC LICENSE

Version 2, June 1991

Copyright (C) 1989, 1991 Free Software Foundation, Inc.

59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.

Everyone is permitted to copy and distribute verbatim copies

of this license document, but changing it is not allowed.

Preamble

The licenses for most software are designed to take away your

freedom to share and change it. By contrast, the GNU General Public

License is intended to guarantee your freedom to share and change free

software--to make sure the software is free for all its users. This

General Public License applies to most of the Free Software

Foundation's software and to any other program whose authors commit to

using it. (Some other Free Software Foundation software is covered by

the GNU Library General Public License instead.) You can apply it to

your programs, too.

When we speak of free software, we are referring to freedom, not

price. Our General Public Licenses are designed to make sure that you

have the freedom to distribute copies of free software (and charge for

this service if you wish), that you receive source code or can get it

if you want it, that you can change the software or use pieces of it

in new free programs; and that you know you can do these things.

To protect your rights, we need to make restrictions that forbid

anyone to deny you these rights or to ask you to surrender the rights.

These restrictions translate to certain responsibilities for you if you

distribute copies of the software, or if you modify it.

For example, if you distribute copies of such a program, whether

gratis or for a fee, you must give the recipients all the rights that

you have. You must make sure that they, too, receive or can get the

source code. And you must show them these terms so they know their

rights.

We protect your rights with two steps: (1) copyright the software, and

(2) offer you this license which gives you legal permission to copy,

distribute and/or modify the software.

Also, for each author's protection and ours, we want to make certain

that everyone understands that there is no warranty for this free

software. If the software is modified by someone else and passed on, we

want its recipients to know that what they have is not the original, so

that any problems introduced by others will not reflect on the original

authors' reputations.

Finally, any free program is threatened constantly by software

patents. We wish to avoid the danger that redistributors of a free

program will individually obtain patent licenses, in effect making the

program proprietary. To prevent this, we have made it clear that any

patent must be licensed for everyone's free use or not licensed at all.

The precise terms and conditions for copying, distribution and

modification follow.

GNU GENERAL PUBLIC LICENSE

TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

0. This License applies to any program or other work which contains

a notice placed by the copyright holder saying it may be distributed

under the terms of this General Public License. The "Program", below,

refers to any such program or work, and a "work based on the Program"

means either the Program or any derivative work under copyright law:

that is to say, a work containing the Program or a portion of it,

either verbatim or with modifications and/or translated into another

language. (Hereinafter, translation is included without limitation in

the term "modification".) Each licensee is addressed as "you".

Activities other than copying, distribution and modification are not

covered by this License; they are outside its scope. The act of

running the Program is not restricted, and the output from the Program

is covered only if its contents constitute a work based on the

Program (independent of having been made by running the Program).

Whether that is true depends on what the Program does.

1. You may copy and distribute verbatim copies of the Program's

source code as you receive it, in any medium, provided that you

conspicuously and appropriately publish on each copy an appropriate

copyright notice and disclaimer of warranty; keep intact all the

notices that refer to this License and to the absence of any warranty;

and give any other recipients of the Program a copy of this License

along with the Program.

You may charge a fee for the physical act of transferring a copy, and

you may at your option offer warranty protection in exchange for a fee.

2. You may modify your copy or copies of the Program or any portion

of it, thus forming a work based on the Program, and copy and

distribute such modifications or work under the terms of Section 1

above, provided that you also meet all of these conditions:

a) You must cause the modified files to carry prominent notices

stating that you changed the files and the date of any change.

b) You must cause any work that you distribute or publish, that in

whole or in part contains or is derived from the Program or any

part thereof, to be licensed as a whole at no charge to all third

parties under the terms of this License.

c) If the modified program normally reads commands interactively

when run, you must cause it, when started running for such

interactive use in the most ordinary way, to print or display an

announcement including an appropriate copyright notice and a

notice that there is no warranty (or else, saying that you provide

a warranty) and that users may redistribute the program under

these conditions, and telling the user how to view a copy of this

License. (Exception: if the Program itself is interactive but

does not normally print such an announcement, your work based on

the Program is not required to print an announcement.)

These requirements apply to the modified work as a whole. If

identifiable sections of that work are not derived from the Program,

and can be reasonably considered independent and separate works in

themselves, then this License, and its terms, do not apply to those

sections when you distribute them as separate works. But when you

distribute the same sections as part of a whole which is a work based

on the Program, the distribution of the whole must be on the terms of

this License, whose permissions for other licensees extend to the

entire whole, and thus to each and every part regardless of who wrote it.

Thus, it is not the intent of this section to claim rights or contest

your rights to work written entirely by you; rather, the intent is to

exercise the right to control the distribution of derivative or

collective works based on the Program.

In addition, mere aggregation of another work not based on the Program

with the Program (or with a work based on the Program) on a volume of

a storage or distribution medium does not bring the other work under

the scope of this License.

3. You may copy and distribute the Program (or a work based on it,

under Section 2) in object code or executable form under the terms of

Sections 1 and 2 above provided that you also do one of the following:

a) Accompany it with the complete corresponding machine-readable

source code, which must be distributed under the terms of Sections

1 and 2 above on a medium customarily used for software interchange; or,

b) Accompany it with a written offer, valid for at least three

years, to give any third party, for a charge no more than your

cost of physically performing source distribution, a complete

machine-readable copy of the corresponding source code, to be

distributed under the terms of Sections 1 and 2 above on a medium

customarily used for software interchange; or,

c) Accompany it with the information you received as to the offer

to distribute corresponding source code. (This alternative is

allowed only for noncommercial distribution and only if you

received the program in object code or executable form with such

an offer, in accord with Subsection b above.)

The source code for a work means the preferred form of the work for

making modifications to it. For an executable work, complete source

code means all the source code for all modules it contains, plus any

associated interface definition files, plus the scripts used to

control compilation and installation of the executable. However, as a

special exception, the source code distributed need not include

anything that is normally distributed (in either source or binary

form) with the major components (compiler, kernel, and so on) of the

operating system on which the executable runs, unless that component

itself accompanies the executable.

If distribution of executable or object code is made by offering

access to copy from a designated place, then offering equivalent

access to copy the source code from the same place counts as

distribution of the source code, even though third parties are not

compelled to copy the source along with the object code.

4. You may not copy, modify, sublicense, or distribute the Program

except as expressly provided under this License. Any attempt

otherwise to copy, modify, sublicense or distribute the Program is

void, and will automatically terminate your rights under this License.

However, parties who have received copies, or rights, from you under

this License will not have their licenses terminated so long as such

parties remain in full compliance.

5. You are not required to accept this License, since you have not

signed it. However, nothing else grants you permission to modify or

distribute the Program or its derivative works. These actions are

prohibited by law if you do not accept this License. Therefore, by

modifying or distributing the Program (or any work based on the

Program), you indicate your acceptance of this License to do so, and

all its terms and conditions for copying, distributing or modifying

the Program or works based on it.

6. Each time you redistribute the Program (or any work based on the

Program), the recipient automatically receives a license from the

original licensor to copy, distribute or modify the Program subject to

these terms and conditions. You may not impose any further

restrictions on the recipients' exercise of the rights granted herein.

You are not responsible for enforcing compliance by third parties to

this License.

7. If, as a consequence of a court judgment or allegation of patent

infringement or for any other reason (not limited to patent issues),

conditions are imposed on you (whether by court order, agreement or

otherwise) that contradict the conditions of this License, they do not

excuse you from the conditions of this License. If you cannot

distribute so as to satisfy simultaneously your obligations under this

License and any other pertinent obligations, then as a consequence you

may not distribute the Program at all. For example, if a patent

license would not permit royalty-free redistribution of the Program by

all those who receive copies directly or indirectly through you, then

the only way you could satisfy both it and this License would be to

refrain entirely from distribution of the Program.

If any portion of this section is held invalid or unenforceable under

any particular circumstance, the balance of the section is intended to

apply and the section as a whole is intended to apply in other

circumstances.

It is not the purpose of this section to induce you to infringe any

patents or other property right claims or to contest validity of any

such claims; this section has the sole purpose of protecting the

integrity of the free software distribution system, which is

implemented by public license practices. Many people have made

generous contributions to the wide range of software distributed

through that system in reliance on consistent application of that

system; it is up to the author/donor to decide if he or she is willing

to distribute software through any other system and a licensee cannot

impose that choice.

This section is intended to make thoroughly clear what is believed to

be a consequence of the rest of this License.

8. If the distribution and/or use of the Program is restricted in

certain countries either by patents or by copyrighted interfaces, the

original copyright holder who places the Program under this License

may add an explicit geographical distribution limitation excluding

those countries, so that distribution is permitted only in or among

countries not thus excluded. In such case, this License incorporates

the limitation as if written in the body of this License.

9. The Free Software Foundation may publish revised and/or new versions

of the General Public License from time to time. Such new versions will

be similar in spirit to the present version, but may differ in detail to

address new problems or concerns.

Each version is given a distinguishing version number. If the Program

specifies a version number of this License which applies to it and "any

later version", you have the option of following the terms and conditions

either of that version or of any later version published by the Free

Software Foundation. If the Program does not specify a version number of

this License, you may choose any version ever published by the Free Software

Foundation.

10. If you wish to incorporate parts of the Program into other free

programs whose distribution conditions are different, write to the author

to ask for permission. For software which is copyrighted by the Free

Software Foundation, write to the Free Software Foundation; we sometimes

make exceptions for this. Our decision will be guided by the two goals

of preserving the free status of all derivatives of our free software and

of promoting the sharing and reuse of software generally.

NO WARRANTY

11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY

FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN

OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES

PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED

OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF

MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS

TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE

PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,

REPAIR OR CORRECTION.

12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING

WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR

REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,

INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING

OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED

TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY

YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER

PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE

POSSIBILITY OF SUCH DAMAGES.

END OF TERMS AND CONDITIONS

Appendix: How to Apply These Terms to Your New Programs

If you develop a new program, and you want it to be of the greatest

possible use to the public, the best way to achieve this is to make it

free software which everyone can redistribute and change under these terms.

To do so, attach the following notices to the program. It is safest

to attach them to the start of each source file to most effectively

convey the exclusion of warranty; and each file should have at least

the "copyright" line and a pointer to where the full notice is found.

<one line to give the program's name and a brief idea of what it does.>

Copyright (C) 19yy <name of author>

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 2 of the License, or

(at your option) any later version.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

Also add information on how to contact you by electronic and paper mail.

If the program is interactive, make it output a short notice like this

when it starts in an interactive mode:

Gnomovision version 69, Copyright (C) 19yy name of author

Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.

This is free software, and you are welcome to redistribute it

under certain conditions; type `show c' for details.

The hypothetical commands `show w' and `show c' should show the appropriate

parts of the General Public License. Of course, the commands you use may

be called something other than `show w' and `show c'; they could even be

mouse-clicks or menu items--whatever suits your program.

You should also get your employer (if you work as a programmer) or your

school, if any, to sign a "copyright disclaimer" for the program, if

necessary. Here is a sample; alter the names:

Yoyodyne, Inc., hereby disclaims all copyright interest in the program

`Gnomovision' (which makes passes at compilers) written by James Hacker.

<signature of Ty Coon>, 1 April 1989

Ty Coon, President of Vice

This General Public License does not permit incorporating your program into

proprietary programs. If your program is a subroutine library, you may

consider it more useful to permit linking proprietary applications with the

library. If this is what you want to do, use the GNU Library General

Public License instead of this License.

Appendice C

ABSTRACTS

Questa tesi nasce dall'esigenza, sempre maggiore, di reperire informazioni da sistemi informatici in maniera efficiente e precisa. Il Sistema Distribuito che descriveremo, denominato Network Search Engine (NSE), aderisce al progetto dell'OpenSource, ed è stato interamente sviluppato in ambiente Linux.

L'NSE è costituito da 2 entità di base: il Broker, che ha il compito di gestire la topologia di rete e le richieste di query dai Client/Agent e l'Agent, che deve invece evadere la query e successivamente inviarla al Client/Agent che l'aveva richiesta. L'Agent lavora in due modalità: Concentratore, quando ha il compito di riunire la query distribuita, e Locale quando deve gestire solo una parte della query distribuita.

L'NSE è costituito da N partizioni, ognuna delle quali gestisce in maniera disgiunta una parte del Dbase FullText Distribuito. Ogni partizione può essere composta da K repliche, questo per ragioni di Efficienza e Affidabilità. Ogni replica è composta da un Broker il quale gestisce M Agent; il numero di Agent dipende dalla quantità di query che vogliamo evadere contemporaneamente. La richiesta di una query viene inviata dal Client ad un Broker, il quale sceglierà, con politica RR (Round Robin), l'Agent (che lavora in modalità Concentratore) libero. Tale Agent invierà agli altri N-1 Brokers la richiesta di query, aspettando i dati che gli verranno forniti dagli altri N-1 Agents (che lavorano in modalità Locale), quest'ultimi selezionati dai relativi N-1 Brokers.

Il Dbase FullText Distribuito usa "Inverted Files" come metodo di indicizzazione e "Document Partition" per suddividere gli indici nelle N Partizioni. Per quanto riguarda l'algoritmo di rilevanza, "Ranking", esso sfrutta l'unione di due noti algoritmi, "Extended Boolean Model" e "Vector Model", opportunamente modificati per lavorare in ambiente distribuito. Il tutto è stato ottimizzato per limitare I/O su disco e ridurre la dimensione degli indici, in modo da avere la massima velocità di risposta. (ErressE).

Appendice E

Lucidi

Esigenza di un Sistema FullText Distribuito,

a bassi costi e personalizzabile

Open Source: Sfruttare codice sorgente

esistente

Obiettivi Principali: Efficienza, Scalabilità,

Affidabilità

Sistema costituito da 2 entità di base:

Broker: Gestione Topologia, Query Client

Agent: Evasione query, Invia dati Client

SISTEMA I.R.

Sistema I.R.

Sistema I.R.

Dell'Architettura Distribuita

Flessibilità: Sistema composto da nodi disomogenei

Concorrenza: Esecuzione simultanea di più processi

Scalabilità: Possibilità di potenziare o aumentare il numero di nodi

Affidabilità: Funzionamento corretto del Sistema anche in caso di errore

Trasparenza: Nascondere la complessità del Sistema


Bilanciamento: Possibilità di usare equamente tutte le risorse

Di n Partizioni

Flusso

Di una Partizione

Sistema Distribuito IR

Basso Costo

Servizi sempre attivi

Inserimento dati con Query in corso

Bilanciamento del carico

Ottimizzazione del traffico dati

Dbase FullText

Scansione ricorsiva dei documenti

Utilizzo dei filtri per poter indicizzare

qualsiasi tipo di oggetto

Indice Word-Based (Prefissi)

Ottimizzazione: I/O Disco, Memoria

Compressione degli Indici

Supporto funzioni AND, OR, termine

esatto o parziale nella query

Algoritmo di Ranking Distribuito

Eliminazione stopwords

Architettura modulare scalabile

Indicizzazione di un documento

Di Test

Una implementazione si trova nel sito:

http://quinordest2.gazzettino.it/.rik/Dbase/search.html

Tempi Elaborazione in relazione

ai termini della query (Doc No limit)

Tempi Elaborazione in relazione

ai termini della query (Doc No limit)

Tempi di elaborazione

in relazione al numero degli oggetti trovati

Tempi Elaborazione in relazione

al numero delle partizioni (Doc No limit)

Sviluppi Futuri

Gestione della cache

Algoritmi innovativi di Ranking

Meccanismi (AAA) Autentificazione,

Autorizzazione, Accounting

Distinzione tra i differenti linguaggi

Ricalcolo dei parametri statistici

Interfaccia utente più sofisticata e

Tools per l'amministratore del NSE

Bibliografia

[1] Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes - Compressing and Indexing Documents and Images . Morgan Kaufmann Publishers second Edition, 1999. Documentazione disponibile al sito http://www.mds.rmit.edu.au/mg

[2] Various Author. UdmSearch (mnoGoSearch) Documentation. Disponibile al sito http://sunsite.bilkent.edu.tr/pub/infosystems/udmsearch o http://search.mnogo.com

[3] Various Author. Htdiag Documentation. Disponibile nel sito http://www.htdig.org

[4] Various Author. Myfluz Documentation. Disponibile nel sito http://www.senga.org/mifluz/html

[5] Various Author. Simple Web Indexing System for Humans SWISH++ Documentation. Disponibile nel sito http://homepage.mac.com/pauljlucas/software/swish

[6] Various Author. Webglimp Documentation. Disponibile nel sito http://webglimpse.net

[7] Various Author. CNIDR Isite information System Documentation. Disponibile nel sito http://www.cnidr.org/isite.html

[8] Various Author. Harvest Documentation. Disponibile nel sito http://harvest.transarc.com e http://www.tardis.ed.ac.uk/harvest

[9] Various Author. SMART Documentation. Disponibile nel sito http://smart.embl-heidelberg.de

[10] Various Author. Information Dimensions Documentation. Disponibile nel sito http://www.idi.oclc.org

[11] Various Author. Fulcrum Technologies Inc. Documentation. Disponibile nel sito http://www.fultech.com

[12] Various Author. Yase Documentation. Disponibile nel sito http://www.mazumdar.demon.co.uk/yase_index.html

[13] Various Author. Excalibur Documentation. Disponibile nel sito http://www.xrs.com

[14] Variuos Author. Inventory of Full-Text Information Retrieval Software Vendors. Disponibile nel sito http://www.ifla.org o all'URL http://www.ifla.org/VII/s21/p1996/fulltext.htm

[15] A. Albano. Basi di Dati. Strutture e Algoritmi. Addison-Wesley October 1996

[16] Riccardo Baeza-Yates and Berthier Ribiero-Neto. Modern Informatio Retrieval. Addison Wesley, 1999

[17] Charles T. Meadow and Bert R. Boyce and Donald H. Kraft. Text Information Retrieval Systems (Library and Information Science Series). Academy Press, October 1999

[18] C.J. Van RIJSBERGEN B. Sc, Ph. D., M.B.C.S. Information Retrieval, 1979. Documentazione disponibile al sito http://www.dcs.gla.ac.uk/~keith o tramite mailto:keith@dcs.gla.ac.uk

[19] C.J. Van RIJSBERGEN. File organization in library automation and information retrieval, Journal of Documentation, 32, 294-317 ( 1976)

[20] C.J. Van RIJSBERGEN. An algorithm for information structuring and retrieval, Computer Journal, 14, 407-412 (1971)

[21] C.J. Van RIJSBERGEN. Further experiments with hierarchic clustering in document retrieval, Information Storage and Retrieval, 10, 1-14 (1974)

[22] G. Salton. The SMART Retrieval Sistem. Experimental in automatic documentation Processing, 1971

[23] G. Salton. Paper given at the 1972 NATO Advanced Study Institute for on-line mechanised information retrieval systems (1972)

[24] G. Salton. Dynamic Information and Library Processing, Prentice-Hall, Englewoods Cliffs, N.J. (1975)

[25] G. Salton. Manipulation of trees in information retrieval, Communications of the ACM, 5, 103-114 (1962)

[26] G. Salton and B.Kahle. Computer evaluation of indexing and text processing. Journal of the ACM, 15(1):8-36, January 1968

[27] G. Salton. Introduction to modern Information retrieval. McGrw-Hill, 1983

[28] Alberto Del Bimbo. Visual Information Retrieval. Morgan Kaufmann Publishers, June 1999

[29] Karen Sparck Jones and Peter Willett. Readings in Information Retrieval (Morgan Kaufmann Series in Multimedia Information and Systems). Morgan Kaufmann, July 1997

[30] Digital library D-Lib Magazine. Documentazione disponibile Full Text Retrieval al sito http://www.dlib.org

[31] ANSI/NISO Standards, The "Z39.50 Maintenance Agency". Documentazione disponibile al sito http://lcweb.loc.gov/z3950/agency

[32] RFC1913 C. Weider, J. Fullton, S. Spero, "Architecture of the Whois++ Index Service", RFC1913, 1996, ftp://ds.internic.net/rfc/rfc1913.txt

[33] XML e DTD . The Word Wide web Consortium. Documentazione disponibile al sito http://www.w3.org

[34] HTML. The Word Wide web Consortium. Documentazione disponibile al sito http://www.w3.org

[35] URI/URL. The Word Wide web Consortium. Documentazione disponibile al sito http://www.w3.org

[36] HTTP. The Word Wide web Consortium. Documentazione disponibile al sito http://www.w3.org

[37] MIME. The Word Wide web Consortium. Documentazione disponibile al sito http://www.w3.org

[38] MIME. "Multipurpose Internet Mail Extensions",estensioni multifunzione della posta Internet. Documentazione disponibile nel sito http://www.nacs.uci.edu/indiv/ehood/MIME/toc.html oppune nel sito http://www.cis.ohio-state.edu/Services/rfc/index.html

[39] RFC. Documentazione disponibile al sito http://www.cis.ohio-state.edu/Services/rfc/index.html

[40] G. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures. Addison-Wesley, 1991

[41] William Frakes and Ricardo Baeza-Yates. Information Retrieval: Data Structures and Algorithms. Prentice Hall, June 1992

[42] Information Retrieval System e FullTest Retrieval (mailto:salvio@giuda.deis.unical.it )

[43] F. Bergadano. Java-based and secure learning agents for information retrieval in distribuited systems (INFOMATION SCIENCES ) Information Sciences 113 (1999) 55-84. (mailto:bergadan@di.unito.it )

[44] Information Retrieval & Word Wide Wed (Marco Mariotti mailto:marcomariotti@tiscalinet.it http://www.unian.it )

[45] Progettazione di un motore di ricerca distribuito per WEB ( Tesi di Fabrizio Silvestri Università di Pisa anno Accademico 1999-2000 )

[46] D.E. Knuth. The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Massachusetts (1968)

[47] D.E. Knuth. The Art of Computer Programming, Vol 3, Sorting and Searching, Addison-Wesley, Reading, Massachusetts (1973)

[48] TREC (Text REtrieval Conference). Documentazione disponibile al sito http://trec.nist.gov

[49] IPV4. Documentazione (RFC) disponibile nel sito http://www.cis.ohio-state.edu/Services/rfc/index.html

[50] IPV6. Documentazione (RFC) disponibile nel sito http://www.cis.ohio-state.edu/Services/rfc/index.html

[51] Netsolve Progetto. Documentazione disponibile al sito http://www.cs.utk.edu/netsolve

[52] Avl. Documentazione disponibile al sito http://www.msu.edu/user/pfaffben/avl

[53] LibXml. Documentazione disponibile al sito http://xmlsoft.org

[54] Bzip2. Documentazione disponibile al sito http://sourceware.cygnus.com/bzip2

[55] W. Richard Stevens. UNIX network Programming Vol I Networking API's: Sockets and XTI Prentice Hall PTR, 1998

[56] W. Richard Stevens. UNIX network Programming Vol II Interprocess Communications. Prentice Hall PTR, 1998

[57] W. Richard Stevens. Advanced Programming in the UNIX Enviroment. Addison-Wesley, 1993

[58] W. Richard Stevens. Unix Sviluppo del Software di Networking. Gruppo Editoriale Jackson, 1991

[59] W. Richard Stevens. TCP/IP Illustated, Vol I The Protocols. Addison-Wesley, 1994

[60] W. Richard Stevens. TCP/IP Illustated, Vol II The Implementation. Addison-Wesley, 1995

[61] W. Richard Stevens and H. B. J. Clifford. TCP/IP Illustated, Vol III TCP for Transations, HTTP, NNTP and Unix Domain Protocols. Addison-Wesley, 1996

[62] Stephen T. Satchell LINUX ip Stacks Commentary. CoriolisOpen Press, 2000

[63] Douglas E. Comer Internetworking with TCP/IP, Vol I: Principles, Protocols, and Architecture. Prentice Hall PTR, 2000

[64] Douglas E. Comer Internetworking with TCP/IP, Vol II, ANSI C Version: Design, Implementation, and Internals. Prentice Hall PTR, 1998

[65] Douglas E. Comer Internetworking with TCP/IP, Vol III: Client-Server Programming and Applications-Windows Sockets Version. Prentice Hall PTR, 1998

[66] Man Page Linux Document Proget (LDP). Documentazione disponibile al sito http://www.ldp.org

[67] Beej's. Guide to Network Programming. Documentazione disponibile al sito http://www.ecst.csuchico.edu/~beej/guide/net

[68] Andrew S. TANENBAUM. Reti di Computer Third Edition. Prentice Hall International, 1996

[69] J. Dollimire and T. Kindberg and G. Coulouris. Distribuited System Concepts and Design Second Edition. Addison-Wesley, 1996

[70] T.H. Cormen, C.E. Leiserson , R.I. Rivest Introduzione agli Algoritmi Vol 1. Jackson Libri,1994

[71] T.H. Cormen, C.E. Leiserson , R.I. Rivest Introduzione agli Algoritmi Vol 2. Jackson Libri,1994

[72] T.H. Cormen, C.E. Leiserson , R.I. Rivest Introduzione agli Algoritmi Vol 3. Jackson Libri,1994

[73] David A. Patterson and Jonh L. Hennessy. Struttura e Progetto dei Calcolatori, L'interfaccia Hardware Software. Zanichelli 1995

[74] Abraham Silberschatz and Peter Galvin. Sistemi Operativi, Quinta Edizione. Addison-Wesley, 1998

[75] R. Geoff Dromey. Algoritmi Fondamentali. Jackson Libri, 1990

[76] Chris Dibona and Mark Stone and Sam Ockman. Open Sources: Voices from the Open Source Revolution (O'Reilly Open Source). O'Reilly & Associates, 1999

[77] Federico Di Trocchio. Le bugie della scienza perché e come gli scienziati imbrogliano. Arnoldo Mondadori Editore, 1993

[78] Julie Beth Lovins. Development of a Stemming Algorithm (published in "Mechanical translation and computational linguistics", 11:22-31, 1968). Documentazione disponibile http://www.cs.waikato.ac.nz/~eibe/stemmers