PhraseRank: indicizzazione per frasi.

Phrase identification in an information retrieval system

I sistemi di IR finora usati dai più grandi motori di ricerca si sono sempre basati sull’acquisizione di contenuti e documenti di testo tramite algoritmi in grado di riconoscere i temi trattati da un documento usando le singole parole contenute: da un documento, eliminate le stopwords, si acquisiscono le parole che formano il documento e si classifica qust’ultimo in base alla rilevanza delle parole all’interno del testo.

Il processo non è assolutamente così semplice come l’ho descritto sopra, ma rende l’idea degli attuali processi per la ricerca e il recupero delle informazioni di un documento di testo in una grande collezione di documenti come il web.

Il gigante californiano di Mountain View, ultimamente, ha rilasciato una serie di 5 brevetti che potrebbero cambiare l’attuale sistema di information retrieval, cambiando così non solo il sistema di indicizzazione dei documenti, ma anche il sistema di ranking e di ordinamento dei risultati, un processo di IR che andrebbe a rivoluzionare l’attuale mondo SEO: l’indicizzazione per frasi.

Il primo brevetto di Google della serie si intitola Phrase identification in an information retrieval system.

Abstract

“Un sistema di IR che usa frasi per indicizzare, recuperare, organizzare e descrivere documenti. Le frasi identificate predicono la presenza di altre frasi nel documento. I documenti vengono indicizzati in accordo alle frasi che includono. Le frasi correlate e l’estensione delle frasi sono anch’esse definite. Frasi in una query sono identificate e usate per recuperare e valorizzare i documenti. Le frasi sono anche usate per raggruppare i documenti nei risultati delle ricerche, creare le descrizioni dei documenti ed eliminare documenti duplicati dai risultati e dall’indice.”

Di seguito leggiamo le traduzioni dei claims del brevetto:

1. Un metodo di selezione documenti in un insieme in risposta ad una query, che comprende: ricevimento della query, idenfitifcazione di una pluralità di frasi nella query, dove minimo una frase è formata da più parole, identificazione dell’estensione di almeno una delle frasi identificate, e selezione dei documenti dall’insieme di documenti che contengono almeno una frase dall’insieme includendo frasi nella query e nell’estensione della frase.

2. Il metodo chiamato al punto 1, dove la selezione dei documenti comprende: combinazione di una “posting list” di un frase identificata e una “posting list” dell’estensione della frase identificata per formare una “posting list” combinata; selezione dei documenti che appaiono nella “posting list” combinata e nelle“posting list”di altre frasi identificate.

3. Un metodo di selezione documenti in una raccolta di documenti in risposta ad una query, comprendendo: ricevimento della query, identificazione di una frase incompleta nella query, rimpiazzo della frase incompleta con l’estensione della frase e selezione documenti dalla raccolta contenente l’estensione della frase.

4. Il metodo chiamato al punto 3, dove l’identificazione della frase incompleta e il suo rimpiazzo comprende: identificazione di una frase candidata nella query, corrispondenza della frase candidata ad una frase incompleta in una lista di frase incomplete e rimpiazzo della frase
candidata con l’estensione della frase associata con la frase incompleta.

5. l metodo chiamato al punto 3, dove un estensione della frase di una frase incompleta comprende una super sequenza di frasi
incomplete che comincia con la frase incompleta.

6. Un metodo di selezione documenti in una raccolta in risposta ad una query, che comprenda: ricevimento di una query includendo la prima e la seconda frase, recupero della “posting list”dei documenti contenente la prima frase; per ogni documento nella lista: accesso alla lista indicando frasi correlate della prima frase che sono presenti nel documento, e sensible a reagire alla lista della frase correlata indicando che la seconda frase è presente in un documento, selezionando il documento da includere nel risultato di una query, senza richiamare una “posting list”di documenti contenenti la seconda frase.

7. Il metodo chiamato al punto 6, comprendente inoltre: sensibile a reagire alla lista delle frasi correlate che indicano che la seconda frase non è presente in un documento, escludendo il documento dai risultati della query, senza recuperare una “posting list”di documenti contenenti la seconda frase.

8. Il metodo chiamato al punto 6, comprendente: in risposta alla lista delle frasi correlate indicando che la seconda frase non è una frase correlata alla prima, intersecando la “posting list”dei documenti per la prima frase e con una “posting list” di documenti per la seconda frase per selezionare i documenti contenenti sia la prima che la seconda frase.

9. Il metodo chiamato al punto 6, comprendente inoltre: archiviazione delle liste di frasi correlate per una prima frase in rispetto ad un documento in un vettore di bit, dove un bit del vettore è regolato per ogni frase correlata alla prima frase che è presente nel documento, e un bit del vettore è rimosso per ogni frase correlata alla prima frase che non è presente nel documento, dove il vettore di bit ha un valore numerico, e valorizzando il documento selezionato determinando un valore adattato del vettore in accordo con l’insieme di bit per le frasi correlate alla prima frase che sono presenti nel documento.

10. Un metodo di ordinamento dei documenti inclusi nei in un risultato di una ricerca in risposta ad una query, dove la query comprende minimo una frase di ricerca, comprendendo: per ogni documento nel risultato di ricerca, accedendo al vettore di frase correlate per una frase di ricerca, dove in ogni bit del vettore è indicata la presenza, o l’assenza, di una frase correlata alla frase di ricerca; e ordinando i documenti nei risultati delle ricerche con il valore del loro vettore di frasi correlate, in modo che il documento con il più alto valore del vettore di frasi correlate è ordinato più in alto nei risultati delle ricerche.

11. Il metodo del punto 10, dove ogni bit del vettore di frasi correlate è associato con un frase correlata della frase di ricerca; e i bit sono ordinati cosicchè il più significativo bit del vettore è associato con una frase correlata avendo una più estesa informazione guadagnata in rispetto alla frase di ricerca, e il bit meno significativo è associato con una frase correlata avendo la minore informazione appresa in rispetto alla frase di ricerca.

12. Un metodo di ordinamento dei documenti inclusi nei risultati di ricerca in risposta ad una query, dove la query comprende al meno una frase di ricerca: per ogni documento nel risultato di ricerca: accedendo al vettore di frasi correlate per una frase della query, dove in ogni bit del vettore è indicata la presenza o assenza di una frase correlata alla frase di ricerca; per ogni bit indicando la presenza di una frase correlata della frase di ricerca, aggiungendo un predeterminato numero di punti associati con il bit per valorizzare un documento, e ordinando i documenti nei risultati di ricerca tramite il loro punteggio.

13. Il metodo al punto 12, dove ogni bit del vettore di frasi correlate è associato con una frase correlata alla frase di ricerca; i bit sono ordinati cosicchè il bit più significativo del vettore è associato con una frase correlata avendo la più estesa informazione guadagnata in rispetto alla frase di ricerca, e il bit meno significativo associato con una frase correlata avendo la minore informazione guadagnata in rispetto alla frase di ricerca; e il predeterminato numero di punti è associato con ogni serie di bit dal maggior numero di punti associati con i bit più significativi fino al minor numero di punti
associati con il bit meno significativo.

14.Un metodo per fornire un sistema di ir: automaticamente identificando frasi valide in un insieme di documenti comprendendo una pluralità di documenti, dove le frasi valide contengono frasi con più parole; indicizzando i documenti in accordo con le frasi valide contenute nei documenti, ricevendo una query di ricerca; identificando frasi contenute nella query, selezionando documenti in accordo alle frasi identificate, e ordinando i documenti selezionati

Storia dell’invezione

[0009] I sistemi di IR, generalmente chiamati motori di ricerca, sono ora uno strumento essenziale per trovare informazioni su larga scala, diverse, e crescenti come Internet. Di solito, i motori di ricerca creano un indice che correla i documenti (o pagine) a parole individuali presenti in ogni documento. Un documento è recuperato in risposta ad una query contenente un certo numero di termini di ricerca, generalmente basato sull’avere alcuni dei termini di ricerca presenti nel documento. I documenti recuperati sono poi ordinati in accordo ad altre misure statistiche, come la frequenza di occorrenze dei termini di ricerca, il dominio, analisi dei link e simili. I documenti recuperati sono poi presentati agli utenti, tipicamente nel loro ordine valorizzato, e senza altri raggruppamenti o gerarchie imposte. In alcuni casi, una porzione selezionata di un testo di un documento è presentata per fornire all’utente una breve descrizione del contenuto del documento.

[0010] Dirette corrispondenze booleane dei termini di ricerca hanno ben note limitazioni, e in particolare non possono identificare documenti che non hanno i termini di ricerca, ma hanno parole correlate. Per esempio, in un tipico sistema booleano, una ricerca con “pastori australiani” non potrebbe fornire documenti su altre razze di cani come i Border Collies che non hanno l’esatto termine di ricerca. Anzi, tale sistema è similmente in grado di recuperare e valorizzare altamente i documenti circa l’Australia (che non hanno niente a che fare con i cani), e documenti in generale sui pastori.

[0011] Il problema è che i sistemi convenzionali indicizzano documenti basati su termini individuali, piuttosto che su concetti. I concetti sono spesso espresso in frasi, come “pastori australiani”, “presidente degli Stati Uniti” o “Sundance film festival”. Al meglio, alcuni sistemi indicizzeranno i documenti in rispetto a un predeterminato e molto limitato insieme di parole conosciute, che sono generalmente selezione da un operatore umano. L’indicizzazione di frasi è di solito evitata a causa delle richieste computazionali e di memoria per identificare tutte le possibili frasi con 3, 4, 5 o più parole. Per esempio, sull’assunto che ogni 5 parole possono costituire una frase, e un grande corpodi testo potrebbe avere al minimo 200.000 termini unici, ci sarebbero approssimativamente 3.2 per 10 alla 26 frasi possibili, chiaramente molto più che un sistema esistente potrebbe memorizzare o comunque manipulare in modo programmatico. Altro problema è che le frasi continuamente entrano ed escono dal lessico in termini del loro uso, molto più frequentemente che una nuova parola venga inventata. Nuove frasi vengono sempre generate, in campo tecnologico, artistico, legato ad eventi mondiali e legislativo. Altre frasi poi tendono a scomparire dall’uso comune nel tempo.

[0012] Alcune sistemi di IR esistenti cercano di provvedere al recupero di concetti usando modelli co-occorrenti di singole parole. In questi sistemi una ricerca su una parola, come “presidente” recupererà documenti che hanno altre parole che frequentemente compaiono in associazione a “presidente”, come “bianca” e “casa”. Mentre questo approccio può produrre dei risultati di ricerca avendo documenti che sono concettualmente correlati a livello di singole parole, questo non cattura di solito le relazioni in tema che sono inerenti fra co-occorenze di frasi.

[0013] In accordo a questo, c’è bisogno di un sistema di IR e di una metodologia che può comprensivamente identificare frasi su larga scala, indicizzare documenti in relazione a frasi, cercare ed ordinare documenti in accordo con le loro frasi, e fornire raggruppamenti addizionali e informazioni descrittive sui documenti.

Sommario del brevetto

[0014] Un sistema e una metodologia di IR che usa frasi per indicizzare, ricercare, ordinare e descrivere documenti in un insieme di documenti. Il sistema è adatto per identificare frasi che hanno sufficientemente frequenza e/o uso distinto in un insieme di documenti per indicare che esse sono “valide” o “buone” frasi. In questo modo frasi di più parole, per esempio frasi di 4, 5, o più termini, possono essere identificate. Questo evita il problema di identificare e indicizzare ogni possibile frase risultante da tutte le possibili sequenze di un dato numero di parole.

[0015] Il sistema è anche adatto per identificare frasi che sono correlate l’una all’altra, basandosi sull’abilitità di una frase di predire la presenza di un’altra frase nel documento. Più specificatamente, si usa una misura di predizione in relazione all’attuale grado di co-occorrenza di due frasi verso un aspettato grado di co-occorrenza delle due frasi. L’ottenimento dell’informazione, come la percentuale dell’attuale grado di co-occorrenza per aspettarsi il grado di co-occorrenza, è una misura di predizione. Due frasi sono correlate dove la misura di predizione supera una predeterminata soglia. In questo caso, la seconda frase ha un guadagno significativo dalle informazioni riguardo alla prima frase. Semanticamente, saranno frasi correlate quelle che sono comunemente usate per discutere e descrivere un dato tema o un concetto, come “presidente degli stati uniti” e “casa bianca“. Per una data frase, le frasi correlate possono essere ordinate in accordo alla loro rilevanza o significato basate sulle loro rispettive misure di predizione.

[0016] Un sistema di IR indicizza documenti in un insieme di documenti tramite la validità o la bontà delle frasi. Per ogni frase, una “posting list” identifica i documenti che contengono la frase. In più, per una data frase, una seconda lista, vettore, o altra struttura è usata per immagazzinare dati indicando quali delle frasi correlate di una data frase sono presenti in ogni documento contenendo la frase data . In questo modo, il sistema può prontamente identificare non solo quali documenti contengono quali frasi in risposta ad una query di ricerca, ma quali documenti contengono anche frasi che sono correlate alla frase di ricerca, e questo più similmente all’essere specifiche sui temi o concetti espressi nelle frasi di ricerca.

[0017] L’uso delle frasi e delle frasi correlate provvedono alla creazione e l’uso di clusters di frasi correlate, che rappresentano, semanticamente, significativi raggruppamenti di frasi. I clusters sono identificati dalle frasi correlate che hanno una misura di predizione molto alta fra tutte le frasi del cluster. I clusters possono essere usati per organizzare i risultati di una ricerca, inclusa la selezione di quali documenti da includere nei risultati della ricerca e il loro ordine, così come l’eliminazione di documenti dai risultati delle ricerche.

[0018] Il sistema di IR è anche adatto per usare le frasi quando ricerca i documenti in risposta ad una query. La query è processata per identificare ogni frase che è presente nella query, così come per rercuperare l’associata “posting list” per le frasi di ricerca, e le informazioni sulle frasi correlate. In più, in alcune istanze un utente può immettere una frase incompleta nella frase di ricerca, come “presidente degli“. Le frasi incomplete come questa possono essere identificate e rimpiazzate dall’estensione della frase, come “presidente degli stati uniti“. Questo aiuto assicura che più similmente le ricerche degli utenti vengono di fatto eseguite.

