Ranking di pagine Web Ilaria Bordino. Pagina 2 Ranking delle pagine Raccolta delle pagine html;...

Ranking di pagine Web

Ilaria Bordino

Pagina 2

Ranking delle pagine

• Raccolta delle pagine html;

• Costruzione del webgraph;

• Transformazione dei dati in un formato adeguato;

• Ranking delle pagine del webgraph:– Con Pagerank;

– Con Hits.

Ilaria BordinoMG4J -- Managing GigaBytes for Java

• Colt

• FastUtil

• WebGraph

• MG4J

Librerie per Web IR


Colt: libreria per il calcolo scientifico

• Url: http://hoschek.home.cern.ch/hoschek/colt/

• Libreria matematica sviluppata presso il CERN per estendere le funzionalità supportate da java.math

• Fornisce strutture dati efficienti ed implementazioni scalabili di algoritmi per Off-line and On-line Data Analysis, LinearAlgebra, Multi-dimensional arrays, Statistics, Histogramming,Monte Carlo Simulation, Parallel and Concurrent Programming.


FastUtil

• URL: http://fastutil.dsi.unimi.it/

• FastUtil estende il framework Java Collections supportando strutture type-specific (mappe, insiemi, liste) con un piccolo ingombro di memoria e metodi molto più veloci per l’accesso e l’inserimento.

• Introduce ulteriori caratteristiche e funzionalità non disponibili nelle classi standard (es. Iteratori bidirezionali).

• Oltre ad oggetti e tipi primitivi, fornisce anche supporto per I riferimenti, oggetti che sono confrontati utilizzando l’operatore di uguaglianza piuttosto che equals().

• Include API per una gestione veloce ed efficiente di I/O su file binari o file di testo.


FastUtil

• La versione 5 (Java >=5) introduce pieno supporto per I generics ed è anche fortemente basata su covariant return type overriding: un metodo x() che ritorna un oggetto di classe T può essere sovrascritto da un metodo x() che restituisce un oggetto di classe U (sottoclasse di T)

• Vantaggi:

• Rafforzamento delle interfacce: casting di tipo non più necessario;

• Le implementazioni possono dichiarare il ritorno di tipi più specifici (solitamente più potenti) di quelli dichiarati nelle interfacce corrispondenti.


FastUtil

• Tutte le strutture dati implementano la corrispodente interfaccia standard (ad es. Map per le mappe): possibilità di fare plug in all’interno di codice esistente e di utilizzo con I metodi di accesso tradizionali.

• Quando possibile, implementano interfacce più stringenti che estendono e rafforzano quelle std esponendo molte versioni polimorfiche dei metodi più utilizzati.

• Maggiore vantaggio: miglioramento delle prestazioni sia in termini di efficienza che di occupazione di memoria


Dsiutil

• MutableString: le classi standard messe a disposizione da Java, String e StringBuffer, giacciono agli estremi opposti dello spettro immutabile/modificabile.

• Indicizzare testi su larga scala richiede alcune caratteristiche intemerdie: ad es, usare una stringa modificabile, una volta “congelata”, nello stesso modo ottimizzato di una immutabile

• Allo stessp tempo non abbiamo bisogno della sincronizzazione (che rallenta StringBuffer)

• Controllare se una parola esiste nel dizionario senza creare un nuovo oggetto


Dsiutil

• Altre utilità:

• BitVector – implementazioni flessibili e performanti

• It.unimi.dsi.compression gestisce diversi tipi di codifiche

• ProgessLogger

• I/O

• Package util: fornisce implementazioni di strutture come prefix map e filtri di bloomit


WebGraph

• Framework che consente la manipolazione di grafi di grandi dimensione grazie all’utilizzo di moderne tecniche di compressione. Il framework si compone di:

• UN insieme predefinito di codici (zeta- codes) particolarmente adatti per la memorizzazione di grafi del web.

• Algoritmi in grado di accedere ai grafi compressi senza effettuarne la decompressione, grazie a tecniche di tipo lazy che rimandano la decompressione al momento in cui diventa necessaria.

• Implementazione java completa e documentata.

• http:/webgraph.dsi.unimi.it


WebGraph: Classi fondamentali

• ImmutableGraph: specifica metodi d’accesso per la manipolazione di un grafo immutabile.

• BVGraph: fornisce metodi flessibili e configurabili per memorizzare e utilizzare grafi del web in formato compresso.

• ASCIIGraph può essere usata per leggere grafi rappresentati attraverso un semplice formato testuale.

• ArrayListMutableGraph: per grafi dinamici. Consente di costruire incrementalmente un grafo e di estrarne successivamente una versione immutabile.

• Transform: consente l’applicazione di molte trasformazioni, come simmetrizzazione o calcolo del trasposto.


WebGraph: Rappresentazione compressa• La rappresentazione compressa di un grafo in formato BV è

costituita da 3 file:

• .graph contiene le liste di successori di tutti I nodi nel grafo. Ogni lista di successori è una lista di interi mappata in una sequenza di bit attraverso l’uso di efficienti tecniche di compressione.

• .offsets Memorizza il bit offset per ogni nodo del grafo. L’offset del primo nodo è 0. Per comodità rappresentiamo anche l’offset dell’ultimo nodo, che di fatto fornisce l’indicazione della lunghezza in bit del file .graph

