All chapters

Question 1

Search engine, quante generazioni abbiamo e caratteristiche di queste ultime.

Answer 1

5 generazioni: 0) semplice, basata su metadati. 1) Basata su contenuto della web page. 2) Introduzione di Anchor text e tiene in considerazione hyperlinks. 3) Si tiene in considerazione Query precedenti degli utenti. 4) Abbiamo un summit delle info, tramite information supply.

Question 2

Parole possono 2 alcune caratteristiche importanti nei search engine, descrivile:

Answer 2

Polisemia (Stessa parola concetti diversi) , sinonimo (Parole diverse, stesso concetto)

Question 3

Come è cambiato paradigma di Search engine?

Answer 3

Prima avevamo query semplici, oggi invece query colloquiali. Abbiamo anche interazione tra IoT devices.

Question 4

Tipologia di dati

Answer 4

Opportunistici, come carte di credito o chiamate telefoniche, utilizzati in modo opportunistico dalle società.
Dati presi con uno scopo, un esempio di questi sono i dati raccolti da sensori.
Dati forniti dall’utente, come quando viene utilizzato un social.

Question 5

Definizione di information retrieval

Answer 5

Indica il trovare del materiale di tipo non strutturato in una grande collezione di elementi che risolve un bisogno di un utente.

Question 6

Dati strutturati vs non strutturati, esempio entrambi.

Answer 6

Database hanno dei dati di tipo strutturato, mentre in information retrieval abbiamo dati semi strutturati come XML o JSON.

Question 7

Perchè non usare un DB tradizionale per search engines?

Answer 7

Poichè se immaginiamo solo wikipedia, abbiamo 1 mil pagine e 1 mil di parole . Troppo grande e documenti non contengono 1 milione di parole diverse, quindi abbiamo tanti zero.

Question 8

Soft AND vs Hard AND

Answer 8

Quando effettuiamo una query, soft AND utilizzato anche da Google, rimuove alcune parole troppo stringenti dalla query a differenza di Hard AND che le richiede tutte.

Question 9

Perchè usiamo Inverted index e come funziona?

Answer 9

Poichè salviamo spazio e tempo. Nello specifico creiamo una lista di token, e per ogni token associamo quelli che sono i documenti contenti il token. Approccio naive per il confronto sarà confronto (n * m) elementi. Approccio ottimizzato (n + m) confronti, poichè teniamo ordinata lista dei documenti.

Question 10

Se avessimo più di due token come effettuiamo operazioni di confronto? potevo usare un metodo più ottimizzato del primo descritto?

Answer 10

In questo caso partiamo da token con minor numero di documenti, in modo da mantenere piccola dimensione di documenti aventi token che ci interessano. Metodo più ottimizzato in questo caso sarebbe utilizzare binary search e non confronto lineare.

Question 11

Come ottimizzare query in inverted index?

Answer 11

Possiamo usare skip pointers, possiamo muoverci tra blocchi la cui dimensione ideale è sqrt(n) elementi, poichè blocchi troppo grandi pochi skip, blocchi troppo piccoli sostanzialmente inutili.
Altro metodo recursive merge, che tramite binary search + ricorsività va a scartare alcuni elementi della lista, molto elegante ma ricorsività può essere pesante per il sistema.

Question 12

Problema delle queries con OR NOT

Answer 12

In questo caso query molto pericolosa, poichè dobbiamo unire due liste di docs, una che rispetta prima proprietà e seconda che non rispetta seconda proprietà (“Lista enorme”).

Question 13

Differenti tipologie di queries.

Answer 13

4 tipologie di queries:
Phrasal: Match perfetto, dobbiamo salvare posizione dei token nel doc.
Proximity: Token si trovano a distanza al più k
Zone/Field queries: Parti del documento di lunghezza variabile (autore, dove scritto, contenuto) , vogliamo sapere se contengono un token che ci interessa. Possiamo salvare o per ciascun token, il field dove contenuto o i token salvati in modo classico e docs contengono reference a field.
Similarity queries: abbiamo token diversi con stesso significato, utilizziamo knoledge graphs.

Question 14

Com’è strutturato un search engine?

Answer 14

Abbiamo back end: un crawler che analizza il web, un page archive dove vengono salvate le pagine web. Page analyzer che si occupa di analizzarle e costruire inverted index tramite indexer.
Mentre il front end è quello che utilizziamo che a partire dalle queries ci restituisce le pagine in ordine di importanza.

Question 15

Che db viene utilizzato per salvataggio di dati da Page archive ecc..

Answer 15

Vengono utilizzati no sql, che permettono di gestire big data tramite delle table “infinite”. Che tramite stringhe permettono di accedere ad altre stringhe.

Question 16

Descrivimi struttura Bow Tie del web

Answer 16

Abbiamo 5 componenti fondamentali:
Strongly connected components, che sono componenti che permettono partendo da uno di loro di tornare al componente di partenza.
In, che permettono di arrivare agli strongly connected components, ma non a quelli di partenza.
Out, partono da strongly connected components ma non tornano a questi ultimi.
Tubes, che portano da IN ad OUT, senza passare per SCC.
Tendrils, che portano verso vicoli ciechi.
Disconnected components, non interessanti non puntano e non sono puntati da SCC, IN o OUT.

Question 17

Quando creiamo crawlers da dove partire come parte del web?

Answer 17