[0019] Le informazioni relative di frase possono anche essere usate dal sistema per identificare e selezionare quali documenti includere nei risultati delle ricerche. Le informazioni sulla frasi correlate indicano per una data frase in un dato documento, quali frasi correlate alla data frase sono presenti in un dato documento. Di conseguenza, per una query contenente due frasi di ricerca, la “posting list” per la prima frase di ricerca è processata per identificare documenti contenenti la prima frase, e poi l’informazioni relativa di frase è processata per identificare quali di questi documenti contiene anche la seconda frase di ricerca. Questi ulteriori documenti vengono inclusi nei risultati della ricerca. Questo elimina la necessità del sistema di processare separatamente la “posting list” della seconda frase di ricerca, fornendo tempi di ricerca più veloci. Giustamente, questo approccio può essere esteso ad ogni numero di frase in una query, limitando risorse computazionali e tempi.

[0020] Il sistema può essere poi adattato per usare la frase e l’informazione relativa di frase per ordinare i documenti in un insieme di risultati di ricerca. L’informazione relativa di frase di una data frase è preferibilmente immagazzinata in un formato, come un vettore di bit, che esprime il relativo significato di ogni frase correlata a una data frase. Per esempio, il vettore di frase correlato ha un bit per ogni frase correlata ad una data frase, e i bit sono ordinati in accordo alle misure di predizione per la frase correlata. I bit più significativi del vettore di frase correlato sono associati con le frasi correlate che hanno il valore più alto della misura di predizione, e il bit meno significativo è associato con la frase correlata che ha il valore più basso della misura. In questo modo, per un dato documento e una data frase, l’informazione relativa di frase può essere usata per valorizzare un documento. Il valore del vettore di bit può essere usato come valore del documento. In questo modo documenti che contengono un alto ordine di frasi correlate di una frase di ricerca sono più portati ad essere correlati alla query che quelli che hanno un basso ordine di frasi relative. Il valore del vettore di bit può essere usato anche come componente in una più complessa funzione di valorizzazione, e può essere pesato ulteriormente. I documenti possono essere ordinati in accordo con il loro loro valore.

[0021] L’informazione di frase può anche essere usata in un sistema di IR per personalizzare le ricerche per un utente. Un utente è modellato come una raccolta di frasi, per esempio, derivate da documenti che l’utente ha visionato (per esempio, visti sullo schermo, stampati, archiviati, etc). Più in particolare, dato un documento selezionato dall’utente, le relative frasi che sono presenti in questo documento, sono incluse in un modello o profilo dell’utente. Durante ricerche subsequenziali, le frasi nel “modello utente” sono usate per filtrare le frasi di una query di ricerca e per pesare il punteggio del documento dai documenti recuperati.

[0022] L’informazione di frase può anche essere usata in un sistema di IR per creare una descrizione di un documento, per esempio i documenti inclusi in un insieme di risultati di ricerca. Data una query di ricerca, il sistema identifica la frase presente nella query, insieme alle frasi ad essa correlate, e le la sua estensione. Per un dato documento, ogni frase di un documento ha un conto di quante frasi di ricerca, frasi correlate, ed estensioni sono presenti nella sentenza. Le frasi del documento possono essere ordinate da questi conti (singolarmente o in combinazione), e un certo numero delle frasi superiori di posto (esempio cinque frasi) sono selezionate per formare la descrizione del documento. La descrizione del documento può essere presentata all’utente quando un documento è incluso nei risultati delle ricerche, cosi che l’utente ottenga una migliore comprensione del documento, relativamente alla query.

[0023] Un perfezionamento ulteriore di questo processo di generazione delle descrizioni dei documenti permette al sistema di fornire descrizioni personalizzate, che riflettano l’interesse dell’utente. Come prima, un “modello utente” archivia informazioni identificando frasi correlate che sono di interesse per l’utente. Questo modello utente è intersecato con una lista di frasi correlate alle frasi di ricerca, per identificare sia frasi comuni sia gruppi. L’insieme comune è poi ordinato in accordo all’informazione relativa di frase. L’insieme risultante di frasi correlate è poi usato per ordinare le frasi di un documento secondo il numero di casi di queste frasi correlate presenti in ogni documento. Un numero di frasi che hanno il numero più alto di frasi comuni correlate è selezionato come descrizione personalizzata del documento.

[0024] Un sistema di IR può anche usare l’informazione di frase per identificare ed eliminare documenti duplicati, sia mentre indicizza l’insieme di documenti, o mentre processa una query di ricerca. Per un dato documento, ogni frase di un documento ha un conto di quante frasi correlate sono presenti nella frase. Le frasi del documento possono essere ordinate tramite questo conto, e un certo numero di frasi di posto superiore (esempio cinque frasi) sono selezionate per formare la descrizione del documento. Questa descrizione è poi archiviata in associazione al documento, per esempio come una stringa o un hash delle frasi. Durante l’indicizzazione, un nuovo documento trovato è processato nello stesso modo per generare la descrizione del documento. La nuova descrizione del documento può essere abbinata contro precedenti descrizioni, e se la corrispondenza viene trovata, allora il nuovo documento è duplicato. Similarmente, durante la preparazione dei risultati di una query di ricerca, i documenti nell’insieme dei risultati delle ricerche possono essere processati per eliminare duplicati.

I: descrizione del sistema

[0037] In riferimento alla fig.1, è mostrata l’architettura software di un sistema di ricerca incoporato 100 in accordo all’incorporazione della presente invenzione. In questo, il sistema include un sistema di indicizzazione 110, un sistema di ricerca 120, un sistema di presentazione 130 e un server front end 140.

[0038] Il sistema di indicizzazione 110 è responsabile dell’identificazione di frasi nei documenti, e dell’indicizzazione dei documenti in accordo con le loro frasi, accedendo a diversi siti web 190 e altri insiemi di documenti. Il server front end 140 riceve le query dall’utente di un client 170, e fornisce queste query al sistema di ricerca 120. Il sistema di ricerca 120 è responsabile della ricerca di documenti rilevanti per la query di ricerca (risultati di ricerca), includendo l’identificazione di ogni frase nella query di ricerca, e poi dell’ordinamento dei documenti nei risultati della ricerca usando la presenza di frasi per influenzare l’ordine di importanza. Il sistema di ricerca 120 fornisce i risultati di ricerca al sistema di presentazione 130. Il sistema di presentazione 130 è responsabile della modifica dei risultati di ricerca inclusa la rimozione di documenti duplicati, e della generazione di descrizioni in tema coi documenti, e fornisce i risultati di ricerca modificati al server front end 140, che fornisce i risultati al client 170. Il sistema 100 include un indice 150 che archivia le informazioni di indicizzazione pertinenti ai documenti, e un magazzino di frasi (dati) 160 che archivia le frasi, e le informazioni statistiche correlate.

[0039] Nel contesto di questa applicazione, i “documenti” rappresentano ogni tipo di media file che può essere indicizzato e recuperato dal motore di ricerca, inclusi documenti web, immagini, file multimediali, documenti di testo, pdf o altri. Un documento può avere una o più pagine, partizioni, segmenti o altri componenti, appropriatamente al suo contenuto e tipo. In maniera equivalente un documento può essere inteso come una “pagina“, come comunemente si usa per riferirsi ai documenti su Internet. Nessuna limitazione all’opportunità dell’invenzione è implicata dall’uso del termine generico “documenti”. Il sistema di ricerca 100 opera su un largo corpo di documenti, come Internet e il World Wide Web, ma può nello stesso modo essere usato in insiemi più limitati, come per l’insieme di documenti di una libreria o di una impresa privata. In entrambi i contesti, si valuteranno i documenti che sono generalmente distribuiti su diversi sistemi di computer e siti. Senza perdita di generalità allora, i documenti in generale, a meno del formato o della locazione (esempio quale sito web o database) sarà collettivamente corrisposto ad un corpo o ad una raccolta di documenti. Ogni documento ha associato un identificativo che identifica univocamente il documento; l’identificativo è di solito una URL, ma anche altri tipi (esempio numeri documenti) possono essere usati. In questa è assunto l’uso delle URL per l’identificazione dei documenti.

Il sistema di indicizzazione: parte I

[0041] In una incorporazione, il sistema di indicizzazione 110 fornisce tre funzioni primarie operative:

  1. identificazione di frasi e frasi correlate,
  2. indicizzazione di documenti con rispetto alle frasi,
  3. generazione e mantenimento di una tassonomia basata sulle frasi.

Queste abilità valuteranno che il sistema di indicizzazione 110 compierà altre funzioni in supporto delle convenzionali funzioni di indicizzazione.

[0042] 1. L’dentificazione delle frasi

[0043] L’operazione di identificazione della frase del sistema di indicizzazione 110 identifica “buone” o “cattive” frasi nell’insieme di documenti che sono utili per indicizzare e ricercare documenti. In un certo aspetto, le buone frasi sono frasi che occorrono in più di una certa percentuale di documenti nell’insieme di documenti, e/o sono indicati avendo un’apparenza distinta in tali documenti, come delimitato dalle modifiche di tags altri morfologie, formattazione, o indicatori grammaticali. Un’altro aspetto delle buone frasi è che sono premonizioni di altre buone frasi, e non sono soltanto sequenze delle parole che compaiono nel lessico. Per esempio, la frase “presidente degli Stati Uniti” è una frase che predice altre frasi quali “George Bush” e “Bill Clinton“. Tuttavia, altre frasi non sono premonitrici, come “cadere dalle nuvole” o “fuori di testa” poiché gli idiomi e i modi di dire come questi tendono a comparire con molte altre frasi differenti e non correlate. Quindi, la fase dell’identificazione della frase determina quali frasi sono buone frasi e quale sono difettose (cioè, difettando nella potenza premonitrice).

[0044] In riferimento alla fig.1, il processo di identificazione della frase segue i seguenti passi funzionali:

[0045] 200: Raccolta delle possibili buone frasi, con frequenza e co-occorrenza statistica delle frasi.

[0046] 202: Classificazione delle frasi possibili sia come buone o difettose basate sulle statistiche di frequenza.

[0047] 204: Scremare la lista di buone frasi basandosi su una misura preventiva derivata dalle statistiche di co-occorrenza.

[0048] Ciascuna di queste fasi ora sarà descritta con ulteriori dettagli .

[0049] La prima fase 200 è un processo tramite cui il sistema di indicizzazione 110 indicizza un insieme di documenti in una raccolta di documenti, facendo ripetutepartizioni nella raccolta di documenti nel tempo. Una partizione è processata per il passaggio. Il numero di documenti recuperati per passaggio può variare, ed è preferibilmente circa 1.000.000 per partizione. Si preferisce che soltanto i documenti precedentemente non recuperati siano processati in ogni partizione, fino a che non siano processati tutti i documenti, o si incontrino alcuni altri criteri per la terminazione del processo. In pratica, il recupero continua poichè i nuovi documenti sono continuamente aggiunti alla raccolta di documenti. I seguenti passi sono presi dal sistema di indicizzazione 110 per ogni documento che è recuperato.

[0050] Attraversare le parole del documento con una lunghezza della finestra di frase di n, dove la n è una lunghezza massima voluta della frase. La lunghezza della finestra sarà tipicamente almeno 2 e preferibilmente 4 o 5 termini (parole). Le frasi includono preferibilmente tutte le parole nella finestra di frase, comprese quelle che in altri modi sarebbero considerato stop words, come “un” “il” e così via. Una finestra di frase può essere terminata da una conclusione della linea, un ritorno di paragrafo, un tag, o altri indizi di un cambiamento nel contenuto o formato.

[0051] La figura 2 illustra una parte di un documento 300 durante un attraversamento del processo di recupero, mostante la finestra di frase 302 che comincia alla parola “razza” e che si estende di 5 parole verso la destra. La prima parola nella finestra di frase 302 è la frase candidata i, e ciascuna delle sequenze i+1i+2i+3i+4 e i+5 è similarmente una frase candidata. Quindi, in questo esempio, le frasi candidate sono: “razza“, “cani di razza“, “cani di razza per“, “cani di razza per“, “cani di razza per i baschi” e “cani di razza per i pastori baschi“.

[0052] In ogni finestra di frase 302, ogni frase candidata è controllata a sua volta per determinare se è già presente nella buona lista di frasi 208 o nella lista di frasi possibili 206 . Se la frase candidata non è presente sia nella buona lista 208 o nella lista possibile 206, allora la frase candidata è stata già determinata per essere “cattiva” eviene saltata.

[0053] Se la frase candidata è nella buona lista 208, come entrata gj allora la voce di indice 150 per la frase gj è aggiornata per includere il documento (per esempio, il relativo URL o altro identificativo del documento), per indicare che questa frase candidata gj compare nel documento corrente. Un’entrata nell’indice 150 per una frase gj (o un termine) è riferita come la “posting list” della frase gj . La “posting list” include una lista dei documenti d (dai loro identitificativi, per esempio un numero di documento, o alternativamente un URL) in cui la frase si presenta.

[0054] In più, la matrice di co-occorrenze 212 è aggiornata, come ancora spiegato sotto. Nel primissimo passaggio, le buone e le cattive liste saranno vuote e così, la maggior parte delle frasi tenderanno ad essere aggiunte alla lista di frasi possibili 206.

[0055] Se la frase candidata non è nella buona lista 208 allora è aggiunta alla lista possibile 206, a meno che non sia già presente. Ogni entrata p sulla lista di frasi possibili 206 ha tre conteggi associati:

[0056] P(p): Numero di documenti su cui la frase possibile compare;

[0057] S(p): Numero di tutti i casi della frase possibile;

[0058] M(p): Numero di casi interessanti della frase possibile. Un caso di una frase possibile è “interessante” dove la frase possibile è distinta dal contenuto limitrofo nel documento tramite indicatori grammaticali o di formattazione, per esempio essendo in grassetto, o sottolineate, o come anchor text di un link, o tra virgolette. Queste (ed altre) distinzioni di apparenza sono indicate dalle varie modifiche fornite con i tag HTML e dagli indicatori grammaticali. Queste statistiche sono effettuate per una frase quando è disposta sulla buona lista 208.