• .properties Contiene una serie di informazioni che sono necessarie per decodificare correttamente I file.offsets e .properties, e anche informazioni statistiche come numero di bit per link.


Caricamento del grafo in memoria• Il modo naturale di usare un grafo compresso è quello di

caricarlo in un array di byte e poi indicizzare I suoi bit usando opportunamente gli offsets.

• Tenere in memoria gli offsets è molto costoso. Altra opzione è quella del caricamento parziale: specifichiamo un offset step J e carichiamo in memoria soltanto un offset ogni J. In questo modo è ancora possibile caricare un grafo in una speciale forma riarrangiata: per ogni J liste di successori memorizziamo prima gli outdegree, poi le restanti liste di successori.

• Per alcune applicazioni (es, calcolo del trasposto) non è necessario calcolare il grafo in memoria: in questo caso possiamo ottenere iteratori che leggono direttamente dal file .graph.

Pagina 14

Utilizzo

delle librerie

Webgraph e

LAW

per il calcolo

di

PageRank

– LAW: collezione software distribuita dal laboratory of Web Algorithmics.

– Contiene il piu' grande insieme di classi e documentazione relativi a PageRank reso disponibile pubblicamente.

– http://law.dsi.unimi.it/software/

Pagina 15

Impostazione

del classpath

– Scaricare e scompattare gli archivi seguenti:

– http://law.dsi.unimi.it/software/law-1.3.1-bin.tar.gz

– http://law.dsi.unimi.it/software/law-deps.tar.gz

– Aggiungere al classpath tutti i file jar contenuti negli archivi suddetti.

Pagina 16

Conversione

del

grafo in formato

Webgraph

– Passo 1: conversione nel formato testuale supportato dal framework.

– Il grafo e' memorizzato in un file chiamato basename.graph-txt. La prima linea contiene il numero di nodi, n. Quindi, il file contiene n linee: la linea i-esima contiene i successori del nodo i in ordine crescente (la numerazione dei nodi va da 0 a n−1). I successori sono separati tra di loro da uno spazio.

– java Text2ASCII graph-name crea un file graph-name.graph-txt contenente il grafo in formato ASCIIGraph

– more graph-name.graph-txt

Pagina 17

Conversione

del

grafo in formato

Webgraph

– Passo 2: conversione dal formato testuale al formato BV.

– java it.unimi.dsi.webgraph.BVGraph -g ASCIIGraph graph-name graph-name

– Produce un grafo compresso in formato BVGraph, con basename graph-name.

– Il grafo risultante viene memorizzato in tre file:

– graph-name.graph

– graph-name.offsets

– graph-name.properties

Pagina 18

Utilizzo

della libreria

LAW

per il calcolo

di

PageRank

– Il package it.unimi.dsi.law.rank contiene una vasta collezione di classi dedicate al calcolo di PageRank.

– PageRank: classe astratta base. Definisce metodi e attributi per il supporto delle computazioni di PageRank o simili.

– PageRank.IterationNumberStoppingCriterion: criterio di terminazione: si ferma quando il numero di iterazioni raggiunge un dato limite.

– PageRankJacobi: calcola PageRank usando il metodo di Jacobi.

– PageRankPowerMethod: calcola PageRank usando il metodo delle potenze.

– ....

Pagina 19

Utilizzo

della libreria

LAW

per il calcolo

di

PageRank

– Il package it.unimi.dsi.law.rank contiene una vasta collezione di classi dedicate al calcolo di PageRank.

– PageRank: classe astratta base. Definisce metodi e attributi per il supporto delle computazioni di PageRank o simili.

– PageRank.IterationNumberStoppingCriterion: criterio di terminazione: si ferma quando il numero di iterazioni raggiunge un dato limite.

– PageRankJacobi: calcola PageRank usando il metodo di Jacobi.

– PageRankPowerMethod: calcola PageRank usando il metodo delle potenze.

– Input: grafo in formato BVGraph

Pagina 20

Calcolo

di

PageRank: esempio

– java it.unimi.dsi.law.rank.PageRankPowerMethod graph-name graph-name

– Calcola sul grafo di nome graph-name il PageRank score di tutti i nodi.

– Output: graph-name.properties, graph-name.ranks (file binario contenente i punteggi calcolati per ogni nodo)

– Lettura degli score calcolati per i nodi del grafo:

– java PrintRanks graph-name.ranks

– Stampa lo score calcolato per tutti i nodi. La riga i-esima contiene lo score del nodo i-esimo.

Pagina 21

Calcolo

di

PageRank: esercizio

– Applicare gli altri metodi supportati per il calcolo di PageRank.

– java it.unimi.dsi.law.rank.PageRankGaussSeidel graph-name graph-name

– java PrintRanks graph-name

– java it.unimi.dsi.law.rank.PageRankJacobi graph-name graph-name


Pagina 22

Esercizio: i

mplementazione

di

HITS

– Applicare gli altri metodi supportati per il calcolo di PageRank.

– java it.unimi.dsi.law.rank.PageRankGaussSeidel graph-name graph-name


– java it.unimi.dsi.law.rank.PageRankJacobi graph-name graph-name


Ranking di pagine Web Ilaria Bordino. Pagina 2 Ranking delle pagine Raccolta delle pagine html;...

Documents

Transcript of Ranking di pagine Web Ilaria Bordino. Pagina 2 Ranking delle pagine Raccolta delle pagine html;...