Partiamo da IN, ovviamente non essendoci
distribuzione delle pagine uniforme le pagine da cui partiamo sono decise in modo “arbitrario”.

Question 18

Come scegliere le pagine da cui effettuare crawling? Quanto fare crawling? E quanto spesso?

Answer 18

Migliori in relazione al tipo di search engine che costruiamo, dobbiamo evitare spider traps “pagine dove entriamo e troviamo tutti contenuti inutili” e spam “pagine offensive o non interessanti”.

Il crawling va effettuato con tradeoff tra pagine già visitate e pagine nuove.

Alcune pagine hanno bisogno di aggiornamento continuo come newspapers, altre come quelle universitarie di un crawl molto più limitato.

Question 19

Come funziona life cycle di un crawler?

Answer 19

NOTA CHE FRONTIERA SI PORTA DIETRO LINKS VISITATI; ASSIGNED REPOSITORY GESTISCE LINKS DA VISITARE

Il crawler si porta dietro una frontiera di links inizializzati con seed urls. Assegnamo tramite il crawler manager i link da visitare secondo un ordine. Da questi vengono scaricati links tramite Page Downloader, nel Page Repository. Da quest’ ultimo poi il link extractor si occupa di analizzare una pagina per scegliere links da inserire nuovamente nell’Assigned repository. Importante i links potrebbero appartenere ad host diversi, oppure link già visitati.
Abbiamo più crawler che lavorano in parallelo.

Question 20

Condizioni di terminazione per un Crawler

Answer 20

Varie, esempi non ci sono altre pagine oppure time limit.

Question 21

Come verificare se una pagina P è buona per un Crawler?

Answer 21

BFS, DFS, RANDOM.
POPULAR DRIVEN, ogni pagina ha uno score come Page Rank.
TOPIC DRIVEN.
COMBINATI.

Question 22

Descrivi come funziona Mercator Crawler

Answer 22

Abbiamo URLs incontrati, un prioritazer che assegna priorità ai vari URLs. K front end queue dove inseriamo elementi basandoci sulla priorità. Questi elementi vengono scelti in modo biased da un biased selector (priorità maggiore, possibilità maggiore di essere scelti). Back end BE queue che servono per gestire vari host, ogni queue ha un host assegnato. Quando prendo elementi da BE li inserisco in min heap basato su tempo di attesa con host per non incorrere in blocco per troppi accessi.
Quando prendo nuova pagina da inserire in Min heap potrei trovare queue vuota, in quel caso prendo una pagina da front end e la inserisco nella relativa queue, se non presente la queue vuota viene assegnata al nuovo host.

Prima pagina da cui effettuare Crawling è la minore del min heap.

Buon valore per B = 3 x numero di thread.

Question 23

Errore nel bloom filter

Answer 23

Dato da (1 - e^ (-k n / m))^k . Dati n, m fixed possiamo settare k = (m/n) ln 2 . In questo modo otteniamo errore uguale ad 0.62^ m/n

Question 24

Differenza tra bloom filter e hash map.

Answer 24

Per hash map noi possiamo avere dimensione array di hash = numero di chiavi. Ma dobbiamo salvare una lista di chiavi per quando incontriamo una collisione. Quindi scopi differenti.

Question 25

Quanto vale errore nello spectral bloom filter

Answer 25

Vale come quello del bloom filter, infatti se ho un errore vuol dire che ho collisioni per tutti gli elementi. Ma questo proprio errore bloom filter poichè non posso avere valori minori di valore reale.

Question 26

Come posso ottimizzare spectral bloom filter?

Answer 26

Uso due spectral bloom filter, SPF2 &laquo_space;SPF1, con hash functions ovviamente differenti. Se presente recurring minimum uso quello, altrimenti inserisco elementi partendo da Single minimum.

Question 27

Crawling parallelo che tipologie posso avere

Answer 27

Static assignment, prevede assegnazione ad ogni crawler di una specifica porzione del web.
Dynamic assignment, prevede assegnazione tramite hash function che restituisce un valore per ogni url tra [0, c - 1] con c numero di crawlers.

Consistent hashing ci permette di assegnare urls tramite fault tollerance.

Utilizzo un ring, dove nodi sono o servers o urls, leggo clock wise ed il primo server che incontro gestirà tutti gli urls.
Il remapping nel caso di aggiunta o rimozione di server riguarda n/s elementi.
Per boostare possiamo prendere s log s servers, visto ad AE, quindi non credo mi interessi.

Question 28

Quali proprietà utilizzo per la compressione del web graph?

Answer 28

Utilizzo tre proprietà:
- Skewed, ossia probabilità che un nodo abbia x links = 1/x^alfa dove alfa è una costante che vale circa 2.1. Questa tipologia di distribuzione è chiamata power law, difficile da distinguere da polinomiale ad occhio nudo, quindi applichiamo log a y = x^-alfa. In questo modo ottengo una funzione lineare data da log 2 y = -alfa log 2, utilizzando un grafo log log scale (1 2 4 8).
Power law indica anche numero di strongly connected components ed altre proprietà del web.
-Locality, molti link in un dominio riportano a pagine dello stesso dominio
-Similarity, pagine dello stesso dominio condivideranno molti link.

Basandomi su queste 3 proprietà posso usare Web Graph Compressor algorithm.

Question 29

Come funziona LSH? Quali sono due versioni dell’algoritmo?