[0059] In addizione alle varie liste, è mantenuta una matrice delle co-occorrenze 212 (G) per le buone frasi. La matrice G ha dimensioni m x m, dove m è il numero delle buone frasi. Ogni elemento G(j,k) nella matrice rappresenta un paio di buone frasi ( gj gk ). La matrice 212 mantiene logicamente tre conti separati per ogni paio ( gj gk ) di buone frasi in rispetto ad una finestra secondaria 304 che è incentrata sulla parola corrente i, e si estende di +/- h parole. In un esempio, come in fig.3, la finestra secondaria 304 è di 30 parole ( i+30, i-30 ). La matrice delle co-occorrenze 212 mantiene:

[0060] R(j,k) Conteggio delle righe co-occorrenti. Il numero delle volte che la frase gj appare in un finestra secondaria 304 con la frase gk.

[0061] D(j,k) Conteggio interessante disgiunto. Il numero delle volte che ogni frase gj o gk appare come testo distinto nella finestra secondaria.

[0062] C(j,k) Conteggio interessante congiunto. Il numero di volte che sia le frasi gj che gk appaiono come testo distinto nella finestra secondaria. L’uso di questo conteggio è particolarmente utile per evitare le circostanze dove la prase (ad esempio: nota di copyright) appare frequentemente nelle barre laterali, nel footer o nell’header, a questa non ha poteri di predizione di altro testo.

[0063] In riferimento all’esempio di fig.2, assumiamo che “cani di razza” è nella buona lista di frasi 208, così come le frase “pastore australiano” e “pastore australiano Club dell’America“. Entrambi queste frasi compaiono nella finestra secondaria 304 intorno alla frase corrente “cani di razza“. Comunque, la frase “pastore australiano Club dell’America” compare come anchor text di un link (indicato dalla sottolineatura) verso un sito web. Così il conteggio della riga co-occorrente per la coppia “cani di razza” “pastore australiano” viene incrementato, e il conteggio di riga e quello di interesse disgiunto per “cani di razza” “pastore australiano Club dell’America” sono entrambi incrementati visto che le frasi posteriori compaiono come testo distinto.

Google TrustRank

Il TrustRank è un algoritmo brevettato da Google, in parte basato sulla valutazione dei siti effettuata da esseri umani, progettato per risolvere il grosso problema dello spam presente negli indici dei motori di ricerca.

Uno dei problemi più grandi che i motori di ricerca si sono trovati a combattere negli ultimi anni è la crescita del fenomeno denominato spam. Lo spam, in questo contesto può essere a grandi linee definito come la pubblicazione di pagine web create con il solo scopo di ingannare gli algoritmi dei motori di ricerca.

Uno dei primi metodi utilizzati per fare spam è stato quello di inserire nelle pagine web del testo nascosto agli esseri umani ma visibile ai motori di ricerca (per esempio impostando il testo con lo stesso colore dello sfondo della pagina oppure usando alcune proprietà dei fogli di stile), così da ottenere buoni posizionamenti relativamente ad argomenti che effettivamente non avevano niente a che fare con il contenuto visibile delle pagine.

Un altro metodo molto popolare per fare spam è quello di creare decine, o anche centinaia, di pagine sostanzialmente inutili per gli utenti, ma tutte contenenti uno o più link verso una specifica pagina, la quale la quale vedrà migliorato il suo posizionamento nei motori di ricerca a causa dell’aumento di fattori come la link-popularity o il PageRank.

In effetti, quando un motore di ricerca si trova davanti ad un circuito di siti web fortemente linkati fra loro, deve effettuare la difficile scelta di stabilire se essi siano davvero siti che si citano per approfondimenti reciproci dell’argomento trattato oppure semplicemente un circuito di spam. Per un essere umano che “conosca il mestiere” è relativamente semplice capire se un sito effettua spam, osservando per esempio in che percentuale esista nelle pagine contenuto utile e testo invisibile, controllando la visibilità e l’effettiva natura dei link, i nomi assegnati a domini, file e cartelle, confrontando gli indirizzi IP dei documenti a cui i collegamenti puntano ed altri fattori ancora. Per un computer, al contrario, riconoscere lo spam è un compito decisamente difficile, tanto è vero che l’approccio finora utilizzato da parte dei motori di ricerca è quello di far eseguire ad un apposito staff di persone il monitoraggio dei risultati per individuare pagine che effettuano spam ed eliminarle dall’indice del motore. Molti motori di ricerca possiedono apposite interfacce pubbliche che permettono la segnalazione di spam direttamente allo staff del motore che, appena possibile, verifica la correttezza della segnalazione ed eventualmente prende i provvedimenti del caso. Il problema dell’eliminazione dello spam dai propri indici è così importante per i motori di ricerca che, in mancanza di meglio sono disposti ad utilizzare questo tipo di approccio, assai lento, costoso, e in definitiva molto poco efficiente.

Nel 2004 alcuni ricercatori del dipartimento di Computer Science della Stanford University hanno pubblicato uno studio dal titolo “Combating web spam with TrustRank” (Combattere lo spam con il TrustRank) ed il 16 marzo 2005 la tecnologia TrustRank è stata ufficialmente brevettata da Google.

L’algoritmo di TrustRank può essere utilizzato sia per suggerire automaticamente allo staff di esseri umani quali sono le pagine del web da controllare più attentamente perché “a rischio spam,” sia per generare un punteggio da usare in fase di ordinamento delle pagine allo scopo di compensare gli effetti negativi che lo spam ha avuto sull’efficacia di altri algoritmi, come quelli per l’analisi del contenuto o quello del PageRank.

Dal momento che identificare lo spam è molto difficile per un computer il TrustRank utilizza in parte l’intervento umano per addestrare l’algoritmo a riconoscerlo.

Come funziona il TrustRank

A grandi linee il funzionamento de TrustRank è questo.

1)L’algoritmo seleziona un insieme di pagine relativamente piccolo (“seed pages”, pagine seme) secondo criteri che spiegheremo in seguito, delle quali non si sa ancora se effettuino spam o meno.

2)Un essere umano esamina ad una ad una tutte le pagine dell’insieme e le divide in “buone” (pagine che non effettuano spam) e “cattive” (pagine che effettuano spam).

3)L’algoritmo processa l’intero indice del motore di ricerca ed assegna a ciascuna pagina che vi è contenuta un punteggio di “trust” (fiducia) basato sul grado di vicinanza alle pagine seme “buone” nel grafo del web.

Ora vedremo in dettaglio come vengono scelte le “pagine seme”, come viene effettuata effettua la loro valutazione ed ovviamente come viene propagata la “fiducia” (trust) dalle pagine buone a tutte quelle che a loro collegate, più o meno direttamente.

L’algoritmo del TrustRank

Il TrustRank riesce a identificare nel web le pagine che non effettuano spam partendo da un piccolo insieme di pagine identificate come buone da un essere umano. Vediamo come è stato sviluppato l’algoritmo che svolge questo compito.

Iniziamo l’analisi dell’algoritmo supponendo per semplicità che le pagine seme vengano scelte in maniera casuale, in realtà non è così, ma torneremo su questo argomento in seguito. Una volta selezionate le pagine seme esse devono essere esaminate da un esperto umano per stabilire quali sono “buone” e quali “cattive”.

Per convenienza, nello studio che stiamo analizzando, questa fase viene equiparata ad una funzione “booleana” che restituisce un valore “0” se la pagina effettua spam ed un valore “1” se invece la pagina è buona. Questa funzione viene chiamata “Oracolo”. Usare la funzione Oracolo è costoso in termini di tempo e di risorse umane, perciò le chiamate alla funzione oracolo devono venire ridotte il più possibile.

Per poter identificare le pagine buone nel web senza dover invocare ogni volta l’oracolo gli ideatori del trutRank fanno affidamento su una osservazione empirica che sta alla base di tutto l’algoritmo: le pagine “buone” tendenzialmente non contengono link che puntano alle pagine “cattive”.

Le pagine cattive sono costruite per ingannare i motori di ricerca e non contengono informazioni utili agli esseri umani, per questo nessun webmaster che crea siti “buoni” ha una ragione per inserirvi dei link che vi puntano. In realtà nel web esistono alcuni link da pagine buone a pagine cattive perchè la quasi totalità di essi è ottenuta con l’inganno. Pensate ad esempio a dei siti di qualità che abbiano però delle chat non moderate o dei guestbook non controllati: queste aree potrebbero essere usate per effettuare spam inserendovi commenti contenenti dei link verso le pagine che si vogliono spingere. Oppure dei webmaster malintenzionati possono creare siti con contenuto valido, inserendovi dei link nascosti a pagine che effettuano spam, al solo scopo di ottenere backlink spontanei, per spingere queste ultime attraverso i siti “buoni” che sono serviti da esca (in queso caso i siti buoni sono chiamati “honey pots”, vasi di miele).

E’ importante capire che,a differenza dei siti buoni, quelli che effettuano spam non si linkano soltanto fra loro, anzi, molto spesso contengono numerosi link a siti di alta qualità che servono a valorizzare i contenuti dei “vasi di miele” e ad aumentare il punteggio hub nei vari motori di ricerca. Quindi per poter esprimere un giudizio su una pagina senza dover usare la funzione Oracolo si cerca di determinare la probabilità che una pagina sia buona basandosi sul grado di vicinanza, in termini di link, all’insieme “relativamente isolato” di pagine buone.

Una funzione “Trust” ideale dovrebbe fornire per ogni pagina del web la probabilità assoluta che essa sia buona, nella realtà questo è molto difficile da ottenere, ma per gli scopi che l’algoritmo si prefigge è sufficiente che svolga due compiti più semplici:

1) Ordinare le pagine contenute nell’indice del motore secondo la probabilità che queste siano buone. Per questo è sufficiente che i rapporti fra i valori di probabilità assegnati alle varie pagine siano corretti, anche se non sono calcolati in modo assoluto.

2) Introdurre un valore di soglia per il quale tutte le pagine che superano un certo valore di probabilità di essere buone vengono considerate buone. Questo serve ad individuare un sottoinsieme di pagine quasi sicuramente esenti da spam.

Per capire meglio l’algoritmo finale del TrustRank iniziamo ad esaminare alcuni approcci di base e, analizzandone i difetti arriviamo per gradi alla struttura finale della funzione che assegna il valore di “Trust” alle pagine.

Se all’inizio viene stabilito di voler usare la funzione oracolo un numero massimo “L” di volte, deve essere per prima cosa selezionato un insieme “S” composto da un numero “L” di pagine seme e poi usato l’oracolo su ciascuna di queste. Al termine l’Oracolo avrà identificato un sottoinsieme di pagine buone S+ ed uno di pagine cattive S-.

A questo punto la funzione “Trust” processa l’indice del motore di ricerca assegnando un valore 1 alle pagine appartenenti a S+, un valore 0 a tutte le pagine appartenenti ad S- e un valore 0,5 a tutte le pagine di cui non si sa ancora niente perché non appartengono all’insieme S esaminato dall’oracolo. Questa parte della funzione viene definita “Ignorant Trust” perché il valore di fiducia ottenuto per le pagine dell’indice non tiene ancora conto delle relazioni fra di esse.

Basandosi sull’osservazione fatta precedentemente, sul relativo “isolamento” delle pagine buone rispetto a quelle cattive, il sistema più semplice per propagare la fiducia dalle pagine seme alle altre è quello di assegnare un valore di 1 a tutte le pagine raggiungibili entro un numero M di passi (link) da una delle pagine seme.

Esaminando gli effetti causati da queso tipo di propagazione, però, si evidenzia subito un grosso problema: anche se non è certo che le pagine a cui viene assegnata la fiducia siano effettivamente buone questa viene comunque trasmessa interamente. Ciò comporta che, nel momento in cui l’algoritmo incontra uno dei rari link che puntano da una pagina buona ad una cattiva, la pagina cattiva acquista lo status di “buona” e può a sua volta propagare interamente la fiducia ad altre pagine che effettuano SPAM.

Gli autori dello studio hanno così ritenuto ragionevole assumere che più ci si allontana dall’insieme di pagine seme buone e più aumenta la probabilità di trovare un link ad una pagina cattiva; quindi hanno inserito nell’algoritmo un sistema cosiddetto di “trust attenuation”, per diminuire la quantità di fiducia che una pagina passa alle altre pagine, via via che ci si allontana dall’insieme originale delle pagine seme buone (S+). Questo tipo di meccanismo può essere realizzato in modi diversi.

Nella figura A vediamo uno schema chiamato “Trust dampening”. La pagina 1 appartiene all’insieme S+ di pagine insieme buone e contiene un link che punta alla pagina 2 alla quale passa un valore di fiducia β minore di 1. Alla pagina 3 che invece è raggiungibile direttamente dalla pagina 2 viene trasmesso un valore di fiducia uguale a β*β e così via. Nel caso in cui le pagine ricevano fiducia da link multipli, può essere assegnato ad esse il valore maggiore trasmesso da una singola pagina oppure una media di tutti i valori.

Il secondo schema, illustrato in figura B viene chiamato invece “Trust splitting” e si basa sul fatto che la cura con cui vengono aggiunti dei link nelle pagine web è spesso inversamente proporzionale al loro numero. Se una pagina buona contiene pochi link questi molto probabilmente punteranno a pagine a loro volta buone, mentre se la stessa pagina contiene centinaia di link è più probabile che alcuni di essi puntino a pagine cattive.

Quindi se una pagina buona ha un valore di fiducia T e contiene ω link ad altre pagine, ad ognuna di queste sarà trasmesso un valore di fiducia uguale a T/ω. In questo caso i punteggi che una pagina riceve da link multipli provenienti da pagina buone vengono sommati. In figura B la pagina 1, appartenente all’insieme di pagine seme buone S+, contiene due link in uscita, così assegna a ciascuna delle pagine a cui punta un valore pari a 0,5 (la metà della sua fiducia). Anche la pagina 2 appartiene all’insieme di pagine seme buone S+, ma contiene tre link in uscita, quindi trasmette a ciascuna delle pagine a cui punta un valore pari a 0,333 (un terzo della sua fiducia). La pagina 3 riceverà quindi una fiducia totale pari a 0,5+0,333=0,833.

