Matematica e dintorni: storie di contaminazione negli ultimi due secoli

Siena 5-7 aprile 2019 - MATEPRISTEM

La applicazioni informatiche che ci hanno cambiato la vita.

Linda Pagli, Dipartimento di informatica

Università di Pisa www.di.unipi.it/~pagli

•  i motori di ricerca: Google

•  le reti sociali

•  i navigatori

•  la crittografia

•  i sistemi di raccomandazione: Netflix

•  le reti neurali

Applicazioni

Come fa a rispondere in un baleno?

Classifica Google 2017

Categoria: come fare a …

Dal sito Google Trends http://www.google.com/trends/topcharts

♦  Le olive in salamoia. ♦  Il back up. ♦  La marmellata di albicocche. ♦  La carbonara. ♦  Lo screenshot. ♦  Il pesto ♦  La crema pasticcera. ♦  Le bolle di sapone. ♦  Il passaporto. ♦  Il cubo di Rubik.

Perché Google è il motore di ricerca più popolare? Perchè è così veloce a reperire le informazioni nel mare del web? Come fa a dirci proprio quello che cerchiamo?

Accesso al web prima di Google

♦ Sommersi in un mare di informazioni!

Poi arrivò

•  La ricerca è facile •  La risposta è immediata e

quasi sempre soddisfacente. •  L’interfaccia è semplice e

pulita senza pubblicità.

Sergey Brin & Larry Page Parte da un garage e da due studenti di dottorato dell’università di Stanford .

A ogni pagina è associato un voto: il page rank

Page rank

♦ È espresso dal dinamismo della rete, non deciso a priori.

♦ La risposta del motore è un elenco di pagine ordinate in ordine decrescente di page rank.

♦ Non giudica sulla reale qualità delle pagine.

♦ In moltissimi casi funziona bene!

Google è un sistema molto complesso di hardware e software! Gli ingredienti del successo: ♦ Web crowling ♦ Dizionari e indici ♦ Calcolo parallelo e distribuito ♦ Page rank

Web Crawling

• Crawler • Spyder • Robot

42 2 Primo enigma: come fa a dirmi proprio quello che cercavo?

Figura 2.2. Il web crawling: “nuotare” dalla pagina Wikipediadelle canzoni dei Beatles alla pagina Wikipedia della canzone “Allyou need is love”.

no moltissimi link. Ma il web e enorme e un crawlerda solo non potra raccogliere e memorizzare tuttala sua informazione, ma ne considerera soltanto unsottoinsieme. Una possibile strategia e quella di vi-sitare le pagine, non seguendo semplicemente i link,ma andando a analizzare per primi quelli piu impor-tanti, dove l’importanza ancora una volta legata alvoto. Un’altra soluzione adottata piu recentemente estata quella di distribuire il lavoro tra tanti crawler,che possono operare o sotto un controllo centralizzatooppure ciascuno in maniera indipendente, ma con uncontinuo scambio di informazioni riguardo alle paginegia considerate e alla suddivisione del lavoro ancorada eseguire.

Nonostante tutti gli stratagemmi possibili e co-

Gli enormi dizionari Google costruisce un indice analitico di tutte le parole incontrate nello scandaglio continuo delle pagine web.

Un micro-web di 5 pagine Ogni pagina il titolo di una canzone dei Beatles: 1.  All You Need Is Love. 2. Love Me Do. 3. Can’t Buy Me Love. 4. Step Inside Love. 5. Sure to Fall (In Love With You).

2.3 Gli enormi dizionari 49

Figura 2.5. Indice delle parole con, accanto al numero di paginache contiene una parola, anche la sua posizione all’interno dellapagina stessa.

di pagina si indica anche la sua posizione all’internodella pagina.

Dalla figura, per esempio, si ricava che love nellaprima pagina si trova in quinta posizione, nella secon-da in prima e cosı via. Quando si vuole trovare unafrase esattamente come quella richiesta, bisogna cheogni parola della frase si trovi, nella stessa pagina,in posizioni adiacenti. Riferendosi al nostro esempiosi vede che love e in prima posizione nella secondapagina e me in seconda posizione nella stessa pagina.Quindi le due parole sono consecutive e riproduco-no esattamente la frase cercata. Quando il risultato