Answer 29

Locality sensitive hashing algorithm si basa su Hamming distance (numero di bits differenti), che permette di costruire similarity partire da un bit vector che rappresenta un elemento = numero di bits totali - Hamming distance / bits totali.
Se effettuiamo delle proiezioni di un elemento per confrontare due vettori, evitando costo lineare per confronto, possiamo vedere come probabilità che vettori dichiarati uguali = similarity s. Se effettuiamo k proiezioni s^k.
Probabilità di errore quindi 1 - s^k.
k è inversamente proporzionale a falsi positivi e direttamente proporzionale a falsi negativi.

LOCALITY SENSITIVE HASHING
Parte da questo concetto, iterando per L volte, con proiezioni di dimensione k. Crea una fingerprint di un vettore con tutte le proiezioni di dimensione k. La probabilità che ci siano dei falsi positivi = 1 - [1 -s^k]^L

Abbiamo due versioni algoritmo:
Offline, che costruisce le varie proiezioni, per poi ordinarle in base al i-esima proiezione trovando vettori simili. Una volta fatto questo costruisce connected components, per i quali vale proprietà transitiva. Si avanza i e si ordina per successiva proeizione.

Online, abbiamo L hash table, dove inseriamo ogni proiezione. Se collisione inseriamo piu elementi. Per ogni query L accessi alle hash table, per tutti i documenti retrieved poi effettuo confronto tra vettori, volendo evitare false positives. Dove numero di celle per hash table = 2^k. Poichè k posizioni possono rappresentare 2^k elementi.

Question 30

K-Means vs LSH

Answer 30

K-Means trova local optimal, mentre LSH trova clusters con alta probabilità.

K-Means compara vettori, LSH compara sketch.

K-Means richiede poche iterazioni, mentre LSH elementi piccoli, pochi scan.

K deve essere conosciuto in anticipo per K-Means, mentre LSH non deve conoscerlo in anticipo.

Posso applicare K-Means ad LSH.

Question 31

Come trovare duplicati Exact Match?

Answer 31

Per exact match posso:
-Fare confronti brute force tra tutti elementi
-Fare confronti tra tutti elementi, ma solo di fingerprint
-Ordinare fingerprint ottenute in modo da ottenere cluster di elementi uguali
Algoritmo che utilizzo per fingerprint Karp Rabin, tra pattern da matchare e documento.

Question 32

Proprietà del Karp Rabin

Answer 32

Rolling hash: Permette di calcolare da fingerprint precedente successiva.
Probabilità di collisione basata su proprietà algebrica: collisione -> A - B mod p = 0.
A - B = C, posso riscrivere C come prodotto numeri primi, numeri primi che sono divisibili per p contenuti in C sono al più m.
Poichè C viene fuori da fingerprints c1 * 2^m-1 + c2 * 2^m-2 ..+ cm * 2^0.
m * log(U) / U, dove U/log(U) = numero di primi compresi tra 0, U.
Efficienza, permette di calcolare senza effettuare recomputing from scratch.

Question 33

Come trovare Near Duplicate Documents? Ricorda che LSH non è metodo principale…

Answer 33

Utilizzo:
Shinglings che sarebbero subset di documento originale di dimensione q, scelta tra 4 e 8 di solito.
Se documenti condividono molti shinglings, allora partial match.
Jaccard similarity: Similarity tra due documenti è data da numero di shinglings uguali / numero di shinglings totali.

Min hashing tecnique ci permette di salvare spazio applicando una permutazione agli shinglings, trasformati in integer , permutazione possibile a * x + b mod 2^64.
Prendo poi il minimo tra queste permutazioni, per ogni doc, per verificare match.
Probabilità che min sia uguale è proprio Jaccard Similarity, poichè per essere uguali P(min perm(A U B) = min perm(A /\ B)) = |A /\ B| / |A U B|.
Possiamo migliorare algoritmo utilizzando sketch, ossia k permutazioni differenti, di cui salviamo min. Per confrontare numero di uguaglianze. Dando come risultato finale, numero di elementi uguali / k.

Cosine distance:
Cosine similarity compresa tra 0 e 1, dove 1 indica documenti uguali.
dati due vettori di elementi da confrontare appartenenti ad R^n (vettore dizionario), cosine similarity = p * q / ||p|| * ||q||.
Applichiamo ora sketching , prendendo k vectors appartenenti sempre ad R^n.
Con questi k vectors costruisco sketch vector, di dimensione k, dove ogni elemento dato da segno del prodotto tra vettore p e vettore randomico.
Probabilità di errore = Prob che due sketches siano uguali = 1 - alfa / 180. Questo poichè numero di possibili tagli che portano i due valori ad essere diversi -1 e 1 è dato da alfa, sopra numero di possibili tutti i possibili angoli del hyperplane perpendicolare.

Question 34

Time complexity di Near duplicates?

Answer 34

Naive: O(n^2 * l)
Sketches: O(n^2 * s), s = sketch dimension
Sketching + clustering: O(k * n * i * s)
Sketching + LSH: O(L * sort(n))

Question 35

Come costruire index?

Answer 35

4 Tecniche:
SPIMI single pass in memory indexing:
Costruisco dizionario di lunghezza variabile, quando pieno raddoppio dimensione posting list. Una volta terminata costruzione del documento sorto i termini nel dizionario e scrivo su disco.