Questi due approcci possono anche essere combinati. In questo caso, sempre riferendosi alla fig.B la pagina 3 riceve un punteggio di β*(0,5+0,333).

Per la formulazione finale dell’algoritmo di TrustRank gli autori hanno deciso di propagare la fiducia usando una versione “personalizzata” dell’algoritmo di PageRank dove, ovviamente, il valore calcolato per ogni pagina, ad ogni iterazione dell’algoritmo, non è il PR ma la fiducia. Il passaggio della fiducia dalle pagine seme buone avviene sostituendo il vettore risultante dal calcolo della funzione di “Ignorant Trust” (vedi sopra) al fattore di dispersione uniforme usato nel calcolo del PageRank. Questa soluzione è stata scelta perché, oltre ad essere funzionale, permette agli autori di sfruttare i risultati dei molteplici studi effettuati negli anni per ottimizzare il calcolo del PageRank, inoltre utilizzi personalizzati dell’algoritmo del PageRank che sfruttassero fattori di distribuzione non uniformi erano stati ipotizzati già anni fa da Page e Brin, vedi per esempio “The PageRank Citation Ranking Bringing Order to the Web” al capitolo 6.

Gli ideatori dell’algoritmo hanno effettuato degli esperimenti pratici utilizzando l’indice dei documenti indicizzati da Altavista nell’Agosto 2003. Allo scopo di ridurre i tempi e le risorse necessarie per effettuare i calcoli gli esperimenti sono stati fatti lavorando al livello dei siti e non dei singoli documenti. Utilizzando algoritmi già sviluppati da Altavista i miliardi di documenti appartenenti all’indice sono stati raggruppati in 31.003.946 siti web. Dopo il raggruppamento quando nei documenti che formano sito A vengono rilevati uno o più link che puntano verso documenti del sito B viene conteggiato un solo link fra i due siti.

Prima di poter procedere all’applicazione dell’algoritmo ed alla valutazione dei risultati ottenuti restava da sciogliere un nodo molto delicato: identificare il criterio migliore per la selezione delle pagine seme. L’insieme di pagine seme deve essere tale da permettere all’algoritmo di TrustRank di identificare altre pagine buone in modo efficace, inoltre deve rimanere relativamente piccolo per limitare le chiamate dell’oracolo. Vedremo nel prossimo articolo come gli autori dello studio hanno affrontato questo problema.

Le pagine seme del TrustRank

La composizione dell’insieme di pagine seme influisce in modo determinante sui risultati restituiti dall’algoritmo TrustRank, inoltre conoscere i criteri di selezione delle pagine seme considerate buone può essere molto utile.

Finora parlando dell’algoritmo del TrustRank abbiamo dato per scontato che le pagine seme, quelle cioè che devono essere valutate manualmente dall’oracolo, fossero scelte casualmente. In realtà la scelta di un insieme di pagine seme piccolo ed efficiente è fondamentale per un buon funzionamento di TrustRank

L’insieme delle pagine seme deve rimanere piccolo per limitare le invocazioni dell’oracolo che, come visto sopra, sono dispendiose sia dal punto di vista del tempo che da quello delle risorse economiche. L’efficienza dell’insieme invece si identifica nella capacità delle pagine selezionate di consentire una buona propagazione della fiducia, attraverso i loro link in uscita, verso il maggior numero possibile di pagine buone e rilevanti.

Come abbiamo la fiducia viene propagata dalle pagine seme buone ad altre pagine, per cui un buon criterio iniziale per la scelta delle prime è che abbiano un alto numero di link in uscita. Implementando questo tipo di ragionamento possono essere selezionate pagine che contengono molti link uscenti che puntano verso pagine che a loro volta contengano molti link uscenti e così via.

La formula che viene fuori è quasi identica a quella del PageRank con l’unica differenza che in questo caso il punteggio non dipende dal numero di link in ingresso, bensì da quello dei link in uscita. Per questo viene definita “Page Rank inverso”. La formula del PageRank inverso, in effetti, non garantisce la massima copertura di pagine dell’indice, ma questa sarebbe matematicamente molto più complessa da calcolare mentre l’applicazione dell’algoritmo del PageRank è stata ottimizzata e perfezionata nel corso degli anni diventando estremamente efficiente.

Il PageRank inverso non è comunque l’unico sistema possibile per la scelta delle pagine seme. Un diverso tipo di approccio potrebbe per esempio mettere già in discussione che ogni pagina contenuta nell’indice del motore sia egualmente importante e che sia indifferente attribuire il punteggio di fiducia ad una piuttosto che ad un’altra. Al contrario può essere considerato preferibile assegnare il punteggio di fiducia alle pagine che hanno maggiore probabilità di apparire in buona posizione rispetto alle ricerche, perché sono quelle che verranno selezionate più spesso dagli utenti.

Google ordina le pagine basandosi sia sul loro contenuto che sul valore di PageRank, potrebbe quindi essere una buona strategia assegnare i punteggi di fiducia alle pagine con più alto PageRank. Inoltre, visto che sperimentalmente si può affermare che spesso le pagine con alto PageRank sono fortemente collegate fra loro la fiducia verrebbe propagata a pagine che a loro volta hanno buone probabilità di essere visualizzate dagli utenti del motore di ricerca e così via.

Nell’esperimento condotto dagli autori dello studio questi due metodi di selezione sono stati comparati utilizzando un grafo “ridotto” del web dove erano comunque presenti degli esempi dei principali tipi di spam. Il sistema che ha permesso di selezionare il miglior insieme di pagine seme è risultato essere il PageRank inverso (anche se la differenza nella qualità dei due insiemi non era enorme) che è quindi stato usato per il resto dell’esperimento.

La prima fase per la selezione delle pagine seme da sottoporre alla valutazione dell’oracolo è quindi consistita nel calcolo del PageRank inverso di tutte le pagine dell’indice del motore utilizzando un fattore di attenuazione di 0,85 (un classico nella letteratura relativa al PageRank ) ed effettuando 20 iterazioni che hanno permesso di ottenere un risultato sufficientemente stabile (vedi la formula originale del PageRank).
Dopo aver ordinato i siti in ordine di Pagerank inverso sono state scelti i primi 25.000 e su questi sono state applicate ulteriori operazioni automatiche di filtraggio allo scopo di ottenere un insieme più ridotto.

Nei 25.000 siti selezionati è stata infatti immediatamente rilevata una massiccia presenza di cloni della intera directory DMOZ realizzati al solo scopo di simulare dei contenuti di qualità o di ottenere un elevato punteggio HUB.

La tattica seguita per eliminare questo tipo di siti è stata quella di rimuovere dall’insieme tutti i siti che non fossero presenti in nessuna delle maggiori web directory. Questo tipo di filtro ha ridotto l’insieme a circa 7900 siti e facendo dei controlli a campione su quelli eliminati è stato accertato che pochissimi siti di qualità erano stati scartati.

Dei 7900 siti rimanenti sono stati esaminati manualmente i primi 1250 in ordine di PageRank inverso (questi rappresentano l’insieme “S”, vedi “L’algoritmo del Trustrank”), il che equivale a dire che la funzione “oracolo” è stata chiamata 1250 volte.

La funzione oracolo ha stabilito che 178 siti fra quelli esaminati erano esenti da spam e quindi sono andati a formare l’insieme delle pagine seme buone (S+).

Un “particolare” molto Interessante da notare è che i criteri con cui l’oracolo ha giudicato i siti sono stati estremamente rigorosi, infatti i siti scelti non risultavano soltanto esenti da spam, ma erano anche siti la cui gestione poteva essee ricondotta in maniera chiara ed univoca ad una istituzione di qualche tipo (es. governativa, mlitare, universitaria).Questo ultimo accorgimento è stato preso per garantire longevità all’insieme delle pagine seme, ipotizzando che i siti gestiti da una qualche organizzazione (ed i loro contenuti) siano più “stabili” e coerenti a medio-lungo termine.

La duplicazione dei contenuti e il filtro antiduplicazione di Google

Di seguito un accorpamento di vari pezzi che ho ritrovato in giro sulla duplicazione dei contenuti, datato 2006, ma che fa luce su quello che è un annoso problema che affligge i motori di ricerca.

La duplicazione dei contenuti

Uno dei problemi principali che i motori di ricerca si trovano ad affrontare riguarda la duplicazione dei contenuti.

La duplicazione di un documento, inteso come pagina web, file di testo o multimediale, può derivare da diverse situazioni che si possono riassumere in 2 macro categorie: la duplicazione di contenuti come tecnica black hat seo, al solo fine di ingannare il motore ed aumentare la propria posizione nelle serp, e la legittima ridistribuzione delle informazioni: basta pensare alle citazioni, ad una hot news, o alle licenze creative commons.

Google, in particolar modo, ha sviluppato un algoritmo per la determinazione di contenuti duplicati e simili, che sentiamo spesso nominare come “filtro antiduplicazione“: di seguito vengono riportate le traduzioni del brevetto di Google sulla duplicazione dei contenuti.

STORIA DELL’INVENZIONE 

La presente invenzione concerne il recupero e il management delle informazioniin generale. Più specificatamente, l’invenzione riguarda la scoperta, ed eventualmente la rimozione, di contenuti e informazioni dupicati o simili

A seguire il termine documenti potrebbe essere diversamente interpretato a potrebbe includere contenuti come pagine webfile di testo, file multimediali, strutture di link, etc. Così, il termine potrebbe notificare quando documenti simili sono rilevati, esatti documenti duplicati saranno rilevati come conseguenza.

Rilevare contenuti duplicati e simili ha molte potenziali applicazioni. Per esempio, i documenti duplicati o simili possono indicare infrazioni di copyright e plagi. Un importante applicazione di rilevazione di contenuti simili appartiene al contesto del recupero e dell’archiviazione delle informazioni.

Esistono efficienti tecniche per rilevare i documenti duplicati. Rilevando quando e se i documenti sono duplicati o simili è molto difficile, specialmente in grandi raccolte di documenti come il Web.

Le fonti per contenuti duplicati e simili sono introdotti nella sezione 1.2.1. I problemi che questi documenti duplicati o simili sollevano, sia per gli utenti finali che che per le entità che li assistono sono descritti in 1.2.2. Infine, nella sezione 1.2.3 vengono introdotte le tecniche usate per la rilevazione di documenti duplicati e simili tra grandi collezioni di documenti.

  • Fonti di duplicazione e documenti simili
  • Problemi sollevati da contenuti duplicati e simili
  • Tecniche conosciute per scoprire documenti duplicati e simili
  • Filtro antiduplicazione: indice dell’invezione

Fonti di duplicazione e documenti simili

Su Internet, il World Wide Web può includere gli stessi documenti duplicati in differenti forme e in differenti posti. (naturalmente, altri network, oppure sistemi “stand alone” possono avere documenti duplicati). Vediamo le fonti di queste duplicazioni.

Primo, alcuni documenti sono “specchiati” in differenti siti nel Web. Questo specchiare è usato per alleviare potenziali problemi quando tanti utenti cercano di accedere allo stesso documento nello stesso momento, e/o per minimizzare eventuali latenze del network (es. utilizzando copie cache di pagine web localmente) 

Secondo, alcuni documenti potrebbero averedifferenti versioni con differenti formattazioni. Per esempio, un dato documento può avere un “piano di testo” e una versione HTML cosacche gli utenti possono visualizzare o scaricare il contenuto nella forma che preferiscono. Così come sempre più differenti
strumenti (PC, cellulari, etc) sono usati per accedere a Internet, un dato
documento può avere differenti versioni con differenti formattazioni per ogni formato (solo testo, testo più media, etc).

Terzo, i documenti sono spesso “prepended” o allegati con informazioni circa la loro locazione nel Web, la data, la data di ultima modifica, la versione, il titolo, il percorso gerarchico di classificazione (es. una pagina Web può essere classificata sotto più categorie dello stesso sito Web), etc. Esempio illustrato nella sezione 4.4 (figs13). 

Quarto, in alcuni casi un nuovo documento viene generato
da un documento esistente usando consistenti rimpiazzi di parole.
 Per esempio, un sito Web può presentare
diversi “brand” per differenti utenti cambiando soltanto determinate parole.Infine, alcune pagine Web aggregano o incorporano contenuti da altre fonti sul Web.

Problemi sollevati da contenuti duplicati e simili

Duplicati e documenti simili sollevano potenziali problemi sia per le persone che accedono all’informazione (es. dal Web) sia per le entità che aiutano le persone ad accedere alle informazioni desiderate (es. i motori di ricerca). Vediamo questi problemi.

Sebbene la gente continua a usare i computers per entrare, manipolare e immagazzinare informazioni, in visione dello sviluppo dell’immagazzinamento dei dati, dello sviluppo di Internet, e dei sistemi di link e collegamenti incrociati che riportano un informazione (es. usando collegamenti con link ipertestuali) le persone useranno i computer per accedere a una vastità di informazioni sempre
crescente.

I motori di ricerca sono stati sviluppati per aiutare gli utenti a trovare le informazioni desiderate. I motori di ricerca, tipicamente, cercano contentuti o “siti Web” archiviati conseguenti a una certa ricerca. In risposta a una determinata ricerca, viene proposta un lista ordinata in base al valore attribuito al documento, che tipicamente include brevi descrizioni del contenuto, così come collegamenti testuali (es. testi con associate URL) ai contenuti. Il sistema di ordinamento è tipicamente basato sulla corrispondenza delle parole cercate nella ricerca e le parole che appaiono nel contenuto.

Dal punto di vista degli utenti, documenti duplicati o simili sollevano problemi. Più specificatamente, quando gli utenti sottopongono una ricerca al motore, la maggior parte di loro non vuole collegamenti a pagine Web che hanno una grande ridondanza di informazioni. Per esempio, i motori di ricerca rispondono a una ricerca fornendo un gruppo di dieci risultati. Se sono fornite pagine con contenuti duplicati, molti tra i risultati di un gruppo potrebbero includere gli stessi contenuti. Da questo l’esigenza di una tecnica per evitare che il motore fornisca, come risultato di una ricerca, collegamenti a pagine Web che hanno contenuti duplicati.