L’indice

♦ Le parole sono ordinate in ordine alfabetico per le ricerche veloci.

♦ Love appare in tutte le pagine. Si

indica numero di pagina e posizione: L’elenco è 1-5, 2-1, 3-4, 4-3, 5-5.

Ricerca per parole chiave

♦ 2 parole chiave love e me ♦ Love: 1-5, 2-1, 3-4, 4-3, 5-5 ♦ Me: 2-2, 3-3 Algoritmo di Merge Seleziona le pagine comuni: 2 e 3

Ricerca di “Love me”

Pagina 2: Hit! Pagina 3: prima me poi love, la distanza è maggiore (la massima possibile).

Si cerca solo nell’indice

♦ La ricerca degli hits si attua nell’indice soltanto. Solo le pagine del risultato dovranno essere reperite nel dizionario.

♦ Non si devono ricaricare o analizzare le pagine.

♦ Tecniche note prima di Google

Milioni di richieste al minuto

♦ Gestite dai suoi famosi data center dislocati geograficamente in tutto il mondo. Composti da cluster.

♦ Un cluster è composto da migliaia di computer (semplici PC) e contiene varie repliche di tutto il web.

Una singola richiesta (query)

♦ una query a Google in media: –  legge centinaia di Megabytes di dati –  consuma decine di miliardi di cicli di CPU

♦ Google gestisce milioni di queries/sec ♦ La nostra query viene smistata al data

center più vicino o, se è molto occupato, a quello più sgombro

♦ Nel cluster:

Google Web Server

Index Servers Document Server Index server

Per ogni richiesta un GWS deve:

♦ Avviare la ricerca delle parole chiave negli indici e restituire i riferimenti alle pagine web che contengono le parole chiave (hit list)

♦ Intersecare le hit list per ciascuna parola chiave per determinare i documenti rilevanti e reperirli.

♦ Calcolare il voto (rank) di ciascuna pagina per ordinare il risultato.

Ricerca: 2 livelli di parallelismo La parola da cercare è replicata in tante copie. 1. L’indice è diviso in pezzi, ciascuno gestito da un insieme di macchine (index servers) per la ricerca parallela della parola sul pezzo. 2. La parola viene mandata in parallelo a tutti i pezzi.

♦  Risposta: Recupero dei documenti della risposta nell’archivio che contiene la copia completa del web a disposizione del cluster. Come nella fase della ricerca i document server effettuano la ricerca contemporanea dei dei documenti e in parallelo sui pezzi. In questa fase si assegnano ai documenti: titolo, Riassunto e un estratto che mostra la parole chiave cercata nel contesto del documento.

Page rank

♦ Come fare le olive in salamoia. 2 pagine web danno la ricetta

“giallozafferano” “sale&pepe”

Strategia immediata per dare il voto: Contare il numero di riferimenti da altre pagine alla pagina in questione. .

Page rank Se contiamo il numero di riferimenti le due pagine coincidono. Ma una cosa è la menzione di un tizio qualsiasi altra cosa la menzione di un personaggio famoso. Deve contare la popolarità (rank) della pagina che contiene la citazione e quante citazioni fa.

!

Calcolo del page rank

R(Sale&pepe)= rank(Mario)/# link(Mario)=1/2 R(giallozafferano)= rank(chef)/#link(chef)=100/100 =1

Page Rank

Page Rank di P = Σ Page Rank di q

numero di pagine citate da q

q cita p

P

q2

q1

=rank( q1)/5 +rank( q2)/1 + …….

♦ Nel nostro esempio il personaggio famoso è anche uno chef, quindi autorevole, ma poteva essere anche un calciatore famoso e il risultato sarebbe stato uguale.

Importante è la popolarità sul web non l’autorevolezza

Il Page Rank non è l’unico parametro considerato

♦ Altri tenuti rigorosamente segreti.

♦ Probabilmente: –  Le home page hanno rank più alto –  Il fatto che una pagina sia fresca –  ….molti altri