Multi way merge sort: ho vari blocchi già ordinati, devo mergiarli in modo ordinato, posso fare questo in memoria. Ovviamente non carico tutte le pagine in memoria, ma di solito prendo 1 pagina da ogni input file, e inserisco 1 minimo per volta. Posso fare più passaggi.

Indexing parallelo: Basato su Map reduce, abbiamo task di parsing per prendere termini e inverter per creare coppia termine -> Doc IDs.
Gestione di due tipi, 1 ogni macchina gestisce solo termini di una parte alfabeto es. [a,c] , in questo modo ogni macchina si porta dietro solo una porzione di liste.
Seconda gestione ogni macchina gestisce solo alcuni docs, in questo caso gestione piu difficile poichè ogni macchina si porta dietro lista completa dei termini.

Indexing dinamico: permette di gestire collezioni dinamiche (possibilità di eliminare, aggiungere elementi), in questo caso per gestire posso utilizzare index principale ed index ausiliario, più un bit vector per tenere traccia delle eliminazioni. Quando leggiamo un valore dobbiamo passare per bit vector per essere sicuri che valore non sia stato eliminato.
LOGARITHMIC MERGE permette di usare una serie di indici di dimensione incrementale M, 2M, 4M, … fino ad arrivare alla struttura su disco. In questo modo quando effettuo operazioni parto da M, se piena sposto in 2M ricorsivamente.

Question 36

Quali steps posso usare per elaborare tokens da un documento?

Answer 36

-Rimozione degli stop words
-Normalization dove rimuoviamo alcuni simboli dalle parole per rendere uguali tokens e queries. Intervento umano richiesto, alcune parole possono avere significati differenti in base a rimozione stop words.
-Case folding, porto tutto in lower case.
-Thesauris, costruisco delle classi di equivalenza per sinonimi.
-Stemming, taglio parte finale
-Lemmatization, vado a portare tutti i verbi infinito, ecc.

Question 37

Quali steps posso usare per elaborare tokens da un documento?

Answer 37

-Rimozione degli stop words
-Normalization dove rimuoviamo alcuni simboli dalle parole per rendere uguali tokens e queries. Intervento umano richiesto, alcune parole possono avere significati differenti in base a rimozione stop words.
-Case folding, porto tutto in lower case.
-Thesauris, costruisco delle classi di equivalenza per sinonimi.
-Stemming, taglio parte finale
-Lemmatization, vado a portare tutti i verbi infinito, ecc.

Question 38

Descrivimi proprietà statistiche di un testo

Answer 38

Zipf law, indica che pochi token sono frequenti, una parte di dimensione media, ha frequenza media. Ed una larga parte è rara.
Basandoci su questo possiamo dire che il k-esima elemento piu frequente ha frequenza = c “costante” / k.
Abbiamo anche General law, dove frequenza = c / k ^ alfa, dove alfa compreso tra 1.5 e 2. Possiamo per visualizzare meglio, applicare log ad entrambi i valori e visualizzarli su un log log plot.

Heaps law, indica che il numero di termini distinti all’aumentare del numero di termini cresce seguendo n^beta dove beta < 1, solitamente utilizzato 0.5.

Luhn law, indica che i termini che ci interessano maggiormente in un documento sono quelli con frequenza media, dato che quelli rari e quelli troppo frequenti non sono cosi rilevanti.

Question 39

Come posso comprimere dictionary?

Answer 39

Lossy, non vista al corso.
Loseless:
-Array di dimensione fixed, in questo caso ho una tabella con 20 bytes per salvare parola, in caso troppo poco non riesco a gestire parola e se troppi sto sprecando bits.
-Dizionario come stringa, salvo puntatore a termini. Salvo circa 60% spazio
-Con blocking posso salvare ancora più spazio, poichè per ogni blocco uso un solo puntatore, ovviamente stringa deve portarsi dietro dimensione di ciascuna parola.
-Front coding, permette di salvare interno della stringa carattere * che indica che substring successive alla parola attuale indicano parole diverse con stessa radice.

Question 40

Tipologie di ricerca in un index?

Answer 40

-Binary search.
-Hash table, buona ma da possibili errori, se usassimo hash perfetto restituirebbe parola esatta, mentre noi vogliamo parole con stessa radice spesso.
-Trie, struttura ad albero in cui ogni parola è un percorso. Molto buona, possibili problemi cache miss poichè usiamo puntatori, molto grandi quindi conviene o usare compact trie, che invce di salvare ogni char, accorpa più char quando percorso non ha possibili diramazioni. Ancora meglio utilizzo Pointerless rappresentation dei tree.

Question 41

Cosa posso tenere in considerazione per capire se una parola è scritta correttamente? Due metodi semplici

Answer 41

Isolated words, parole che hanno un misspelling non basato sul contesto, ma non sempre corretto.
Context-sensitive, in base al contesto capiamo quale migliore parola.

Question 42

Come funziona spelling correction, come posso fixare parola? Hint. Ho bisogno solo di una cosa

Answer 42

Mi porto dietro un lexicon (dizionario dei termini conosciuti) e data una sequenza di chars restituisco la parola più vicina dal lexicon.

Question 43

Misure per cercare vicinanza tra parole

Answer 43

Idea iniziale cerco tramite brute force distanza tra tutte le parole.