La maggior parte dei motori di ricerca assolvono a tre funzioni principali:

  • esplorazione del Web
  • indicizzazione dei contenuti
  • rispondere a una data ricerca usando l’indice
    dei contenuti per generare i risultati.

Data l’enorme vastità di informazioni disponibili, queste 3 funzioni sono automatizzate a una grande estensione. Mentre l’operazione di esplorazione assocerà parole o frasi con un documento (es. una pagina Web), l’operazione di indicizzazione assocerà documenti (es. pagine Web) con parole o frasi. L’operazione di ricerca allora:

  • usa l’indice per trovare documenti (es. pagine Web) contenenti varie parole di un certa ricerca
  • valorizza e ordina i documenti trovati in accordo ad altre implementazioni

Ricordiamo che il Web può includere gli stessi documenti duplicati in differenti forme o in differenti posti nel Web. Per esempio, come introdotto in 1.2.1 sopra, i documenti possono essere “specchiati” in diversi siti nel Web, i documenti possono avere un numero di diversi formati cosi che gli utenti possano visualizzare o scaricare il contenuti nella forma che preferiscono, i documenti possono essere proposti in differenti versioni con diverse informazioni allegate, alcuni documenti possono essere stati generati da altri con un consistente cambiamento di parole, e alcuni documenti possono essere aggregati e incorporati da un’altra fonte nel Web. Potrebbe essere desiderabile eliminare questi documenti duplicati e questi simili.

A parte l’eliminazione di documenti duplicati e simili per andare incontro alle esigenze e alle aspettative degli utenti, l’eliminazione di documenti duplicati e simili è desiderabile dai motori di ricerca per:

  1. ridurre lo spazio richiesto (esempio per gli indici e le strutture di dati derivati dagli indici)
  2. ridurre le risorse necessarie per i processi di indicizzazione, ricerca, etc.

In visione di questi obiettivi sono necessarie diverse tecniche per scoprire (ed eliminare) documenti simili

Tecniche conosciute per scoprire documenti duplicati e simili

Alcune precedenti tecniche per scoprire documenti duplicati e simili implicano la generazione di alcuni elementi dei documenti chiamati “fingerprints” (impronte digitali) (esempio paragrafi, sentenze, parole o targhette, insegne (per esempio l’accavvallamento stirato di parole consecutive)).

Guardiamo per esempio gli articoli:

  • Z. Broder, “On the Resemblance and Containment of Documents,” Proceedings of Compression and Complexity of Sequences 1997, pp. 21-27, IEEE Computer Society (1988);
  • S. Brin et al., “Copy Detection Mechanisms for Digital Documents,” Proceedings of the ACM SIGMOD Annual Conference, San Jose 1995 (May 1995)

Alcuni o tutti i “fingerprints” possono essere usati per determinare documenti duplicati o simili. In maniera più specifica, due documenti potrebbero essere considerati simili se condividono più di un predeterminato numero (minimo due, generalmente piu’ alto) di “fingerprints”.

Per un grande insieme di documenti (per esempio i miliardi di documenti che vengono indicizzati dai motori di ricerca) questa determinazione diventa piuttosto costosa, sia letteralmente che in termini di spazio per l’archiviazione.

Guardiamo, per esempio, l’articolo:

  • M. Fang et al., “Computing Iceberg Queries Efficiently,” Proc. 24.sup.th Int’l. Conf. On Very Large Databases, pp. 299-310 (1998)

Il problema non è di facile soluzione. Per esempio, non è in special modo utile “pre-processare” le rappresentazioni di tali documenti usati nelle tecniche Broder per eliminare da ulteriori considerazioni, come la conoscenza dei “fingerprints”, per essere unica.

Questo perché tutti i documenti con “fingerprints” non unici (come i documenti rimasti dopo il pre-processamento) possono, tuttavia, avere documenti non simili. Questo necessita, quindi, di una migliore tecnica per la determinazione di documenti duplicati e simili.

Filtro antiduplicazione: indice dell’invezione

Il brevetto sul filtro anti duplicazione che vi presentiamo può determinare documenti simili da:

1) per ogni documento, generando i “fingerprints

2) determinando documenti simili basandosi sui “fingerprints”

In una incorporazione, i “fingerprints” possono essere pre-processati per eliminare quelli che occorrono solamente in un documento.

In un’altra, soltanto i rimanenti “fingerprints” potrebbero essere usati nella determinazione di documenti duplicati.

L’atto della generazione dei “fingerprints” per ogni documento può essere compiuto:

1) estraendo parti (come le parole) dai documenti,

2) hashing, ognuna di queste parti estratte per determinare quali da un pre-determinato numero di liste

3) per ognuna di queste liste, generando dei “fingerprints”


In risposta alla determinazione di documenti duplicati, la presente invenzione può funzionare anche per eliminare i documenti duplicati. 

La presente invenzione può funzionare per generare dei clusters di documenti simili, nei quali usare una proprietà transitiva. Ogni documento può avere un identificativo per l’identificazione del cluster al quale è associato. In questa alternativa, in risposta a una data ricerca, se due candidati risultano documenti dello stesso cluster e se i due candidati risultano documenti corrispondenti alla ricerca, solo quello dei due che è ritenuto più rilevante (per esempio da una alto valore di PageRank, oppure se è più recente) viene restituito dalla ricerca. 

Nel campo dei motori di ricerca, la presente invenzione può essere usata anche durante le attività di crawl per accelerarne il processo e alleggerire la banda disponibile non archiviando documenti simili, pagine o siti, come determinato dalla scoperta dei documenti durante un crawl precedente.

Brevetto Google Comportamenti, Preferenze, Raccomandazioni

Ultimamente in vari forum e SEO blog si è tornato a parlare di “users behavior”, comportamento degli utenti , quindi scelte e preferenze di un sito piuttosto che un altro da una lista di risultati, tempi di accesso alla risorsa, e di come/se l’aumento del traffico, delle visite e degli utenti di un sito possano aiutare il sito stesso a meglio posizionarsi tra i risultati di una certa ricerca.

È di qualche settimana fa, per esempio l’esperimento di Stuart, Traffic VS Sandbox , Traffico contro Sandbox, un test che mira a valutare se l’effetto di un grosso aumento di traffico, rintracciabile da Google, possa vincere l’annosa anomalia dell’ effetto Sandbox; anomalia in quanto, come scritto da Matt Cutts , l’effetto Sandbox sarebbe un’anomalia che l’algoritmo di Google incontra con l’indicizzazione di un nuovo sito, in alcune situazioni. Un effetto non voluto generato dall’algoritmo ma non risolto, visto che “salvaguarda” il motore.

In una recente discussione sul Forum di Posizionamento sui Motori di Ricerca GT, alcuni forummisti affrontano l’importanza crescente dei “ traffic pattern ”, gli schemi di traffico che Google può riconoscere e valutare con l’algoritmo sui Dati Storici

Google effettua aggiornamenti legati a Dmoz, penalizzando i siti che usano i dati di ODP ed inevitabilmente si torna a studiare il TrustRank ed a parlare di siti HUB.

Ed ecco che qualche giorno fa, esattamente il 18 aprile come riporta il brevetto, Google brevetta ufficialmente un nuovo algoritmo dal titolo:

Sistemi e metodi per ricercare e raccomandare oggetti da un magazzino di informazioni categoricamente organizzato.

Dall’introduzione del Brevetto:

” Un sistema di “ricerca e raccomandazione” impiega le preferenze ed i profili di utenti, individuali e di gruppo, all’interno di una comunità di utenti, cosi come pure le informazioni derivate dagli “indicatori di contenuto” categoricamente organizzati per accrescere le ricerche in Internet, ri-posizionare i risultati delle ricerche , e fornire raccomandazioni per quegli oggetti basati sull’oggetto di ricerca iniziale.

Il sistema di “ricerca e raccomandazione” opera nel contesto di gestione degli “indicatori di contenuto”, che archiviano gli indicatori di contenuto di utenti (alcuni dei quali potrebbero essere pubblicati o condivisi per usi di gruppo) su un database centrale di “indicatori di contenuto” connesso a Internet.

Il sistema di “indicatori di contenuto” condivisi è implementato come un programma distribuito, porzione del quale operano sul terminale dell’utente e altre che lavorano sul sistema centrale del database degli indicatori. Un “indicatore di contenuto” di un utente è organizzato in accordo con una gerarchia locale, a tema, e categorica.

L’organizzazione gerarchica è usata per definire un contesto rilevante entro il quale gli oggetti restituiti vengono valutati e ordinati. “

Leggiamo dagli obiettivi

Quello che si cerca è un metodo per ricercare un magazzino d’informazioni, caratterizzato come un oggetto spaziale gerarchico, il metodo comprende le fasi di:

  1. stabilire un insieme di indicatori di contenuto condivisi, ognuno dei quali corrisponde a un oggetto;
  2. ricevere almeno una parola chiave da cercare
  3. cercare almeno una porzione dell’insieme di indicatori di contenuto condivisi
    in accordo con la parola chiave cercata
  4. derivare almeno una parola chiave addizionale dall’insieme, associata alla parola chiave cercata
  5. incrementare la query con almeno una parola chiave addizionale derivata dall’insieme
  6. recuperare un gruppo di oggetti che corrispondono all’argomento cercato
  7. identificare un contesto all’interno del gruppo di oggetti
  8. ordinare il gruppo di oggetti recuperato basato su corrispondenza computata con il contesto
  9. ordinare il gruppo degli indicatori di contenuto recuperati in ordine di valore
  10. l’ordine è determinato da un insieme pesato di “user metrics” di unità di misura dell’utente, dove l’insieme viene scelto da un gruppo consistente di misure, come la misura della popolarità, la misura della frequenza di accesso, la misura di accessi recenti e la misura della struttura dei link.

Il campo dell’invenzione

L’invenzione si riferisce al campo della ricerca e visualizzazione delle informazioni, e più in particolare a sistemi e metodi per abilitare ricerche e raccomandazioni di documenti in un insieme attraverso l’uso di segnalibri condivisi in una comunità di utenti.

Approfondimenti

Google, brevetto sui dati storici

Information retrieval based on historical data

Dati Storici rappresentano tutti quei dati relativi ad analisi di tipo storico che i motori di ricerca possono analizzare per attribuire al sito la posizione più indicata tra i risultati delle ricerche: dall’anzianità del dominio alla variabilità nel trend degli aggiornamenti.

Questo “sistema di valorizzazione” consiste nell’ esaminare diversi aspetti nell’ archiviazione di dati di tipo “storico“, relativi cioè ai cambiamenti e gli aggiornamenti nel tempo di un documento.

L’ invenzione che vi andremo a descrivere si riferisce generalmente ai sistemi di reperimento delle informazioni e, più in particolare, ai sistemi e ai metodi usati per generare i risultati di una ricerca basati, almeno in parte, sui dati storici associati a documenti rilevanti.

Idealmente, un motore di ricerca , in risposta a una data ricerca di un utente, fornirà i risultati più attinenti e più relativi ai termini ricercati.

Per raggiungere lo scopo esso può monitorare e archiviare informazioni reperite da un documento di diverso tipo e in diversi modi Una categoria di motori di ricerca identifica i documenti rilevanti per una certa ricerca basandosi sulla comparsa nel documento dei termini associati alla ricerca.

Un’ altra identifica i documenti rilevanti per una certa ricerca usando altri fattori oltre, o in addizione, alla presenza dei termini ricercati nei documenti: uno di questi fattori, per esempio, usa le informazioni associate ai link uscenti o entranti di un documento per determinarne l’ importanza ai fini della ricerca.

L’ importanza di questo documento, la grande quantità di informazioni in esso contenute e la difficoltà di comprensione e di correlazione di tutti gli algoritmi proposti, testimonia come raggiungere un buon posizionamento sui motori di ricerca risulti un’ operazione delicata, con tempi di risposta molto lunghi, in cui le variabili da analizzare e a cui attribuire significati sono tante e complesse e i cui legami molteplici.

Tutte le ipotesi e le teorie sviluppate fino ad ora nel campo del Search Engine Optimization da SEO professionisti e non, potrebbero trovare in questo documento, quindi, una fonte ufficiale di informazioni. Infatti il 31 Marzo 2005 Google ha registrato un brevetto dal titolo Information retrieval based on historical data Reperimento di informazioni basato su dati storici ) presso la US Patent & Trademark Office, in cui nella sezione principale del documento intitolata Exemplary history data , ci sono 99 paragrafi, suddivisi in 14 sub-categorie, in cui vengono descritti molteplici algoritmi eventualmente usati per l’ archiviazione e la restituzione di dati e informazioni.

Brevettati ufficialmente il 31 Marzo 2005 come si può leggere all’ inizio del documento, il brevetto sui dati storici risale al 31 Dicembre 2003 e potrebbe essere, quindi, già parte integrante degli algoritmi di funzionamento di Google e spiegare così alcune teorie in campo SEO, come quella relativa all’ ” effetto sandbox ” o sulla nascita del nuovo TrustRank.

La data iniziale dei documenti

La Data Iniziale può essere vista come il “primo contatto” tra il motore di ricerca e il documento. E’ uno dei parametri fondamentali sul quale si basano molte implementazioni diverse dell’algoritmo: il motore di ricerca, infatti, per poter eseguire le diverse analisi necessarie al reperimento dei dati storici e comparare i dati relativi a periodi diversi, deve attribuire al documento una “data di nascita” dalla quale cominciare a rilevare cambiamenti e aggiornamenti.

Nel brevetto, Google, ci indica l’utilizzo di diversi modi usati dal suo motore di ricerca per reperire la Data Iniziale di un documento:

– attraverso l’esplorazione, cioè con il primo passaggio dello spider nel documento
– attraverso la segnalazione del documento al motore di ricerca da fonti esterne, come ad esempio il modulo di segnalazione Add URL dello stesso Google
– attraverso una combinazione delle prime due tecniche
– attraverso l’esplorazione del web, quando lo spider del motore di ricerca trova per la prima volta un link al documento.

In altre implementazioni dell’algoritmo poi, ci sono anche altri modi di reperire la Data Iniziale: alcuni esempi li possiamo leggere nel Brevetto, ma ci sono anche altre tecniche non specificatamente menzionate, o combinazioni di esse, che possono essere usate per determinare la data iniziale del documento. Alla luce di questo, soffermiamoci sul significato e sulle possibili applicazioni del concetto di Data Iniziale.

