Oral Questions Flashcards
Crawlers cosa sono?
Sono dei programmi che girano il web in cerca di pagine da scaricare
Importante quando creiamo crawerls é la qualità delle pagine
Le pagine migliori da cui partire sono sicuramente legate alla tipologia di pagine che vogliamo visitare
Dobbiamo evitare i duplicati e ci sono pagine che sono da identificare
Spam pages
Spider traps, che costringono crawler a visitare tante pagine useless collegate tra loro
Quanto dobbiamo fare crawling
Dobbiamo capire quante pagine nuove e ogni quanto dobbiamo ricaricare vecchie pagine
Ogni quanto
Dipende da quanto vogliamo che le pagine siano aggiornate
Come funziona
Abbiamo una frontiera cosa di url che sono stati puntati da altri url visitati
Url visitati
Algoritmo verifica se sono disponibili nuovi urls in frontiera
Se non disponibili url o tempo di vita crawler finito termina
Ogni crawler non può gestire web intero, ma solo un numero di pagine, più crawler in contemporanea surfano web, utilizzando meccanismi che permettono di evitare la visita delle stesse pagine
come funziona la gestione di vita di un crawler
Crawler manager prende link da priority queue quelli da refresh o nuovi li inserisce nella assigned repository
Downloader che scarica pagine da assigned repository e inserisce in page repository
Extractor che prende pagine da page repository e estrae link per metterli in Priority queue
Bloom filter
ogliamo comprendere velocemente se una pagina é già stata visitata o meno
Non possiamo utilizzare hash map poiché hash map troppo grande, miliardi di docs
Per risolvere questo problema utilizziamo bloom filter, occupa poco spazio, ma problematico poiché non sempre preciso
Abbiamo Bloom array con m posizioni, e k hash function
Quando vogliamo aggiungere un url, utilizziamo k hash functions ed inseriamo in posizioni risultanti 1
Per verificare se presente un valore utilizzo le k hash functions, verifico se presente almeno uno zero, in questo caso non presente
Errore bloom filter
Altrimenti c’é possibilità di falso positivo, di ( 1 - eˆ(-kn/m))ˆk k = num hash functions, n numero urls, m dimensioni di bloom filter
Se abbiamo n e m fidati possiamo calcolare valore migliore per k = m/n log2
Con questa sostituzione di k errore diventa = 0.62 ^m/n
Certe volte m/n é un numero molto grande e non conviene utilizzarlo
Differenze con hash table
Hash table occupa O(n)
Bloom filter occupa m bits
Mercator é un crawler utilizzato da Altavista
Per funzionare utilizzava un sistema a due queue,
Front queue dove abbiamo k queue con priority differenti, n.b. che in una front queue abbiamo urls differenti
Da front queue viene presa una della k queue randomicamente, ma influenzata da priorità
Poi i valori da front passano a B queue in back, ognuna di queste queue gestisce un solo dominio
Passaggio influenzato da quando si libera back
Quando si libera, prendiamo valore da front, facendo attenzione a inserirlo nel queue nel back corrispondente a dominio, se non presente queue libera diventa relativa a dominio
Una volta presi valori da back vengono inseriti in min-heap, che é basato sul tempo trascorso tra una visita al dominio ed un’altra
Spectral bloom filter
Utilizzato per query logs, permette delete e counting
Abbiamo un bloom filter che ricorda accessi, quando prendiamo valore dobbiamo scegliere il minimo, poiché é sicuramente valore più vicino ad approssimazione di occorrenze
Probabilità che minimo corrisponda é la stessa dell’errore di bloom filter
Inserimento aggiungiamo alle varie posizioni un valore
Delete rimuoviamo
Search applichiamo minimum selection
Se minimo ricorre più di una volta si chiama recurring minimum ed é estremante improbabile che due valori accedano stessa posizione
Se minimo ricorre una volta é single minimum
Per improve di molto funzionamento di spectral bloom filter utilizziamo idea di Recurring minimum e single minimum
Se un item ha due occorrenze con stesso valore, molto probabilmente corretto
Altrimenti utilizziamo secondo bloom filter molto più piccolo dove partiamo da single minimum
Parallel Crawlers
Quando abbiamo più crawlers che lavorano in parallelo quello che facciamo é distribuire il lavoro
Due soluzioni
Static assignment: dove dividiamo web in base a url, difficile poiché urls .it per esempio molti meno di .com
Dynamic: tecnica spesso utilizzata dove partendo da una funzione hash associamo URLs ad una macchina
Per manage fault tolerance utilizziamo consistent hashing
Utilizziamo una o più hash functions
Abbiamo s servers, ad ogni server associamo dei valori nel range della hash function, se un server rimosso, valori verranno gestiti da server precedente, se server aggiunto valori splittati con altro server che prima li gestiva
Storage compresso del web graph
Quando scarichiamo le pagine, creiamo grafi, questi ultimi composti da miliardi di pagine e miliardi di miliardi di collegamenti
Dobbiamo avere metodo di compressione
Metodo chiamato Web graph compressor
Proprieta :
Skewed property: probability che un nodo abbia x link é circa 1/x^alfa dove alfa vale 2.1
Le tipologie di distribuzione dove alfa vale un fixed value sono chiamate power law
Possiamo creare un grafico che mostra evoluzione di skewed property
Pagine che hanno un solo hyperlink sono tante, più aumentano hyperlinks più diminuiscono pagine
Studiosi partendo da Skewed hanno analizzato y = x^-alfa
Applicando il logaritmo da entrambi i lati log y = log x^-alfa
Corrisponde a log y = -alfa log x
Questo se inserito in una log log function ci porta un grafico discendente che non rispetta al cento percento Skewed, ma si avvicina
Questa proprietà vale per il web, non sono Strongly connected component ma anche In e out
Locality: pagine da un host puntano allo stesso host
Per trovare locality utilizziamo reversed domain www.unipi.it = it.unipi.www
Questo fará trovare vicine pagine dello stesso dominio se effettuo un sort
Similarity: pagine da stesso host, sharano molti hyperlinks
Se due pagine stesso dominio la loro lista hyper links sará simile
Locality sensitive hashing
E’ una tecnica che ci permette di trovare grado similarità tra pagine simili in maniera molto efficiente
Definiamo due componenti composti da d bits, p e q, Hamming distanza tra p e q = numero di bits differenti
Similarità = (d - distanza(p,q)) / d
Per effettuare confronti non posso utilizzare brute force, ma utilizzo algoritmo basato su proiezioni
Creo una funzione h( ) che proietta un valore in una posizione random
Creo k proiezioni, se valori proiezioni uguali molto probabilmente trovo similarità
Probabilità che proiezioni siano uguali
Probabilità che due singole proiezioni siano uguali è s
Probabilità che tutte proiezioni siano uguali è s^k dove k è numero di proiezioni totali
Notiamo che k funge da stepper, se aumenta possibilità si avvicina a zero, se diminuisce possibilità di avvicina ad 1
Devo quindi effettuare un bilanciamento tra falsi positivi e falsi negativi
Come funziona locality sensitive hashing
Iteriamo per L volte funzione h( ) con valori random
Abbiamo fingerprint di un vettore
Due vettori simili se almeno una proiezione uguale
In questo modo possiamo evitare O(n*n) confronti ma abbiamo complessità di O(n log n)
Probabilità che due vettori siano dichiarati simili è P(g(p) = g(q)) => P( esiste hj(p) = hj(q)) => 1 - P( per ogni j hj(p)!=hj(q)) => 1 - (P(hj(p) != hj(q))^L = 1 - (1- S^k)^L
Locality sensitive hashing offline
Fissiamo k e estraiamo i k set di dim m , con m valori fixed
Creiamo fingerprint per vettori analizzati partendo dai k set
Invece di effettuare confronti tra tutte le projections posso utilizzare proprietà transitiva della similarity: se a simile a b e b simile a c => a simile a c
Creo connected components, non ho bisogno di specificare transitivity
Versione online
Creo hash table per L projections
Quando voglio i valori simili effettuo L query su hash table ed ottengo tutti i valori simili tra loro
Locality sensitive hashing
E’ una tecnica che ci permette di trovare grado similarità tra pagine simili in maniera molto efficiente
Definiamo due componenti composti da d bits, p e q, Hamming distanza tra p e q = numero di bits differenti
Similarità = (d - distanza(p,q)) / d
Per effettuare confronti non posso utilizzare brute force, ma utilizzo algoritmo basato su proiezioni
Creo una funzione h( ) che proietta un valore in una posizione random
Creo k proiezioni, se valori proiezioni uguali molto probabilmente trovo similarità
Probabilità che proiezioni siano uguali
Probabilità che due singole proiezioni siano uguali è s
Probabilità che tutte proiezioni siano uguali è s^k dove k è numero di proiezioni totali
Notiamo che k funge da stepper, se aumenta possibilità si avvicina a zero, se diminuisce possibilità di avvicina ad 1
Devo quindi effettuare un bilanciamento tra falsi positivi e falsi negativi
Come funziona locality sensitive hashing
Iteriamo per L volte funzione h( ) con valori random
Abbiamo fingerprint di un vettore
Due vettori simili se almeno una proiezione uguale
In questo modo possiamo evitare O(n*n) confronti ma abbiamo complessità di O(n log n)
Probabilità che due vettori siano dichiarati simili è P(g(p) = g(q)) => P( esiste hj(p) = hj(q)) => 1 - P( per ogni j hj(p)!=hj(q)) => 1 - (P(hj(p) != hj(q))^L = 1 - (1- S^k)^L
Locality sensitive hashing offline
Fissiamo k e estraiamo i k set di dim m , con m valori fixed
Creiamo fingerprint per vettori analizzati partendo dai k set
Invece di effettuare confronti tra tutte le projections posso utilizzare proprietà transitiva della similarity: se a simile a b e b simile a c => a simile a c
Creo connected components, non ho bisogno di specificare transitivity
Versione online
Creo hash table per L projections
Quando voglio i valori simili effettuo L query su hash table ed ottengo tutti i valori simili tra loro
Trovare duplicati tra documenti
Abbiamo due tipologie di duplicati
Esatti
Uguali che modificano pochi elementi come quelli dinamici
Ovviamente la seconda tipologia più importante da individuare
Per trovare i duplicati possiamo confrontare totalmente i documenti a due a due con grande spesa computazionale, oppure possiamo utilizzare funzioni hash per velocizzare confronto
Tipologie utilizzabili md5 e checksum, molto lenti
Una volta ottenuti fingerprints noi possiamo ordinarli per evitare n*n confronti
Essendo piccoli integer sort non costoso, parliamo di sort lineare
Per migliorare algoritmo di confronto utilizzo la tecnica Karp-Rabin:
Prendiamo vettore di A contenente m bits , applichiamo finger print partendo da un numero random nella seguente maniera (a1 * 2^m-1 + a2 * 2^m-2 … + am * 2^0) mod p.
Basata su tre proprietà
Rolling Hash:
Efficiente da computare poiché abbiamo 1 shift e un’addizione
Probabilità di collisione molto bassa
P(fp(A) = fp(B)) = P( A mod p = B mod p) = P ( (A - B) mod p = 0 )
Numero di divisori non comuni tra A e B, diviso numeri primi in 2, U
Numero di numeri primi totali in 2,U >= U/log(U)
Numero di divisori non comuni tra A e B <= m
Quindi la formula finale sarà m log(U) / U
Sapendo che m spesso è un numero molto piccolo log(U)/ U
E’ un rolling hash quindi permette di computare avendo una finestra che shifta di uno su un documento, hash non ricomputerà documento da zero
Algoritmo
Computiamo finger print fp(P)
Per trovare uguaglianza in documento calcoliamo fp di documento avanzando di un bit per volta
Metodo Shingling
Prendo un documento e lo divido in q-grams di dimensione q, questi q-grams avranno q elementi a partire dalle frasi di un documento
Registriamo quindi il numero di Shingling shared
Q ha valore compreso tra 4 e 8, maggiore valore maggiore sarà strictly comparazione
Jaccard Similarity
Definita come numero di Shingling condivisi tra due documenti su numero di shingling totali
Problema di Jaccard Similarity che sono tanti gli shingling, vorremmo algoritmo che
Permette di risparmiare spazio
Permette di effettuare confronti veloci
Ci permette di lavorare senza documento originale
Abbia un basso numero di falsi positivi
Utilizziamo tecnica Min-Hashing per superare problemi precedentemente descritti
Partendo da Shingles, trasformiamo tramite Karp-Robin fingerprint gli shingle in numeri, dopo questo prendiamo minimo
Permutazione migliore da applicare é a * x + b mod 2^64
Per ogni permutazione prendo solo minimo valore
Due documenti si dicono uguali se permutazione uguale
Possiamo dimostrare che la probabilità che le due permutazioni sono uguali é esattamente la stessa della Jaccard Similarity
Probabilità(min permutazione( A U B ) = min premutazione ( A intersecato B)) = | A intersecato B | / | A unito B |
Creare estimator Jaccard similarity prendendo k = 200 permutazioni differenti e numero di componenti uguali diviso k = jaccard Similarity
Se vogliamo partire da documenti e non perdere informazioni come con Min-Hashing possiamo usare cosine similarity
Spesso documenti potrebbero contenere più volte un termine poiché sono semplicemente più lunghi, cosine similarity elimina questo
Costruiamo dei vettori che partono da valori, se valore presente vettore in quella posizione avrà 1 per esempio
Cosine similarity definita come p * q (prodotto scalare) / || p || * || q ||
Ricorda che prodotto scalare uguale a sommatoria dei prodotti tra due vettori
|| p || = square root ( sommatoria dei valori di un singolo vettore al quadrato)
Piú angolo vettori é grande più cos sim va verso 0, se angolo piccolo si va verso zero
Sketching for cosine similarity
Prendiamo k random vector da {0, 1}ˆn
Mappiamo un vettore p in uno smaller vector sketch in {-1, 1}ˆk
Definito Sketch(p) = segno di p r1, segno di p r2, …, segno di p rk
Positivo se sono stesso lato, negativo altrimenti
p*q = || p || || q || cos alfa , segno positivo se coseno > 0 => 0 < alfa <= pigreco/2
Probabilità che sketch p e sketch q uguali = 1 - alfa/pi greco
Confronto complessità
Naive
O(n^2 * lunghezza documenti)
Sketching
Costo sketch (n * lunghezza documenti) + costo confronti O(nˆ2 * dimensione sketches)
Sketching + clustering
Costo sketch O(n * lunghezza documenti) + O( k numero cluster * dimensione sketches * n * numero di ripetizioni tipicamente basso)
Sketching + LSH
Costo sketch + O( L numero di proiezioni * costo sort), il costo sort é n log n se fit in memoria, sennò aggiungi costo accesso memoria esterna
Costruzione index
Per salvare i tokens prodotti nel chapter precedente abbiamo bisogno di una struttura dati ad hoc
Tipologie di Compressioni
Loseless
Lossy
Strutture utilizzabili per salvare dati:
Array fixed larghezza
Prendiamo 20 bytes per Termini
4 bytes per occorrenza
4 bytes per posting list
Problema spesso chars utilizzati di meno
Dizionario come stringa
Utilizziamo pointer che indicano posizione di word in una stringa enorme
Risparmio 60 percento
Dizionario come stringa blocking
Possiamo utilizzare pointer ad un blocco con k elementi ed ogni elemento contiene posizione di inizio blocco
Search sul dizionario
Utilizziamo binary search su dizionario che viene ordinato in ordine alfabetico, se parola cercata maggiore andiamo avanti senno indietro
2.6 confronti circa
Search su block
Simile alla precedente, ma confronto dopo un tot diventa sequenziale, poiché lista di elementi
Front coding
Parole simili quindi salviamo common prefix e solo ciò che cambia
Per search
Binary
Hash table, funziona ma non efficiente con prefix search
Trie permette invece di fare confronti in modo semplice, unico problema é spazio
Si ottimizza spazio con compact trie che invece di utilizzare per ogni char un pointer, se outgoing 1 possiamo mettere tutto in un nodo unico
Pointerless Trie, migliori come spazio peggiori come ricerca
Correttezza dello spelling
Per verificare se una parola scritta correttamente possiamo utilizzare due tecniche
Correttezza singola parola
Correttezza in relazione al contesto
Correttezza va applicata sia documento, sia alla query per verificare che tutto vada bene
Key del meccanismo é utilizzo di lexicon ossia una serie di termini “approvati” che riteniamo corretti
Questi possono essere sia da un dizionario generico, ma anche relativi alla specifica applicazione
Come confrontiamo termini con dizionario?
Brute force
Non efficiente per verificare ciascun termine quanto dista da termini Lexicon
Edit distance
Utilizzo programmazione dinamica per verificare ciascun elemento quanto dista da elementi Lexicon
Possiamo effettuare per capire distanza operazioni di delete, insert, replace
Edit distance pesata
Possiamo pesare edit distance, grazie a matrice pesata in base a char errati, per esempio in base a tastiera e distanza possiamo pesare
1 D distance
Teoricamente possiamo confrontare tutti i termini ma nella realtà troppo lento più veloce verificare un solo char
L(A-1) <- sostituzioni +(L+1)A <- aggiunte di car +L <- delete di un char =A(2L+1) dove A numero lettere alfabeto, L numero di char stringa
Pro molto veloce come computazione
Cons esoso come risorse, possiamo avere falsi positivi
Overlap distance
K-Gram é una selezione di k chars
Verifichiamo k-grams siano uguali a quelle di confronto
Errore accettabile influenza numero di k grams uguali
L - E * k, L = lunghezza, errore k = k gram … Per essere accettabile valore inferiore di 3
Wild card queries
Abbiamo bisogno di cercare parole del tipo aa, bb, aabb
Per risolvere questo problema utilizziamo permuted index in modo da trovare char * alla fine
Assodato che per termini inglese media di Permuted index 4x dimensione lexicon
Soundex
Utilizzo di termini che suonano allo stesso modo
Manteniamo prima lettera
Trasformiamo nello stesso numero lettere che hanno suono uguale
Alcune lettere verranno trasformate in zero
Rimuovo numeri che si susseguono
Rimuovo zero
Prendo primi quattro valori
Estrazione Keywords
Collocazione parole importante
Non devono essere modificabili
Non sostituibili
Non si può comprendere significato delle parole singolarmente ma nel loro insieme
Primo approccio possibile per prendere keywords
Prendiamo tutte coppie possibili adiacenti
Non va bene poiché la maggior parte delle parole sono stop words
Tag pattern
Secondo approccio più funzionale poiché prendiamo solo coppie da 2 o 3 valori
Tagghiamo ogni parole con Aggettivo Pronome e proposizione
Prendiamo solo coppie o tripletta interessanti
Es. AA non ci interessa
In questo modo possiamo prendere keywords con frequenza maggiore poiché eliminiamo useless
Buon metodo, molto veloce, ma non sempre keywords sono contigue, abbiamo bisogno di più flessibilità
Distance distribution
Poiché distanza non sempre 1 tra termini, creiamo una tabella dove verifichiamo quanto coppie sono interessanti per una determinata finestra di distanza in relazione alla frequenza, distanza può essere negativa e positiva in base a posizione di una parole rispetto all’altra
d= distanza media con cui troviamo le due parole
S = varianza tra le distanze, ovviamente molto alta indica che parola potrebbe non essere interessante
Varianza molto alta indica bi-modal distribution
Per migliorare approccio utilizziamo query logs, possiamo scartare parole se mai apparse nelle query degli utenti
Pearson chi square test
Se valore grande, rispetto a parametro k detto degree of freedom, ci indica che parole non sono posizionate randomicamente
Degree of freedom = (c - 1) * (r - 1), colonne e righe, caso di bigrams c = 2, r = 2
Formula sopra
Per sapere se valore ci va bene utilizziamo tabella of freedom, con cui confrontiamo chi square, in base anche ad errore accettato
Tecnica RAKE, Rapid access key extraction
Fase 1 - trovare candidate keywords
Prendiamo tutte le parole, dividendole tramite stop words, comma, space
Prendiamo contiguous words, che possono essere considerate una unica parole se sono due noun vicini per esempio
Fase 2 - punteggio alle Keywords candidate
Table dei punteggi
Diagonale contiene parola con occorrenza a solo
Calcoliamo degree of parola, data da somma valori sulla riga
Calcoliamo frequency parola, data da valori occorrenza a solo
Calcoliamo ratio -> nostro score
Score per keywords = somma dei valori di ratio di ciascuna keyword e ordiniamo in base ad occorrenze
Fase 3 - Aggiustiamo keywords
Per identificare quali sono interessanti prendiamo keywords con occorrenza minima 2
Punteggio dato da somma punteggi, ovviamente stopwords non hanno punteggio
Fase 4 - Selezionare un terzo delle keywords
Se abbiamo 9 keywords ne selezioniamo top 3
Query processing
Le query sono da rielaborate
Quando abbiamo una query da tre parole come possiamo agire?
Prima idea 2-word indexes
Parola 1 + parola 2, intersechiamo con parola 2 + parola 3
Non sempre esatta ovviamente
Seconda idea indici posizionali
Aggiungiamo ad inverted index posizioni nei documenti
Questo aiuta motori di ricerca ad effettuare proximity queries
Anche computare scores, poiché se parole più vicine, ovviamente migliori
Peso ovviamente aumenta, ma non troppo, inglese 2 fino a 4 per dimensione, grazie ad ottimizzazione di compressione
Terza idea combinare two words con indici posizionali
Quarta idea Soft and
Utilizzato da Google in origine, oggi da molti
And troppo forte
Utilizziamo un progressivo aumento della specificità della query
Prima query totale con tutti i termini
Poi se abbiamo non almeno k risultati effettuiamo query su query meno specifica
Fino ad arrivare alla vector space query dove effettuiamo query per singolo elemento
Rank finale dei docs quando abbiamo almeno k results
Cache per velocizzare queries
Possiamo salvare risultati delle query in una cache
Problema mantenere cache consistency
Possiamo salvare posting list
In questo modo salviamo posting list differenti e poi uniamo valori es. Mario draghi finanziaria, possiamo aver salvato results di Mario draghi e intersechiamo con finanziaria
Tier queries
Creiamo liste di tier in base ad importanza dei documenti
Tier di livello maggiore vanno con memorie più veloci
Se troviamo k docs ci fermiamo, altrimenti scendiamo
Ottimizzazione queries con skip pointers
Possiamo inserire skip pointers tra i vari docs nelle liste in modo da poter saltare quando cerchiamo documenti
Troppi skip pointers pesanti e poco utili
Pochi skip pointers potrebbero essere non utilizzati
Compressione dei documenti
Per ogni documento salviamo versione compressa
riutilizzabile per esempio tramite snippet
poche righe che mostrano main content della pagina
maggiori algoritmi di compressione basati su LZ77
prendiamo parola e cerchiamo se parole successive nel documento riutilizzano lettere precedenti parole
Abbiamo window utilizzabile, da -1 a -9
-1 poche frasi, -9 più ottimizzato, ovviamente dobbiamo utilizzare dimensione che fits in memory
Importante alcune volte LZ77 può occupare dimensioni maggiori di quelle iniziali
Squash compression benchmark
Sito che permette comparazione dei vari algoritmi di compressione per testo che inseriamo
Compressione e networking
Per ottimizzare spazio e sending time utilizzato tecniche di compressione e cache
Caching
Evita di riscaricare oggetti già inviati
Compressione
Elimina ridondanza dei dati inviati
Utilizzo di knowledge per ottimizzare dati inviati
Common knowledge
Conosciamo dati comuni non relazionati ad un file
Inviamo solo Delta compression
Delta compression ottenuta applicando LZ77 tra file nuovo e file vecchio
Efficient Web access
con cache, quando inviamo pagine, possiamo inviare solo modifiche rispetto a cache, possiamo anche unire tutte pagine cached per verificare differenze
Z delta compressor
Comprimere gruppo di files
Effettuiamo LZ77 tra tutti i files nˆ2 compressions più n iniziali
Creiamo graph directed
Ogni edge indica peso LZ77 tra due files
Creiamo alla fine un optimal branching tree ^
Per migliorare
Creare cluster di elementi simili, in modo da aver strongly connected components
Assegnare weights invece di computare z delta
Partial knowledge
Conosciamo file comune
Dobbiamo sincronizzare file