Edit distance, quante modifiche di chars (delete, insert, substitute, transposition “inversione di due lettere”) effettuo per arrivare a parola desiderata.
Costo s1 * s2, posso migliorare cercando edit distance di al più D. In questo caso costo = max s1, s2 * D.

Weighted edit distance, tiene conto della distanza dalla lettera typed con quella possibile.

n-gram distance.

Question 44

One-error correction parlamene e come gestirlo

Answer 44

Invece di confrontare mia parola con tutte le possibili, accetto un solo errore (insertion, deletion, sub).
Data L lunghezza stringa, numero possibili varianti ammettendo 1 solo errore = L “deletions” + (L + 1) * A “Insertions” + L * (A - 1) “sub”.
Per effettuare confronto tra le due stringhe posso costruire un dizionario contenente tutte le possibili variazioni di un solo char.
Effettuo poi query per perfect match, e seguendo tutti gli edit richiesti.
Posso avere un falso positivo se gestisco tutto con hash, a meno di utilizzare un hash perfetto.

Question 45

Cosa è overlap distance?

Answer 45

Creo un k-gram index per doc (index che contiene ogni k gram a cui associata una lista di parole che contengono quel k gram).
Creo un altro k gram index per query, partendo da questi due valori e confronto. Errore possibile E (edit distance), indica che accetto k * E valori differenti come threshold.
Perchè usiamo questa formula con k per errore, poichè ogni char differente, rende differenti “k” k-grams.
Sarebbe utile utilizzare context sensitive spell correction, ma troppo costoso, usato solo quando ottengo pochi risultati.

Question 46

Wild-card queries come funzionano

Answer 46

Query nella forma parola* , parola, parola.
Uso permuted index $parola, a$parol, la$paro.
X cerco X$.
X# cerco $X#.
#X cerco X$#.
#X# cerco X# senza $.
X#Y cerco Y$X#.

Question 47

Soundex come funziona?

Answer 47

Mantengo prima lettera, sostituisco alcune lettere con “0”, altre lettere con numeri, accorpo numeri consecutivi, rimuovo 0, restituisco primi 4 valori.

Question 48

Come misurare qualità di un search engine, quali parametri?

Answer 48

Precision: percentuale di documenti retrieved che sono rilevanti rispetto al totale dei documenti retrieved.
Recall: percentuale di documenti retrieved che sono rilevanti rispetto a tutti i documenti rilevanti.
F1= 1/2 p + 1/2 r.
Precision at K results con K = 1 o 5 o 10. Quale è precisione dei primi K risultati? Utile poichè non posso scannerizzare tutti i documenti possibili e quindi mi baso solo sui primi K.

Question 49

Cosa si intende per collocation delle parole?

Answer 49

Per collocation intendiamo parole che rispettano 3 features:
-Limited compositionality: Parole da sole non mi danno significato della collocation
-Non sostituibili: non possiamo sostituire altre parole e mantenere stesso significato
-Non modificabili: non possiamo aggiungere altre parole, altrimenti cambia

Question 50

Come funziona il Tag pattern?

Answer 50

Assegnamo ad ogni token un tag: attributo, nome e proposizione.
Ora costruisco insiemi di due/tre elementi, salviamo numero di occorrenze, filtrando alcune coppie come AA che sicuramente non ci interessa.
Dobbiamo anche tenere in considerazione flessibilità, ci limitiamo a finestre di dimensioni k, poichè alcune parole potrebbero essere accoppiate, anche se ad uno o due token di distanza, quindi teniamo in considerazione media e varianza della distanza. Ovviamente se varianza alta coppia potrebbe non essere rilevante.
Per essere sicuri possiamo effettuare query log check, se coppie non cercate tra milioni di query, non rilevanti.

Question 51

Come funziona Pearson’s Chi sqare test

Answer 51

Vogliamo comprendere di quanto frequenza di una coppia sia differente rispetto ad una distribuzione uniforme delle parole.
Per fare ciò creiamo una matrice di dimensione nn, dove n è numero di parole nella coppia. Ogni elemento della matrice indica numero di occorrenze di combinazioni tra parole presenti e non presenti.
Partendo da matrice possiamo costruire Chi-square value:
X^2 = sommatoria per tutti i possibili i, j( frequenza attuale - frequenza avg)/ frequenze avg.
Il valore X^2 viene confrontato con P-value che possiamo scegliere in base a errore che vogliamo, questo P-value è dato da tabella dei degree of freedom. Il degree of freedom (r-1)(c-1) dove r e c sono il numero di righe e colonne della matrice precedente.

Question 52

Rake Rapid Automatic keyword extraction come funziona?

Answer 52

Funziona su una piccola quantità di documenti, non ha bisogno di training set, veloce e non ha bisogno di supervisione.
Diamo in pasto a rake set di delimitatori, stop words.
4 steps:
- Trovare keywords candidate, splittando documento tramite delimitatori.
- Assegnare score alle keywords candidate: nella matrice andiamo ad inserire numero di occorrenze sulla diagonale (dove reinseriamo keyword), mentre colonna riga indica corrispondenze tra parola colonna e parola riga.
Possiamo calcolare quindi frequenza (elemento su diagonale) e degree (somma tutte colonne), otteniamo cosi punteggio parola (degree(parola) / freq(parola)).
Score di keyword comulativa = somma score di ogni singola keyword che compone keyword maggiore.
-Adjoining keywords: alcune parole non considerate poichè contengono stop words, in questo caso verifico se presente almeno due volte, assegno quindi punteggio considerando che keyword if non ha score.
-Delle keywords ottenute prendo un terzo.