La Data Iniziale di un documento è necessaria al motore di ricerca per stabilire quanto sia “vecchio” o “giovane” un documento: per misurare l’ “anzianità” di un documento in un determinato momento, Google nel suo brevetto fa riferimento alla Data Iniziale dello stesso. A seconda, poi, dell’anzianità del documento, e anche in base al settore di competenza dello stesso, ma lo vedremo più avanti, può essere implementato un sistema di valorizzazione che consideri più importante un documento più anziano a dispetto di uno più giovane.

In un esempio del Brevetto, Google indica la corrispondenza del concetto di Data Iniziale con i backlink di un documento: infatti, partendo dall’assunto che un documento con una Data Iniziale abbastanza recente non riceva un numero significante di link da altri documenti rispetto ad un documento più vecchio a cui puntano molti più link, possiamo facilmente intuire che il documento più anziano sia considerato più importante e di conseguenza venga maggiormente valorizzato.

D’altro canto, introducendo il concetto di “ritmo di crescita” dei backlink, cioè quanti backlink riceve un documento in un determinato periodo di tempo a partire dalla Data Iniziale, quanto appena detto sopra potrebbe non essere più vero, ed un documento più giovane con un ritmo di crescita maggiore potrebbe avere più valore di un documento più anziano con più link ma con un ritmo di crescita minore. Questo a testimoniare il fatto che un documento “anziano” ha maggiori probabilità di contenere informazioni “obsolete” rispetto ad un documento più giovane.

In questo modo, il ritmo di crescita dei backlink di un documento può essere monitorato dal motore di ricerca ed usato anche come fattore di determinazione di probabile spam al motore stesso e il concetto di ritmo di crescita diventa quindi un concetto molto importante al fine di “pesare” i backlink di un documento.

Il concetto “ritmo di crescita“, appena descritto per i backlink, assume, quindi, un valore molto importante: ritroveremo in altre sezioni il “ritmo di crescita” di qualcosa, cioè quanto un determinato fattore viene implementato o aggiornato in un determinato periodo di tempo, e vedremo quanto questo concetto sia importante per la corretta lettura di tutto il Brevetto.

L’aggiornamento dei contenuti

L’aggiornamento, o il cambiamento, dei contenuti di un documento o di un sito web possono essere dei fattori determinanti per il posizionamento sui motori di ricerca.

Il motore di ricerca, grazie allo spider che analizza il web nella sua continua ricerca di informazioni, riesce a monitorare gli aggiornamenti, e l’entità di essi, effettuati sul documento o su parti di esso, a partire dalla sua data iniziale o in un determinato lasso di tempo: lo spider archivia, poi, i dati analizzati in una memoria temporanea (la versione cache di Google) in modo da controllare più facilmente se al documento sono apportate modifiche e aggiornamenti.

Nel Brevetto sul reperimento di Dati Storici, Google ci indica anche in che modo potrebbe rilevare e dar peso agli aggiornamenti effettuati: una funzione, che potrebbe essere una somma o una somma pesata, in cui vengono messi in relazione due fattori: uno legato alla frequenza degli aggiornamenti, che indica al motore di ricerca “quanto spesso” viene aggiornato un documento, e uno legato alla quantità degli aggiornamenti effettuati.

La frequenza con cui un documento viene tenuto aggiornato nel tempo può essere determinata dal motore di ricerca facendo uso di “copie” del documento che vengono archiviate nel database del motore e possono essere usate per effettuare analisi comparative in un determinato periodo.

Per determinare, poi, la quantità degli aggiornamenti effettuati, Google nel suo brevetto ci indica diversi fattori che possono essere esaminati per assegnare un punteggio legato alla quantità degli aggiornamenti: dal numero delle nuove pagine in un lasso di tempo, al rapporto di queste ultime con il totale delle pagine contenute dal documento a partire dalla sua Data Iniziale…ma non solo!!

Dal numero dei fattori riportati dal Brevetto possiamo facilmente renderci conto della necessità di aggiornare un documento con contenuti nuovi e validi; infatti la quantità degli aggiornamenti può essere a sua volta una funzione di diversi fattori pesati in maniera differente.

Google può determinare il “tipo” di agggiornamento effettuato e attribuirgli un peso diverso a seconda che il tipo di aggiornamento effettuato sia considerato “importante” o no. Per esempio i cambiamenti di contenuti come commenti, pubblicità, script ed elementi di navigazione possono avere un peso relativamente piccolo od essere addirittura ignorati da Google nella determinazione della quantità degli aggiornamenti.

Dopo aver descritto la frequenza e la quantità degli aggiornamenti, passiamo ad analizzare i vari modi di utilizzo di questi due parametri. Ritroviamo il concetto di “ritmo di crescita” (già visto nella Data Iniziale per il numero di link entranti in un certo documento) applicato agli aggiornamenti o cambiamenti dei contenuti di un documento o di un sito. Il ritmo di crescita degli aggiornamenti in un dato periodo può essere rilevato, esaminato e messo a confronto col ritmo di crescita riferito ad un altro periodo (precedente) per determinare eventuali accelerazioni o decelerazioni negli aggiornamenti dei contenuti: per esempio, a quei documenti in cui viene rilevato un incremento nel ritmo di crescita e nei quali l’entità degli aggiornamenti supera un certo valore, potrebbe essere attribuito un punteggio maggiore rispetto ad altri documenti che non vengono aggiornati, e rimangono statici nel tempo, o che subiscono leggeri aggiornamenti.

Per determinare tutti questi fattori e tenere sotto controllo il ritmo di crescita degli aggiornamenti e la loro entità, il motore di ricerca deve usare fisicamente e materialmente molte risorse: dallo spazio fisico per la memorizzazione dei dati, alle risorse di banda per l’analisi e il rilevamento dei questi ultimi.

Finchè queste risorse sono a disposizione può essere analizzato e archiviato l’intero documento, al fine di rilevarne gli aggiornamenti, ma, in alcune situazioni, queste risorse possono essere momentaneamente insufficienti per una corretta analisi e archiviazione dei dati: in questo caso il motore di ricerca usa archiviare delle “copie” o “rappresentazioni” del documento, invece del documento stesso, e monitorare queste ultime per determinarne gli aggiornamenti. Queste rappresentazioni possono essere delle “signature” (letteralmente firme) di un documento, o un “vettore di dati” in cui sono memorizzati i termini ritenuti più importanti o più frequentemente ricorrenti nel documento.

Con lo stesso tipo di analisi effettuate per determinare l’aggiornamento dei contenuti di un documento, il motore di ricerca può generare, sempre sulla base dei contenuti di un documento, un certo “codice” di somiglianza, in cui memorizzerà una serie di termini o una copia intera del documento, e monitorare questo codice per rilevare gli aggiornamenti effettuati. Lo stesso “codice di somiglianza” può essere usato, poi, dal motore di ricerca, per rilevare eventuali duplicazioni e simili di un documento. A tal proposito, nel brevetto sui dati storici, è indicato che per documenti molto grandi, che includono per esempio parti di documento o documenti interi appartententi a più individui, il punteggio che il motore di ricerca genera può essere assegnato a ciascuno dei sub-documenti, che è aggiornato dal singolo individuo ma che fa parte a tutti gli effetti del “macro” documento.

Alla luce di quanto visto, la frequenza e la quantità degli aggiornamentideicontenuti di un documento, o di un sito internet, possono essere due parametri fondamentali elaborati dal motore per il corretto posizionamento del sito sui motori di ricerca; aggiornare spesso i contenuti di un sito, o di un documento, è sicuramente un fattore da non sottovalutare per ottenere un corretto posizionamento. Il motore, infatti, in generale preferisce siti che aggiornano spesso, e in grande quantità, i propri contenuti, tranne in alcuni casi in cui, per alcune ricerche, possono essere favoriti documenti che non sono stati recentemente aggiornati rispetto al altri aggiornati più di recente.

Le analisi delle ricerche

Le ricerche effettuate dagli utenti nel motore di ricerca e le loro scelte nella pagina dei risultati, possono essere analizzate ed esaminate dal motore e considerate ai fini del posizionamento del documento e del sito.

Una delle intuizioni nel settore del posizionamento sui motori di ricerca, quando non c’era ancora una fonte ufficiale come il Brevetto presentato da Google sul reperimento dei Dati Storici, era quella di pensare che il motore di ricerca considerasse le preferenze degli utenti nella serp associata ad una data ricerca.

Come possiamo ora verificare l’intuizione era valida …ma non assolutamente esaustiva: alcuni esasperarono questo concetto e si generò così una sorta di leggenda metropolitana tale da far cercare e clikkare il sito da posizionare tra le pagine dei risultati forniti dal motore per spingerlo in alto nei risultati. Questa pratica, smentita dalla considerazione del motore degli “accessi unici” ad un documento e associati poi al cambiamento della versione Cache del documento, trova oggi una definizione ufficiale.

Come descritto dal Brevetto di Google, infatti, l’analisi delle ricerche diventa uno dei parametri fondamentali nel reperimento di dati di tipo storico; uno dei primi fattori da analizzare riguarda proprio la quantità di volte nella quale un documento è selezionato nel tempo nei risultati di una ricerca.

Oltre ad associare la preferenza dell’utenza nei risultati di una ricerca, nei confronti di un documento piuttosto che un altro, il motore potrebbe capire, analizzando le ricerche effettuate in un determinato periodo e valutando un particolare insieme di termini, se i termini e il documento sono collegati ad un particolare evento molto popolare od ad un argomento particolarmente “caldo” che catalizza l’attenzione di molti per un certo periodo, e attribuire un valore maggiore ai documenti associati a tali termini. Uno dei modi che Google utilizza per capire se un determinato argomento sia “caldo” è quello di analizzare eventuali cambiamenti nel numero dei risultati associati ad alcune ricerche: un significativo incremento può indicare, infatti, che l’evento associato ad un particolare set di termini (parole chiave), sia “sulla bocca di tutti” e, di riflesso, incrementare il valore dei documenti associati a quelle ricerche.

Altro fattore, da tenere in considerazione sull’analisi delle ricerche, è legato a quelle ricerche che non subiscono variazioni nel tempo, ma che portano, invece, a risultati variabili. L’esempio, sul brevetto di Google, è quello relativo a una ricerca legata a risultati sportivi: in un determinato periodo di tempo è molto probabile che i documenti relativi ad una particolare squadra risultino più “caldi” e più clikkati; in questo caso il motore può monitorare ed analizzare le ricerche effettuate dagli utenti e valorizzare di conseguenza i documenti associati.

Focalizziamo ora l’attenzione ai riferimenti legati ad analisi temporali: ritroviamo, come ritroveremo ovunque sul brevetto, dei riferimenti “impliciti” (nel tempo, in un determinato periodo di tempo) alla Data Iniziale o altri tipi di date indispensabili al motore di ricerca per effettuare le sue analisi sui Dati Storici; di fondamentale importanza è l’introduzione, in relazione ad una analisi storica, del concetto di “staleness” di un documento: un parametro che il motore associa ai documenti che compaiono nei risultati di una ricerca e che indica quanto il documento è considerato “stantio”, superato, obsoleto, per quella data ricerca.

La staleness risulta essere, quindi, un altro parametro da considerare nel posizionamento sui motori di ricerca. Per rilevare la staleness di un documento, Google può basarsi, oltre ai fattori considerati fin qui sulle analisi delle ricerche, su altri fattori come:

  • la Data Iniziale e le rilevazioni temporali ad essa collegate;
  • l’aggiornamento dei contenuti e il loro ritmo di crescita;
  • la crescita del numero di backlink, forward link e anchor.

Per alcune ricerche particolari, i documenti più recenti sono più favoriti: basti pensare a “Last minute”: un utente preferirebbe sicuramente trovare la versione più recente o l’ultima proposta, piuttosto che un documento con informazioni vecchie. In base alle preferenze degli utenti su determinate ricerche e ai documenti da loro selezionati, quindi, il motore di ricerca può imparare per quali ricerche sono più importanti i documenti più recenti e per quali ricerche sono più importanti i documenti più stantii, e aggiustare di conseguenza il loro valore basato sull’analisi delle ricerche.

I link

Prima di rilasciare il Brevetto sul reperimento di informazioni basato sui Dati Storici , infatti, Google usava già da tempo il Page Rank (PR), un algoritmo che attribuisce un valore al documento basandosi soprattutto sui fattori esterni al sito stesso come la Link Popularity (LP): quest’ultima risulta così essere uno dei parametri fondamentali che determinano il posizionamento sui motori di ricerca. La Link Popularity descrive la popolarità del documento, quanti link, e di che tipo, riceve un documento o un sito.

La logica è quella per cui un documento acquisisce importanza in base a quanti link riceve da altri documenti: ovviamente un documento linkato da molti altri documenti viene considerato più importante di uno poco linkato o addirittura isolato.

Ultimamente, Google, ha rilasciato il Trust Rank (TR), un nuovo Brevetto che attribuisce ancora più importanza alla LP, pesando ogni link a partire da un certo numero di grossi siti (hub) che certificano la qualità di un documento ( DMOZ , Yahoo Directory ). Il TR nasce, come altri brevetti, per garantire la buona qualità delle serp e combattere la produzione di massa di link artificiali, con link farm (link factory), e combattere quindi lo SPAM.

La produzione di massa di link, al solo fine di posizionare un documento nei risultati del motore di ricerca, è considerata da Google una tecnica illecita, causa di dubbia qualità delle serp, e quindi combattuta col Trust Rank (Trust = fidato).

Nel Brevetto sui Dati Storici di Google esistono molti criteri basati sui link , da considerare ai fini di un più preciso calcolo della LP e forse anche del TR: infatti, uno dei fattori determinanti, tra i vari criteri adottati sui link, è l’introduzione di un tipo di analisi che dipenda dai pesi assegnati ai link: ogni link può essere valutato, pesato, attraverso l’utilizzo di diversi fattori.