Question 53

Phrase queries come risolverle?

Answer 53

-2 word indexes: salvo bigrams del documento e la query viene trasformata in coppie two words e su quelle effettuo ricerca AND.
Ottengo superset delle reali soluzioni.
-Indice posizionale: aggiungo posizione agli elementi per verificare posizioni ed è utilizzato anche per effettuare proximity queries.
-Combino: Two words e indice posizionale, poichè two words molto utile per parole come “Micheal Jackson”.
-Soft AND: Ritorno fino a quando non ottengo K elementi:
Phrase query.
AND tra 2-gram.
Vector space query con singoli termini.
Rank dei risultati e return.

Question 54

Caching per velocizzare queries come funziona

Answer 54

Ho due metodi che posso utilizzare per velocizzare le queries:
-Cache dei query results, problema poichè spesso risultati molto cachati possono essere invalidati dopo poco
-Cache delle posting list relative ad ogni termine

Posso utilizzare anche tier levels, per salvare in memoria in base al livello di una posting list, ovviamente i livelli più importanti salvano posting lists in memorie più veloci.

Question 55

Skip pointers come scegliere dimensione blocchi?

Answer 55

Dimensione blocchi di solito rad(n), ma se conosco distribuzione dei documenti mi conviene utilizzare dei blocchi minori per documenti con alto score.

Question 56

Differenza tra gzip e lz77

Answer 56

Gzip libreria che usa compressione (LZ77) con windows di size: -1,..,-9 le windows indicano di quanti chars posso retrocedere.

Question 57

Tecniche standard per velocizzare invio dei dati

Answer 57

Caching salvo oggetto per riutilizzarlo, importante che oggetto sia atomico rispetto alle modifiche.
Compression elimino ridondanza da dati che invio

Question 58

Delta compression come funziona?

Answer 58

E’ una tecnica basata su common knowledge condivisa tra sender e receiver.
Utilizzata da tools come diff, zdelta, REBL.
Se applicata ad un file fnew di cui abbiamo vecchia versione fold deve restituire fdelta.
fd = gzip(fnew|fold), per applicare gzip mettiamo fold e proviamo a scrivere fnew in funzione di fold.

Question 59

Come posso con zdelta ottimizzare Web Access?

Answer 59

Pongo cache tra sender e receiver, nel proxy , qui salvo pagine già visitate.
Per utilizzare tutte le pagine visitate posso accorpare tutte pagine in cache e chiamare il tutto fknows, molto pesante.

Question 60

ZDelta applicato a più files come funziona?

Answer 60

Creo un grafo pesato, che parte da un modo eps ed ogni nodo rappresenta un file, eps rappresenta file vuoto. Arco pesato indica dipendenze tra file e qual’è lunghezza di fdelta.
Peso quadratico. Una volta che ho il grafico dobbiamo trovare directed minimum spanning tree .
Per ottimizzare posso clusterizzare in modo da avere molti strongly connected components
Posso stimare pesi invece di calcolarli

Question 61

Come funziona rsynch?

Answer 61

Il client richiede fnew, inviando hash dei blocchi di fold. Fold viene diviso in blocchi di dimensione B, più grandi blocchi più copio ma più possibilità che blocchi non possano essere usati poiché un solo char mi invalida blocco.
Partendo da hash dei blocchi di fnew che già conosce client può ricostruire fnew.

Question 62

Zsync come funziona?

Answer 62

Evoluzione di rsync, basato su client più potenti che permettono di ridurre overhead su server. Interazione inizia dal server che invia hash values dei blocchi di fnew. Client verifica corrispondenza con sliding window che avanza di una sola posizione per volta, obbiettivo ottenere più match possibili. Client invia al server bitmask con 1 se contiene iesimo hash value. Server a questo punto invia valori mancanti.

Question 63

Text based ranking tra due documenti come funziona?

Answer 63

Il text based ranking é dato da dimensione intersezione tra due documenti, possiamo considerare queries come documenti composti da pochi termini. Intersezione da sola non tiene in considerazione dimensione del documento, viene usato quindi coefficiente di Dice 2 | X /\ Y| / |X| + |Y|, non funziona con triangle inequality.
Coefficiente di Jaccard più utilizzato | X /\ Y | / | X U Y |.

Question 64

Quali misure prendo in considerazione per migliorare misurazioni su termini in un documento?

Answer 64

Frequenza di un termine condiviso, maggiore è indice di una parola importante per quel documento.
Scarsità nel documento, i termini più scarsi se condivisi potrebbero essere utili, mentre quelli troppo presenti potrebbero essere proposizioni.
Lunghezza del documento devi normalizzare score in base a questa.

Question 65

Tf-Idf come funziona?

Answer 65