Un link può essere pesato:

  • in base ad una funzione che determini la freschezza del link;
  • ad una funzione che sia a sua volta una “somma di pesiâ€? attribuiti
    al documento valutando diversi fattori;
  • in base alla legittimità e all’autorità del
    sito che contiene i link;
  • in base a diverse combinazioni di quanto detto finora.

La data di apparizione di un link

Il primo fattore da considerare per l’analisi dei Dati Storici basati sui link è relativo alla date di apparizione di nuovi link ai documenti e alle date in cui un link esistente scompare.

In questa parte del Brevetto, come già visto nell’ Aggiornamento dei Contenuti per la misura di parametri che si basano sulla Data Iniziale dei documenti , saranno molto importanti, per la corretta interpretazione del brevetto, i fattori relativi al tempo o al ritmo con cui cresce (o decresce) un determinato fattore.

La data di apparizione di un link, come la data iniziale o la data in cui si effettua un aggiornamento, diventa indispensabile per le analisi effettuate dal motore per valutare i dati storici dei link.

La data di apparizione di un link può essere la data in cui il motore trova il link per la prima volta, oppure potrebbe corrispondere con la data iniziale del documento o una delle date di aggiornamento in cui è comparso il link stesso.

La comparsa e la scomparsa di un link a un documento possono essere viste dal motore di ricerca come fattori che testimoniano rispettivamente la freschezza o la staleness di un documento.

In relazione poi, all’apparizione o alla scomparsa di un link, Google può analizzare la variazione nel tempo dei link che puntano a un documento e in questo rilevare quale sia la tendenza del documento: con che frequenza un documento acquista backlink. Un ritmo crescente nel numero e nella velocità di apparizione di nuovi link in un periodo di tempo, può segnalare al motore di ricerca che il documento sia nuovo, fresco, o comunque mantenuto aggiornato, ed essere meritevole, quindi, di maggior valorizzazione.

La variazione può essere monitorata comparando il numero di nuovi link negli ultimi n giorni col numero di link a partire dalla Data Iniziale del documento, o a partire da una delle date in cui si è aggiornato significativamente il documento dando vita così a una funzione di distribuzione delle età associate alla comparsa di un link che punta a un documento.

Questa funzione assumerà valori differenti a seconda se il documento venga o no aggiornato frequentemente e il motore di ricerca può analizzarla come ulteriore fattore per determinare la freschezza o la stalenessdi un documento.

Alla luce di quanto visto, la frequenza e la quantità del numero di nuovi link a un documento o a un sito internet, possono essere due parametri fondamentali elaborati dal motore per il corretto posizionamento del sito sui motori di ricerca; aumentare in modo legittimo e con costanza il numero dei backlink è sicuramente un fattore da non sottovalutare per ottenere un buon posizionamento.

I testi dei link

Tutti gli operatori che lavorano nel posizionamento sui motori di ricerca hanno capito quanto risultano essere importanti i link per i motori di ricerca, soprattutto per un motore di ricerca come Google che considera molto di più i fattori cosiddetti “esterni” di un sito, come per esempio la link popularity e il peso di un backlink, piuttosto che i fattori di ottimizzazione “interna” relativi alla struttura adottata per il sito, ai tag HTML usati per la formattazione dei testi e alle parole chiave utilizzate.

Detto questo, possiamo ancora imparare molto sull’uso che il motore di ricerca fa dei link:

– una volta rilevati e analizzati i backlink, pesati e rilevata la loro “freschezza”, scopriamo altre novità sempre derivanti dall’analisi dei Dati Storici.

La novità che Google introduce con il suo brevetto sui Dati Storici relativamente ai testi delle ancore riguarda, come ci si sarebbe potuto aspettare dall’interpretazione della sezione relativa ai Criteri basati sui link, il modo in cui i testi delle ancore cambiano nel tempo.

Nello stesso modo in cui vengono analizzati e pesati i link a un documento, possono essere rilevati anche i cambiamenti nel tempo del testo di un link.

Questo anche perchè il testo dell’ancora di un link, e più in generale un link, è spesso considerato come parte integrante del documento a cui punta e di qui l’ovvia conseguenza che il testo contenuto nell’ancora debba essere rilevante per il dominio a cui punta, e non apparire per risultati di ricerche “fuori tema”.

Un esempio classico di questa tecnica è il monitoraggio di un dominio, dei testi delle ancore contenute nei link, per rilevare se il dominio che ospita il documento ha cambiato proprietario, e di conseguenza ha cambiato i suoi contenuti.

In questo caso Google nel suo brevetto sui Dati Storici ci indica che tutti i backlink precedenti, che risultano quindi essere non “in tema” potrebbero essere poco considerati o addirittura ignorati.Tutto questo sempre nell’ottica perseguita da Google di restituire sempre risultati di qualità in tema con le parole chiave ricercate.

Come rilevato dall’analisi dei Criteri sui link, la freschezza di un link risulta essere un parametro utile al motore per effettuare aggiornamenti sul valore di un documento o di un sito. Nello stesso modo, la freschezza del testo di un’ancora può essere determinata e usata dal motore di ricerca per rilevare se c’è stato un aggiornamento, o un cambiamento di argomento, del documento a cui punta il link e di conseguenza aggiornare il valore del documento per il posizionamento sul motore di ricerca.

Il Traffico

Un altro fattore usato dal motore di ricerca, nella sua analisi e valutazione dei dati storici, risulta essere il Traffico associato ad un documento in un determinato periodo di tempo.

In questo momento storico, in cui alcuni algoritmi dei motori di ricerca stanno diventando così complessi da usare funzioni come i filtri bayesiani o l’intelligenza artificiale per l’auto-apprendimento, come potevamo NON pensare che anche il Traffico che riceve un documento o un sito potesse essere un fattore correttivo per il posizionamento sui motori di ricerca?

In termini di qualità, come abbiamo visto nella sezione riguardante l’aggiornamento dei contenuti, un documento costantemente aggiornato può essere considerato più meritevole rispetto ad un documento stantio e quindi risultare meglio posizionato nei risultati delle ricerche.

Questi fattori possono essere rilevati anche attraverso le analisi del traffico associato al documento, attraverso la determinazione delle caratteristiche delle variazioni del traffico : per esempio una grande riduzione di traffico nel tempo può significare che il documento sia da considerare stantio, obsoleto.

Tra l’altro, il Brevetto sul reperimento di Dati Storici nasce come strumento per la lotta allo SPAM per rilevare e combattere tutti quei spammer che cercano di ingannare il motore di ricerca per ottenere migliori posizionamenti nei risultati delle ricerche: una delle strategie adottate da questi riguarda proprio il reindirizzamento del traffico proveniente dal motore di ricerca verso un documento o un sito da “spingere”.

Il Traffico a cui è soggetto un documento può essere monitorato dal motore per rilevare variazioni dello stesso: Google ci indica come il motore di ricerca possa identificare ed esaminare degli Schemi di Traffico , comparando, per esempio, il Traffico medio mensile di un documento al traffico medio durante il mese in cui il documento ha ricevuto il maggior traffico, oppure con il traffico annuale.

In questo modo il motore di ricerca può rilevare periodi in cui un documento è più o meno popolare (genera più o meno traffico), come durante l’estate o i fine settimana, identificare degli schemi di traffico ripetitivi e correggere il valore del documento in relazione al periodo considerato.

Un altro modo usato dal motore di ricerca nell’analisi del traffico di un documento, riguarda il monitoraggio delle caratteristiche della variazione nel tempo per il ” traffico pubblicitario “, traffico derivante cioè da circuiti pubblicitari in cui vengono esaminati diversi fattori: dal numero di inserzioni e il ritmo di aggiornamento nel tempo, alla qualità degli inserzionisti (collecandoci al fattore “peso” attribuito ad un link nell’analisi dei criteri basati sui link) e al grado di traffico da questi generato verso il documento a cui fanno riferimento.

Mentre per il “traffico pubblicitario” appare abbastanza chiaro che i dati e le informazioni possano essere recuperati dal circuito pubblicitario AdSense e AdWords, per la rilevazione del traffico e degli schemi di traffico dovrà esistere un modo in cui Google riesca a monitorare le preferenze di un utente: collegandoci alle Analisi delle Ricerche, sappiamo, per esempio, che Google può monitorare il numero delle volte in cui un documento è selezionato in una pagina di risultati della ricerca e/o il tempo che un utente impiega per arrivare a quel documento.

Ma non è tutto. Cito Jill Whalen di HighRankings.com da un suo articolo riportato su masternewmedia.org:

“Potreste chiedervi come fa Google ad ottenere informazioni sul traffico del vostro sito, dato che voi non avete mai fornito questo tipo di informazioni. Ebbene, Google ha alcuni partner che spiano e che sono installati in migliaia di browser, sotto il nome di “Google Toolbar”. Per usare certe funzioni della toolbar, gli utenti devono acconsentire al trasferimento di dati verso Google, dati che includono quali siti sono stati visitati e per quanto tempo.”

Oltre alla Google Toolbar, se pensiamo che funzioni simili di aggregazione di dati possono essere usate anche da applicazioni come MyGoogleSearch,(anche gli altri più grandi motori di ricerca come MSN e Yahoo hanno sviluppato simili applicazioni) o dal traffico proveniente, per esempio, dalla G-Mail o da GoogleTalk, ed utilizzate dal motore per correggere l’ordinamento dei risultati di una ricerca, si potrebbe pensare ad una nuova era per i motori di ricerca: Motori Intelligenti che ordinano i risultati di una ricerca personalizzandoli a seconda dell’utenza e della ricerca effettuata; una nuova era in cui il posizionamento sui motori di ricerca assumerà connotazioni, caratteristiche e modi di sviluppo sostanzialmente diversi, in cui non ci sarà più un posizionamento “assoluto” nei risultati delle ricerche ma ogni documento verrà posizionato in base alle preferenze dell’utente.

In conclusione anche il traffico associato ad un documento può essere un fattore importante da considerare al fine di migliorare il posizionamento tra i risultati delle ricerche.

Il comportamento degli utenti

Il comportamento degli utenti risulta essere un fattore storico utile alla correzione del punteggio del documento per il posizionamento tra i risultati delle ricerche.

Riepilogo correlazioni

Come abbiamo visto nelle analisi delle ricerche e nella traduzione della parte del brevetto di Google riguardante il traffico dei documenti, non solo le ricerche effettuate dagli utenti nel motore di ricerca e le loro scelte nella pagina dei risultati possono essere analizzate ed esaminate dal motore e considerate ai fini del posizionamento del documento, ma anche il traffico verso un documento o un sito web può essere monitorato e valutato per correggere il punteggio che determina il posizionamento sui motori di ricerca.

Introduzione

Il comportamento degli utenti nei confronti di un documento può essere utile a Google per valutare altri parametri, diversi da quelli descritti nei passati articoli, ma sempre relativi alle preferenze e all’atteggiamento dell’utente.

Mentre, con le analisi delle ricerche, Google valuta le preferenze dell’utente nella scelta di un documento piuttosto di un altro tra i risultati forniti per una certa ricerca, con l’analisi del traffico rileva dati storici e ritmi di diminuzione o accrescimento dei volumi di traffico, con l’analisi del comportamento individuale o di massa degli utenti riesce a valutare l’accessibilità del documento e i tempi di permanenza sullo stesso.

Fattori chiave da analizzare

Come possiamo leggere nella traduzione del paragrafo sul comportamento degli utenti nel Brevetto di Google sui Dati Storici, “il motore di ricerca può monitorare il numero delle volte che un documento è selezionato da un insieme di risultati di una ricerca e/o la quantità di tempo che uno o più utenti spendono accedendo al documento” ; con questo tipo di analisi, applicando i criteri visti finora per l’aggiornamento dei contenuti e i fattori relativi alla freschezza o alla “staleness ” di un documento, Google riesce ad effettuare delle valutazioni che riguardano l’accessibilità dei documenti: quanto tempo, cioè, gli utenti spendono accedendo ad un documento.

Con l’analisi di questi dati in un determinato periodo di tempo, Google potrebbe usare l’accessibilità e la permanenza su un documento come fattori di valutazione che gli permettano di attribuire documento un punteggio legato alla “ freschezza ” del documento: cioè, se prima spendevo 30 secondi per accedere ad un documento, ed ora, ogni volta che seleziono lo stesso documento, spendo 5 secondi per accedervi, il motore di ricerca potrebbe interpretare questo mio comportamento e valutare che il documento sia ormai datato, obsoleto, e non contenga più informazioni fresche e utili.

Il recupero e le analisi dei dati storici

Ma come fa Google a recuperare questi tipi di dati?

Abbiamo già visto nella sezione relativa al traffico come Google abbia molti partner associati nello sviluppo di applicazioni di Information Retrieval; ne parla Jill Whalen di HighRankings, ne parlano Danny Sullivan e Chris Shermansu SearchEngineWatch .

Per effettuare certe analisi specifiche sulle attitudini e il comportamento degli utenti, il motore di ricerca, necessita di reperire dati: lo potrebbe fare attraverso la Google Toolbar , Google Desktop, Gmail o anche semplicemente acquistando i dati necessari da circuiti di analisi approfondite circa le tendenze,i comportamenti e le preferenze dell’utente come Alexa.

Per effettuare delle valutazioni di questo tipo che risultino rispondenti alla realtà dei fatti, il motore di ricerca necessita di un’enorme mole di dati: le informazioni che possono essere reperite rappresentano comunque una piccola percentuale rispetto alla totalità, ma possono già essere utili per tracciare dei profili- tipo per diverse utenze e associare, con metodi statistici, il comportamento generale degli utenti a questi profili.

Google Hilltop

Hilltop è un algoritmo di ordinamento che permette di assegnare ai documenti un punteggio di “autorevolezza” relativo a specifici argomenti, e migliorare in molti casi gli ordinamenti basati sull’analisi del contenuto e, per esempio, sul PageRank.

Quando gli utenti interrogano i motori di ricerca su argomenti molto popolari i motori restituiscono generalmente un grande numero di documenti. Ordinare questi documenti può essere un grosso problema per degli algoritmi che si limitano ad analizzarne il contenuto, perché, diversamente da quanto accade nel campo dell’information retrieval classica, dove si suppone che tutti i documenti provengano da fonti autorevoli, nel web esiste una grossa percentuale di SPAM, ovvero documenti che sono scritti appositamente per avere un buon posizionamento nei motori di ricerca ma che presentano un contenuto di bassa utilità per l’utente finale. Anche quando non c’è un tentativo deliberato di ingannare i motori di ricerca, i loro indici sono affollati da un grande numero di documenti di qualità estremamente variabile e difficili da ordinare.