Tiene in considerazione Term frequency = numero di volte in cui incontro un termine in un documento e idf che indica frequenza di un termine rispetto a tutti i documenti nella collezione.
Tf è semplicemente numero di occorrenze, idf si misura come log(n/nt) dove nt è il numero di occorrenze nel documento corrente.
Possiamo vedere i valori Tf-idf di un documento che ci interessano come elementi di un vettore ad n dimensioni, dove n è il numero di termini nel nostro documento. Essendo vettori quelli che analizziamo possiamo confrontare loro distanza, quello che ci interessa per fare ciò è coseno dell’angolo tra i due vettori, dato che distanza euclidea ci può trarre in inganno.
Possiamo misurare questa distanza come prodotto scalare tra i due vettori / norma di v1 * norma di v2. Coseno = 1 se documenti uguali, zero se totalmente differenti.

Question 66

Come posso approssimare top k documents da analizzare e computare per il document ranking?

Answer 66

Posso usare 5 approcci, tutti basati su una collezione di m documenti, dove k < m &laquo_space;N numero di documenti totali.
-Considero documenti con maggior numero di termini della query. Problemi poichè questi documento potrebbero contenere proposizioni o articoli della query, in modo da superare threshold e solo 1 termine rilevante.
- High Idf terms, considero di una query solo i termini con miglior idf, buona tecnica poichè effettuo pruning di articoli e proposizioni
- Champion list supero limiti di approccio precedente, tenendo in considerazione anche tf. Creo un dizionario offline, quindi effettuo un preprocessing delle posting list, ordinando elementi per weight relative al termine, in questo modo considero solo i top M elementi. Avendo nel worst case |Q| * M.
-Fancy hits, ho un weight dato da Somma per ogni termine della query (tf - idf t,d) + g(d). Dove g(d) = page rank non relativo ai termini, ma al documento specifico.
Computo offline page rank di tutti i documenti ed ordino in base a page rank per ogni termine.
Ora prendo top m documenti secondo tf idf, il minor tf-idf ci da upper bound per elementi non appartenenti a top M elementi.
Ora posso analizzare questi altri documenti (IL), nello specifico Page rank di questi, quando incontro top elementi (FH) il cui Page rank è minore di ub(page rank t1) + ub(page rank t2) non ha senso continuare a cercare nei non top documents se questo valore è minore di elementi già analizzati o dei top elements.
-Clustering, considero uno spazio vettoriale di dimensione q. Creo K clusters, e confronto query solo con i K rappresentanti dei clusters. Una volta trovato il cluster più vicino, meglio i b cluster più vicini poichè query si potrebbe trovare a cavallo tra due clusters, posso comparare elementi con la mia query per un costo di O(K + |Ci|) , Ci numero di elementi per cluster. Il numero di cluster da scegliere ideale = rad(n).

Question 67

Come posso computare top k documents precisi?

Answer 67

Uso WAND, che parte da scoring dei documenti offline, salvo quindi per ogni termine upperbound max score del documento.
Ora mi porto dietro tetha, che indica dentro un min heap quale è minore valore computato in modo da poter cercare una volta superato k valori se il nuovo valore che voglio inserire nel min heap supera il mio threshold.
Tecnica buona ma limiti sulla locality, posso portarmi dietro con Blocked WAND upper bound locale.

Question 68

Relevance Feedback come funziona?

Answer 68

Applico in base a documenti scelti da utente una modifica alla query stessa, applicando regola del parallelogramma e sommo query a documento se documento buono, altrimenti rimuovo documento da query ottenendo una nuova query Q’. Importante potrei avere problemi poiche potrei avere topic drift.
Posso avere anche pseudo relevance feedback dove top k documenti sono considerati i preferiti da utenti, peggiore poichè avro sicuramente topic drift.
Poi ho query expansion che permette ad utente di aggiungere + o - ai termini che reputa piu importanti. Engine applica quindi una ricerca per sinonimi di quel termine.

Question 69

Quali sono tecniche per trovare sinonimi utilizzate da search engine?

Answer 69

-Manual thesaurus, posso trovare sul web lista di relazioni tra le parole come sinonimi
-Global analysis, creo database analizzando grande data collection cercando relazioni tra le parole
-Local analysis come la global, ma dataset piu piccolino ed effettuo una analisi dinamica sul result set di una query.

Question 70

Come funziona random walk?

Answer 70

Prendiamo un grafo e creiamo matrice di adiacenza, partendo da questa andiamo a creare matrice di transizione Xt che indica con che probabilità mi troverò in ogni nodo della matrice al tempo t.
Possiamo formalizzare questa matrice come costituita da Xt+1 = Xt * P = Xt-1 * P^2 = … = X * P^t+1 dove P è matrice di adiacenza di base. Posso usare power method per calcolare queste matrici incrementali, calcolando solo log(t + 1) matrici. Vogliamo adesso trovare uno steady state, quindi uno stato dove Xt + 1 = Xt -> Xt * P = Xt , ma questo ci ricorda autovettori ed autovalori Xt +1 * P = 1 * Xt. Possiamo anche vedere questo stato che vogliamo raggiungere come uno stato in cui ho:
-1 solo SCC, quindi grafo G irriducibile
-Il GCD “Greatest common divisor” per tutte le lunghezze dei cicli in G deve essere 1.
Queste proprietà importanti poichè ci indicano che se parto da ogni nodo, posso raggiungere ogni altro nodo in ogni momento (1); poi ci indicano che se parto da ogni nodo ho infiniti modi di arrivare ad un altro nodo.

Question 71

Page rank come funziona?

Answer 71

Trasformo grafo in fully connected component aggiungendo archi per fare ciò. Questi archi connettono ogni possibile nodo tra loro.
Il peso di questi archi è dato da 1 - alfa.
Se alfa = 0, andrò in questi nodi con la stessa probabilità degli archi reali.
Se alfa = 1, questi nodi non vengono considerati, ma non ottengo SCC.
Il rank di un nodo i è calcolato sommando il rank di tutti i nodi aventi arco entrante in i/numero di archi uscenti da nodi + 1-alfa/ n (peso degli archi nuovi).
Alfa scelto da Google = 0.85, probabilimente con esperimenti. Dopo questo Google calcolo Page rank di tutti i documenti , circa un milione.
Possiamo effettuare una modifica al page rank, andando a usare un subset di nodi verso cui creare archi nuovi, in questo modo posso ottenere più pagine vicine ad alcune che mi interessano.

Question 72

HITS algorithm come funziona?

Answer 72

Sviluppato nello stesso periodo del page rank, basato sulle queries. Prendo documenti che matchano con query (root set), ora da questi prendo documenti puntati e che puntano e costruisco il mio baseset.
Dal baseset valuto i documenti online, quindi pesante e per questo non utilizzato.
Per valutare documenti ho due scores:
Authority score: buona authority page puntata da molte buone hubs pages.
Hub score: buona hub page punta a molte buone authority pages.
Possiamo vedere da un punto di vista algebrico questi scores:
a = A^T * h (poichè consideriamo pagine che puntano)
h = A * a.
Possiamo anche aggiungere pesi alle authorities iniziali, modificando matrice di adiacenza iniziale.

Question 72

Come posso effettuare sommario di un documento?

Answer 72

Prima idea valutavo saliency di una frase: sommatoria per ogni parola p tf-idf(p) / numero parole; prendo poi top k.
Il limite di questo approccio è che non tengo in considerazione connessione tra le frasi, posso quindi usare sommario di frasi che riguardano stessa parte del testo.
Per superare queste limitazioni, usato Text-Rank, creo fully connected graph con tutte le frasi. Il peso di un arco è dato da similarity (Non Jaccard, ma simile) misurata in questo modo dimensione tra intersezione di parole tra due frasi / log(f1) +log(f2).
Costruisco quindi transition graph dove elemento viene dato da peso/ somma per avere probabilità.
Applico quindi Page Rank.
Posso usare anche un page rank personalizzato per dare priorità ad alcune sentences iniziali, semplicemente modificando teleportation step.

Question 72

Cosa è Lexical page rank?

Answer 72

E’ uguale al Text Rank con due modifiche:
-Uso threshold per effettuare pruning di alcuni archi.
-Weights dati da cosine similarity.

Question 73

Come posso diminuire dimensione dei calcoli da effettuare per gestione delle matrici?

Answer 73

-Random projection (data indipendent)
-LSI (basato su SVD single value decomposition)

Question 74

Come funziona LSI Latent semantic indexing?

Answer 74

Costruisco due matrici, una term-term T = A * A^T, altra doc-doc D = A^T * A. Dove dimensione di AA = m ( termini) * n (documenti).
Partendo da r, rango della matrice, ossia numero di righe/colonne indipendenti tra loro; posso costruire U (mr) costituito da autovettori di T e V (n r) costituito da autovettori di D. Posso quindi scrivere A = U * Sigma * V^T. Sigma è una matrice avente elementi solo sulla diagonale principale, i restanti valori sono tutti zero.
I valori sulla diagonale di Sigma sono i quadrati degli autovalori di A, rappresentano la strength di ogni concept. Il nostro scopo era quello di diminuire dimensione della matrice A, possiamo farlo limitando il valore di r, a k. Andando a limitare la dimensione di U otteniamo quella che viene chiamata matrice dei latent concepts, infatti ogni riga di U rappresenta una serie di termini, ed ogni riga di Uk rappresenta un concetto ed il peso che ogni termina ha rispetto a quel concetto. Stessa cosa per D^T k, dove la trasposta fa si che ogni riga sia relativa ad un concetto ed ogni colonna rappresenta quanto un documento sia related a quel concetto. Ora ottengo quindi Ak un approssimazione di A.

Question 75

Come posso associare i concetti ad un significato reale?

Answer 75

Molto utili knowledge graphs, dove ogni nodo rappresenta un entità ed ogni edge rappresenta relazione tra queste.

Question 76

Come funziona TagMe?

Answer 76

Trova parole chiave e annotale con articoli da wikipedia.
Difficoltà che ogni parola chiave, può essere linkata a differenti articoli wikipidea. Va compreso quindi in base al contesto.
Quando effettuiamo disambiguazione tra le varie pagine la Probabilità che p sia la pagina giusta per anchor a = P(p|a) = # volte in cui p utilizzata per a / # a anchor totali.
Mentre la probabilità che a sia anchor dato da # di volte in cui a è anchor / # di volte che a è presente nel testo.
Per effettuare poi valutazione delle pagine, verifico quanto una pagina è relativa all’altra tra due possibili pagine candidate per due anchor.
Effettuo pruning di pagine poco comuni utilizzate come anchor, applico voting scheme, prendo prime k pages e scelgo nuovamente in base a commmoness.

Question 77

Relatedness di un testo

Answer 77

Relatedness di un testo, indica quanto due pagine siano relazionate tra loro s(a, b) = log( max(|A|,|B|)) - log(|A /\ B|) / log(|W|) - log(min(|A|,|B|).