Quello che ho appena scritto non è un opinione personale, ma il riassunto dell’introduzione di una pubblicazione del 2002 di Krishna Bharat, un ingegnere di Google, noto fra le altre cose per essere il creatore di Google News.

In response to a query, a search engine returns a ranked list of documents. If the query is about a popular topic (i.e., it matches many documents), then the returned list is usually too long to view fully. Studies show that users usually look at only the top 10 to 20 results. However, we can exploit the fact that the best targets for popular topics are usually linked to by enthusiasts in the same domain. In this paper, we propose a novel ranking scheme for popular topics that places the most authoritative pages on the query topic at the top of the ranking. Our algorithm operates on a special index of “expert documents.” These are a subset of the pages on the WWW identified as directories of links to non-affiliated sources on specific topics. Results are ranked based on the match between the query and relevant descriptive text for hyperlinks on expert pages pointing to a given result page. We present a prototype search engine that implements our ranking scheme and discuss its performance. With a relatively small (2.5 million page) expert index, our algorithm was able to perform comparably on popular queries with the best of the mainstream search engines.

Khrisna Barat aveva già pubblicato interessanti studi, per esempio riguardo alla distillazione del topic di un documento (Improved algorithms for topic distillation in a hyperlinked environment.) ed alla realizzazione di vettori di termini (The Term Vector Database: fast access to indexing terms for Web pages).

Nel 2002, insieme a George A. Mihaila (altro “geniaccio” di cui riparlerò) pubblica “When experts agree: using non-affiliated experts to rank popular topics”. Questa pubblicazione analizza il problema sopra indicato e tenta di trovare una soluzione efficiente.

Per prima cosa vengono analizzati gli approcci usati precedentemente per tentare di risolvere il problema, fra questi vi è un accenno specifico al PageRank, del quale individua un limite specifico nel “non poter distinguere fra pagine autorevoli in generale e pagine autorevoli relativamente all’argomento della ricerca. In particolare un sito autorevole in generale può contenere una pagina che soddisfa una certa query ma che non è autorevole rispetto all’argomento”.

In altre parole un sito che tratta, per esempio, di animali domestici può essere molto popolare ed avere un alto PR. Molto probabilmente questo PR proviene da link di altri siti che trattano lo stesso argomento e lo consigliano come approfondimento ai propri utenti, un consiglio valido e fondato quindi. Ma se in quello stesso sito ci fosse una sola pagina che trattasse di auto da corsa, non significherebbe che i siti che lo consigliano intendano raccomandare anche la lettura di quella pagina. Eppure in virtù del PR del sito, se ben inserita nella struttura dei link, questa pagina avrebbe buone possibilità di posizionarsi per ricerche riguardanti le auto da corsa.

L’approccio “Hilltop” si basa, come quello del PageRank, sull’assunto che la qualità e la quantità dei link che puntano ad un documento è un buon indice della qualità del documento, la differenza è che Hilltop considera solo i link provenienti da specifici documenti ritenuti “esperti” relativamente alla ricerca effettuata dall’utente, “documenti creati con lo specifico scopo di dirigere le persone verso le risorse”. Quando viene eseguita una query, l’algoritmo Hilltop per prima cosa individua una lista dei documenti “esperti” più rilevanti per l’argomento, poi all’interno di questi seleziona i link più rilevanti rispetto alla query e seguendo questi individua le pagine da posizionare. Queste pagine sono poi “ordinate secondo il numero e la rilevanza di esperti non affiliati che puntano ad esse. Così il punteggio di una pagina riflette l’opinione collettiva dei migliori esperti indipendenti dell’argomento della query”.

E’molto importante capire che questo tipo di algoritmo funziona solo in presenza di un numero sufficiente di “documenti esperti”, cosa che in generale capita per argomenti molto popolari, dove esistono molti siti web che compilano liste di risorse a tema. D’altra parte i webmaster dei siti, in generale, cercano di pubblicare liste di link aggiornate e complete per aumentare la loro popolarità e la loro influenza nella comunità web interessata ad un certo argomento.

Per interrogazioni che non permettano di individuare una lista di documenti esperti ritenuta sufficiente l’algoritmo Hilltop semplicemente non viene utilizzato, ma questo non è un grosso limite, perché viene specificato chiaramente che l’algoritmo serve a migliorare l’accuratezza delle query sulle quali viene applicato e non è assolutamente necessario che venga utilizzato per tutte quelle eseguite dagli utenti. D’altronde Hilltop ha maggiori possibilità di funzionare bene in presenza di un elevato numero di siti attinenti alla ricerca effettuata, proprio la situazione in cui l’analisi del contenuto si rivela insufficiente.

E’ molto probabile che questo algoritmo sia già utilizzato da Google fin dall’update Florida, del 2004, quello in cui ci fu un vero e proprio terremoto nelle serp (pagine dei risultati). Il fatto che venga applicato soltanto alle ricerche più “popolari” spiegherebbe anche un certo comportamento di Google, che per le ricerche con un basso numero di risultati sembra tendere a dare maggior peso all’analisi dei contenuti. Nei prossimi due articoli vedremo in dettaglio come Hilltop seleziona i documenti esperti e come assegna il punteggio di “Autorevolezza” ai documenti che restituisce come risultato.

Hilltop: la selezione dei documenti esperti

L’algotitmo Hilltop di Google ordina i risultati delle ricerche in base al numero ed alla qualità di link provenienti da documenti esperti. Vediamo come vengono selezionati questi documenti.

Il requisito fondamentale di un “documento esperto” è che esso deve contenere numerosi link che puntino a pagine correlate alla ricerca eseguita dall’utente e che non siano affiliate fra loro. Quindi per prima cosa l’algoritmo Hilltop deve saper distinguere quando due siti diversi appartengono alla stessa organizzazione. Hilltop giudica due siti affiliati fra loro quando si verifichi almeno una delle due seguenti circostanze:

– I due siti dividono gli ultimi tre ottetti di un indirizzo IP (stessa classe C)
– La sezione più a destra e non generica del nome del dominio è la stessa.

In generale le aziende, e specialmente le grandi aziende possiedono i server sui quali risiedono i loro siti. Quindi se esse posseggono più siti questi condivideranno lo stesso indirizzo, oppure avranno indirizzi vicini, dal momento che gli indirizzi vengono assegnati in tranche alle varie organizzazioni che ne fanno richiesta.

Le tranche in cui vengono assegnati gli indirizzi IP possono però essere anche molto più piccole di quelle considerate da Hilltop come soglia di affiliazione, infatti le ultime tre cifre contengono effettivamente 256 indirizzi IP, ma attraverso un artificio tecnico chiamato Subnet Mask, ad una organizzazione ne possono venire assegnati anche molti meno, per esempio 16, ed in questo caso Hilltop potrebbe considerare affiliate 16 organizzazioni che in realtà non lo sono.

Addirittura molti servizi di hosting economici usano lo stesso server ed un solo indirizzo IP per ospitare decine e decine di siti e domini diversi.

Di conseguenza, durante la selezione dei documenti esperti Hilltop potrebbe scartarne alcuni perché contengono link che puntano a pagine che vengono rilevate come affiliate. Tuttavia questo è ritenuto accettabile, perché se viene comunque individuato un numero sufficiente di documenti esperti ci sarà in questo caso la certezza o quasi che siano realmente imparziali e che contengano link a pagine ritenute sinceramente valide.

La condizione di affiliazione che riguarda il nome del dominio, invece, adotta la convenzione di considerare “sezioni” di questo le parti delimitate dai punti e di considerare come generiche, e quindi ignorare, le parti che si ripetono identiche in un grande numero di siti, come per esempio “.it”, “.co.uk”, “.com” ecc.

Per esempio comparando “www.ibm.com” e “www.ibm.co.mx” vengono ignorati i suffissi “.com” e “.co.mx”, per cui le sezioni più a destra, delimitate da un punto risulteranno essere “ibm” in entrambi i casi e i due siti saranno considerati affiliati.

La relazione di affiliazione è inoltre transitiva, per cui se i siti A e B sono rilevati come affiliati ed i siti B e C sono rilevati come affiliati, allora i siti A e C saranno considerati affiliati anche senza ulteriori “prove a carico” del fatto.

Prima ancora di selezionare i documenti esperti viene costruito uno specifico indice di affiliazioni fra i vari siti, dove a tutti quelli che vengono ritenuti affiliati, in base ai criteri già specificati, viene assegnato uno stesso codice identificativo. Questo indice viene usato per verificare velocemente l’affiliazione fra due siti: se hanno lo stesso codice sono affiliati, altrimenti non lo sono.

Dopo aver creato l’indice delle affiliazioni viene creato un nuovo indice, quello dei documenti esperti. Questo indice viene ricavato analizzando il database principale del motore ed estraendone i documenti che vengono considerati buone sorgenti di link tematizzati.

Per prima cosa vengono considerati i documenti che hanno un numero di link in uscita superiore ad una determinata soglia, diciamo, per esempio, 5 link in uscita. Dopodichè i link in uscita di tutti i documenti vengono confrontati con l’indice delle affiliazioni. Se risulta che i 5 link puntano a 5 siti non affiliati il documento è considerato un documento esperto. Anche un certo tipo di formattazione “regolare del documento”, stile directory per intenderci, può avere del peso nell’aiutare l’algoritmo a capire che il documento è una vera lista di risorse.

Infine se nell’indice di partenza del motore è memorizzata una classificazione di massima dell’argomento trattato dai documenti indicizzati (come per esempio arte, sport, scienza ecc.) può essere anche posta la condizione che la maggior parte o tutti i link in uscita del documento esperto debbano puntare a documenti che condividano la stessa classificazione di argomento.

Vedremo ora come vengono indicizzati i documenti esperti e come vengono assegnati i punteggi ai documenti restituiti agli utenti.

Hilltop: ordinamento dei risultati

Quando viene eseguita una ricerca, Hilltop estrae dal suo indice dei documenti esperti quelli rilevanti e li utilizza per individuare ed ordinare i documenti che restituisce all’utente finale.

Nella fase d’analisi dei documenti esperti, l’algoritmo Hilltop esamina solo alcune parti di essi, parti che nel gergo specifico di questo algoritmo sono chiamate “frasi chiave”. Le “frasi chiave” di Hilltop non hanno niente a che vedere con le parole o le frasi digitate dagli utenti per effettuare una ricerca. La definizione di “frase chiave” nell’ambito di Hilltop è “una parte di testo che qualifica uno o più link in uscita”.

I documenti esperti contengono, come abbiamo visto nel precedente articolo, numerosi link in uscita: Hilltop associa ad ognuno di essi alcune “frasi chiave” presenti in specifiche parti della struttura del documento.

I documenti esperti sono inseriti in uno speciale indice inverso organizzato per keyword, nel quale esiste un record per ogni associazione fra una keyword ed una “frase chiave” di un documento esperto. Per ognuno di questi record è memorizzato anche il tipo di “frase chiave” (tag title, intestazione, ecc.) e la prominenza della keyword all’interno della frase.

Quando l’utente esegue una ricerca, l’algoritmo seleziona una lista di documenti esperti rilevanti rispetto ad essa (nell’esperimento relativo alla pubblicazione in esame la lista era composta di 200 documenti esperti). Per essere considerato rilevante rispetto ad una ricerca, il documento esperto deve contenere almeno un link che abbia tutte le parole della ricerca nelle “frasi chiave” che lo qualificano.

Ai documenti esperti viene assegnato un punteggio basato sul numero e sul tipo di “frasi chiave” (tag title, intestazione, ecc.) contenenti le keywords della ricerca. Nell’assegnamento del punteggio sono considerate soltanto le “frasi chiave” che contengono quasi tutte le keyword e viene tenuto conto anche della percentuale di testo che le keyword rappresentano all’interno di ogni frase. I duecento documenti con punteggi più alti vengono scelti come documenti esperti per la ricerca in questione.

A questo punto l’algoritmo Hilltop esamina tutti i documenti a cui puntano i link contenuti negli esperti selezionati ed estrae tutti quelli che ricevono un link da almeno due esperti non affiliati fra loro (ed ovviamente neppure con il documento in esame). Questi documenti sono definiti “bersagli”, e sono quelli che saranno ordinati nei risultati che verranno forniti agli utenti.

Ogni associazione fra una “frase chiave” contenuta in un esperto e un documento “bersaglio” trasmette a quest’ultimo un punteggio proporzionale a quello del documento esperto ed al tipo di “frase chiave” (tag title, intestazione, ecc.). Se due documenti esperti affiliati puntano allo stesso “documento bersaglio” il punteggio di uno dei due, per la precisione di quello più basso, non viene conteggiato.

Ai “documenti bersaglio” viene assegnato un punteggio uguale alla sommatoria dei punteggi ricevuti dai documenti esperti. I risultati vengono infine ordinati combinando i punteggi dell’algoritmo Hilltop e quelli ottenuti dall’analisi dei contenuti dei “documenti bersaglio“.

Sono state eseguite prove di confronto fra i risultati forniti dall’algoritmo Hilltop e quelli forniti da tre motori di ricerca commerciali: Altavista, Direct Hit e Google (prima che assumessero Khrisna Barat, l’inventore dell’algoritmo). I risultati sono stati esaminati da giudici esterni che non sapevano quale lista appartenesse a quale motore. I test hanno evidenziato una capacità di Hilltop pari o migliore degli altri motori di ricerca nel generare una prima pagina di risultati contenente siti molto rilevanti. E’ anche probabile che le prestazioni di Hilltop siano estremamente migliorate al momento della sua integrazione in Google, grazie all’’ampio indice di documenti ed ai sofisticati algoritmi di analisi del contentuto che ha potuto sfruttare.

Se vuoi leggere tutto il paper su Hilltop lo trovi qui: http://ftp.cs.toronto.edu/pub/reports/csrg/405/hilltop.html