Compressione di grafi
Il grafo del web in pochi bit per arco
Sebastiano Vigna
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
il primo è
, che è negativo: diventa
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
il primo è
, che è negativo: diventa
gli altri:
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
il primo è
, che è negativo: diventa
gli altri:
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
6403
2 byte
33504
3 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
6403
2 byte
33504
3 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
6403
2 byte
33504
3 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
in arancione il grado, nei primi byte di ogni lista
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
in arancione il grado, nei primi byte di ogni lista
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
in arancione il grado, nei primi byte di ogni lista
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
offset in bit
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
offset in bit
in arancione il grado più uno, in γ, all'inizio di ogni lista
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
offset in bit
in arancione il grado più uno, in γ, all'inizio di ogni lista
E gli offset?
Gli offset sono
numeri crescenti: la successione giusta per
Elias–Fano
Con
bit di liste e
nodi bastano
bit per nodo, e l'accesso a un offset resta veloce
Per il crawl del 2015, compresso a circa 0,9 bit per arco (lo vedremo): circa 9 bit per nodo, 1,2 GB
E gli offset?
Gli offset sono
numeri crescenti: la successione giusta per
Elias–Fano
Con
bit di liste e
nodi bastano
bit per nodo, e l'accesso a un offset resta veloce
Per il crawl del 2015, compresso a circa 0,9 bit per arco (lo vedremo): circa 9 bit per nodo, 1,2 GB
E gli offset?
Gli offset sono
numeri crescenti: la successione giusta per
Elias–Fano
Con
bit di liste e
nodi bastano
bit per nodo, e l'accesso a un offset resta veloce
Per il crawl del 2015, compresso a circa 0,9 bit per arco (lo vedremo): circa 9 bit per nodo, 1,2 GB
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Demo: codificare una lista
Una lista di successori, i suoi scarti, la codifica a byte e quella con γ. Si possono scegliere liste diverse e modificarle.
Consecutività e somiglianza
Consecutività
(
consecutivity
): molti successori sono consecutivi, come le pagine di una cartella: scarti uguali a 1
Somiglianza
(
similarity
): pagine vicine hanno liste simili, perché condividono menu, barre laterali, piè di pagina
Gli scarti sfruttano la consecutività, ma non la somiglianza: ogni lista ripete in gran parte la precedente
1002
1003
1004
1005
consecutività: scarti uguali a 1 lungo le righe
Consecutività e somiglianza
Consecutività
(
consecutivity
): molti successori sono consecutivi, come le pagine di una cartella: scarti uguali a 1
Somiglianza
(
similarity
): pagine vicine hanno liste simili, perché condividono menu, barre laterali, piè di pagina
Gli scarti sfruttano la consecutività, ma non la somiglianza: ogni lista ripete in gran parte la precedente
1002
1003
1004
1005
consecutività: scarti uguali a 1 lungo le righe
somiglianza: le stesse colonne in righe vicine
Consecutività e somiglianza
Consecutività
(
consecutivity
): molti successori sono consecutivi, come le pagine di una cartella: scarti uguali a 1
Somiglianza
(
similarity
): pagine vicine hanno liste simili, perché condividono menu, barre laterali, piè di pagina
Gli scarti sfruttano la consecutività, ma non la somiglianza: ogni lista ripete in gran parte la precedente
1002
1003
1004
1005
consecutività: scarti uguali a 1 lungo le righe
somiglianza: le stesse colonne in righe vicine
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
consecutività
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
consecutività
somiglianza
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
: il grafo trasposto
trasporre scambia righe e colonne: orizzontale ↔ verticale
consecutività
somiglianza
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
: il grafo trasposto
trasporre scambia righe e colonne: orizzontale ↔ verticale
consecutività
somiglianza
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
aggiuntivi
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
aggiuntivi
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
aggiuntivi
lista di
= elementi copiati dal riferimento
aggiuntivi
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
blocchi:
; si comincia sempre copiando, quindi qui il primo blocco è vuoto
in
si scrivono
: il primo, che può essere
, aumentato di uno
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
blocchi:
; si comincia sempre copiando, quindi qui il primo blocco è vuoto
in
si scrivono
: il primo, che può essere
, aumentato di uno
con riferimento a
: 32 bit invece di 80
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
blocchi:
; si comincia sempre copiando, quindi qui il primo blocco è vuoto
in
si scrivono
: il primo, che può essere
, aumentato di uno
con riferimento a
: 32 bit invece di 80
qui la lista di copia costerebbe 13 bit, i blocchi ne costano 14
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
con
,
non potrebbe usare
: la catena sarebbe lunga 3
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
con
,
non potrebbe usare
: la catena sarebbe lunga 3
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
con
,
non potrebbe usare
: la catena sarebbe lunga 3
Demo: comprimere un grafo
La matrice di adiacenza di un piccolo grafo e i bit per arco con le diverse codifiche. Si possono cambiare ordine, finestra W, catene R, e trasporre.
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
eu-2015-host
3,13 bit
uk-2014-host
6,87 bit
hollywood-2011
4,88 bit
ljournal-2008
10,91 bit
itwiki-2013
11,04 bit
fb-current
12,30 bit
enwiki-2025
13,09 bit
twitter-2010
13,90 bit
web
host
reti sociali
Wikipedia
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit (4%)
uk-2014
1,03 bit (4%)
it-2004
1,41 bit (6%)
gsh-2015
1,61 bit (6%)
eu-2015-host
3,13 bit (16%)
uk-2014-host
6,87 bit (34%)
hollywood-2011
4,88 bit (31%)
ljournal-2008
10,91 bit (55%)
itwiki-2013
11,04 bit (66%)
fb-current
12,30 bit (53%)
enwiki-2025
13,09 bit (67%)
twitter-2010
13,90 bit (64%)
web
host
reti sociali
Wikipedia
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
ordine qualunque
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Demo: propagazione di etichette
Un grafo con cluster nascosti, numerato a caso; a destra la matrice di adiacenza, con i nodi ordinati per etichetta.
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
‹
1
/
›
Compressione di grafi
Il grafo del web in pochi bit per arco
Sebastiano Vigna
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Da dove partiamo
Il crawler produce un grafo: un nodo per ogni pagina, un arco per ogni link
Numeriamo i nodi da
a
(escluso); per ogni nodo
ci serve la lista ordinata dei suoi
successori
Due modi di usarlo: chiedere i successori di un nodo qualunque, oppure scorrere tutto il grafo, nodo per nodo
Un crawl europeo del 2015:
miliardi di pagine,
miliardi di link
PageRank, centralità, visite: tutti scorrono il grafo molte volte, quindi deve occupare poco spazio
Il problema di oggi: quanti bit servono per un arco, senza rinunciare a un accesso veloce?
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Liste di adiacenza
La rappresentazione più naturale: per ogni nodo, un vettore con i suoi successori
Il grafo non cambia più, quindi ogni vettore ha esattamente la sua lunghezza
Ma è comunque un oggetto separato, raggiunto con un puntatore da 8 byte
Con un miliardo di nodi sono un miliardo di allocazioni, sparse in memoria
Scorrere il grafo salta da un punto all'altro della memoria: niente località
Semplice, ma occupa molto spazio ed è lenta da scorrere (cattivo uso della cache)
nodi
ogni lista: un oggetto in memoria, con la sua lunghezza (in azzurro)
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
Rappresentazione compressa per righe
Rappresentazione compressa per righe
(
compressed sparse row
, CSR): tutte le liste in fila, in un unico vettore di successori
Un vettore di
offset
: la lista di
va dalla posizione offset
a offset
Il grado di
è offset
: non serve memorizzarlo
Spazio:
successori da 32 bit, o da 64 se i nodi sono più di
, e
offset da 64 bit: 32 o 64 bit per arco
Per il crawl del 2015 bastano 32 bit: 367 GB di successori, più 8,6 GB di offset
Due sole allocazioni e una scansione sequenziale: ma 32 o 64 bit per arco sono ancora troppi
offset
successori
successori di
: da offset
a offset
; grado
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
L'ordine conta
Come numerare i nodi? In ordine casuale, i successori di
sono sparsi fra
e
Numeriamo le pagine in
ordine lessicografico degli URL
: le pagine di uno stesso sito, e della stessa cartella, diventano vicine
La maggior parte dei link è
navigazionale
: menu, indici, pagine sorelle dello stesso sito
Quindi in molti archi
la differenza
è piccola: è la
località
(
locality
)
Nell'esempio: il sito www.esempio.it occupa i numeri da 1000 a 1010
in azzurro i successori di 1003 (arancione)
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
il primo è
, che è negativo: diventa
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
il primo è
, che è negativo: diventa
gli altri:
Gli scarti
I successori sono ordinati:
, dove
è il grado
Invece dei successori memorizziamo gli
scarti
(
gap
):
,
, …
Il primo successore si scrive come differenza
dal nodo stesso; ma può essere negativo
Si rimedia alternando: 0, −1, 1, −2, 2, … diventano 1, 2, 3, 4, 5, …; così tutti gli scarti sono positivi
Per la località gli scarti sono piccoli: vince un codice che li scrive in pochi bit
lista di
scarti
il primo è
, che è negativo: diventa
gli altri:
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
6403
2 byte
33504
3 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
6403
2 byte
33504
3 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Il codice a byte a lunghezza variabile
Codice a byte a lunghezza variabile
(
variable-byte
): il numero in binario, a gruppi di 7 bit
Ogni gruppo va in un byte, preceduto dal
bit di continuazione
, che dice se segue un altro byte
Da
a
un byte, fino a
due, e così via
Si decodifica a byte interi: è semplice e veloce
Ma anche lo scarto 1, frequentissimo, costa 8 bit
6
1 byte
1
1 byte
6403
2 byte
33504
3 byte
in arancione il bit di continuazione: 1 = segue un altro byte
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
in arancione il grado, nei primi byte di ogni lista
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
in arancione il grado, nei primi byte di ogni lista
Un CSR compresso
Concateniamo le liste codificate in un vettore di byte; gli offset sono ora in byte
Nel CSR il grado era la differenza fra due offset; ora gli offset contano byte, non successori
Ma il grado lo vogliamo in tempo costante: lo scriviamo nei primi byte di ogni lista, con il codice a byte
Così sappiamo quanti scarti leggere, e per scorrere il grafo in successione gli offset non servono
Sulla lista di
: 15 byte, cioè 120 bit, invece di 352
lista di 1002: 21 byte
lista di 1003: 15 byte
lista di 1004: 16 byte
byte
offset in byte
in arancione il grado, nei primi byte di ogni lista
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
offset in bit
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
offset in bit
in arancione il grado più uno, in γ, all'inizio di ogni lista
Un flusso di bit
sugli interi positivi:
,
,
,
, …:
bit per
, e lo scarto 1 ne costa uno
Le liste in
, una dopo l'altra, in un unico flusso di bit; gli offset sono in bit
In testa a ogni lista il grado, che può essere 0: si scrive il grado più uno
Sulla lista di
: 80 bit, cioè 7,3 bit per arco
1002: 140 bit
1003: 80 bit
1004: 81 bit
bit
offset in bit
in arancione il grado più uno, in γ, all'inizio di ogni lista
E gli offset?
Gli offset sono
numeri crescenti: la successione giusta per
Elias–Fano
Con
bit di liste e
nodi bastano
bit per nodo, e l'accesso a un offset resta veloce
Per il crawl del 2015, compresso a circa 0,9 bit per arco (lo vedremo): circa 9 bit per nodo, 1,2 GB
E gli offset?
Gli offset sono
numeri crescenti: la successione giusta per
Elias–Fano
Con
bit di liste e
nodi bastano
bit per nodo, e l'accesso a un offset resta veloce
Per il crawl del 2015, compresso a circa 0,9 bit per arco (lo vedremo): circa 9 bit per nodo, 1,2 GB
E gli offset?
Gli offset sono
numeri crescenti: la successione giusta per
Elias–Fano
Con
bit di liste e
nodi bastano
bit per nodo, e l'accesso a un offset resta veloce
Per il crawl del 2015, compresso a circa 0,9 bit per arco (lo vedremo): circa 9 bit per nodo, 1,2 GB
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Il confronto su una lista
La lista di
ha 11 successori: 1000, 1001, 1002, 1004, 1005, 1006, 1008, 1009, 1010, 7413 e 40917
32 bit ciascuno: 352 bit
Scarti con il codice a byte, grado compreso: 120 bit, ma gli scarti uguali a 1 costano un byte ciascuno
Scarti con
, grado compreso: 80 bit; gli scarti uguali a 1 costano un bit
Il costo vero sta negli scarti grandi: 6403 e 33504 occupano 56 bit su 80
32 bit
byte, con il grado
γ, con il grado
la lista di
: 11 successori, in bit
Demo: codificare una lista
Interactive Demo
Una lista di successori, i suoi scarti, la codifica a byte e quella con γ. Si possono scegliere liste diverse e modificarle.
Consecutività e somiglianza
Consecutività
(
consecutivity
): molti successori sono consecutivi, come le pagine di una cartella: scarti uguali a 1
Somiglianza
(
similarity
): pagine vicine hanno liste simili, perché condividono menu, barre laterali, piè di pagina
Gli scarti sfruttano la consecutività, ma non la somiglianza: ogni lista ripete in gran parte la precedente
1002
1003
1004
1005
consecutività: scarti uguali a 1 lungo le righe
Consecutività e somiglianza
Consecutività
(
consecutivity
): molti successori sono consecutivi, come le pagine di una cartella: scarti uguali a 1
Somiglianza
(
similarity
): pagine vicine hanno liste simili, perché condividono menu, barre laterali, piè di pagina
Gli scarti sfruttano la consecutività, ma non la somiglianza: ogni lista ripete in gran parte la precedente
1002
1003
1004
1005
consecutività: scarti uguali a 1 lungo le righe
somiglianza: le stesse colonne in righe vicine
Consecutività e somiglianza
Consecutività
(
consecutivity
): molti successori sono consecutivi, come le pagine di una cartella: scarti uguali a 1
Somiglianza
(
similarity
): pagine vicine hanno liste simili, perché condividono menu, barre laterali, piè di pagina
Gli scarti sfruttano la consecutività, ma non la somiglianza: ogni lista ripete in gran parte la precedente
1002
1003
1004
1005
consecutività: scarti uguali a 1 lungo le righe
somiglianza: le stesse colonne in righe vicine
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
consecutività
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
consecutività
somiglianza
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
: il grafo trasposto
trasporre scambia righe e colonne: orizzontale ↔ verticale
consecutività
somiglianza
Due facce della stessa medaglia
Disegniamo la matrice di adiacenza del grafo
: una riga per nodo, un punto per ogni successore
Consecutività: tratti
orizzontali
, cioè scarti uguali a 1 lungo una riga
Somiglianza: tratti
verticali
, cioè lo stesso successore in righe vicine
Trasponendo, righe e colonne si scambiano: la somiglianza in
è la consecutività in
, e viceversa
Più in generale: scarti piccoli in un grafo vogliono dire liste simili nel suo trasposto
: righe = liste dei successori
: il grafo trasposto
trasporre scambia righe e colonne: orizzontale ↔ verticale
consecutività
somiglianza
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
aggiuntivi
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
aggiuntivi
Codifica per riferimenti
Per la lista di
scegliamo un
riferimento
: la lista di
, per un piccolo
(
: nessun riferimento)
Una
lista di copia
(
copy list
): un bit per ogni successore di
, 1 se è anche successore di
I successori di
che non vengono copiati sono i
successori aggiuntivi
, codificati con gli scarti come prima
Si scrivono: il grado,
, la lista di copia, i successori aggiuntivi (in
il grado e
, che possono essere 0, aumentati di uno)
Si decodifica con una fusione: copiati dal riferimento e aggiuntivi, entrambi già ordinati
lista di 1003
riferimento 1002
in verde gli elementi comuni
lista di copia
aggiuntivi
lista di
= elementi copiati dal riferimento
aggiuntivi
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
blocchi:
; si comincia sempre copiando, quindi qui il primo blocco è vuoto
in
si scrivono
: il primo, che può essere
, aumentato di uno
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
blocchi:
; si comincia sempre copiando, quindi qui il primo blocco è vuoto
in
si scrivono
: il primo, che può essere
, aumentato di uno
con riferimento a
: 32 bit invece di 80
Blocchi di copia
Se la lista di copia alterna lunghi tratti di uni e di zeri, conviene scriverne le lunghezze
Si parte con un blocco da copiare (che può essere vuoto), poi si alternano blocchi da saltare e da copiare
Le lunghezze dei blocchi si scrivono in
; il primo, che può essere 0, aumentato di uno
Esempio:
diventa
Qui però i tratti sono corti: i blocchi costano 14 bit, la lista di copia 13
riferimento 1002
lista di copia
copia 0
salta 1
copia 3
salta 1
copia 3
salta 1
copia 3
salta 1
blocchi:
; si comincia sempre copiando, quindi qui il primo blocco è vuoto
in
si scrivono
: il primo, che può essere
, aumentato di uno
con riferimento a
: 32 bit invece di 80
qui la lista di copia costerebbe 13 bit, i blocchi ne costano 14
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Quale riferimento?
Si fissa una
finestra
: si provano come riferimento le
liste precedenti, e anche nessun riferimento
Si sceglie la codifica più corta
Per
conviene la pagina principale,
: 28 bit invece di 80
Su tutto il sito dell'esempio, in bit per arco: 11,6 con il codice a byte, 8,7 con
, 3,5 con i riferimenti (con
)
Una finestra più ampia di solito comprime un po' meglio, ma rallenta la compressione e l'accesso (cattivo uso della cache)
lista di
, finestra
: nessun riferimento
: 1002
: 1001 (indice dei corsi)
: 1000 (pagina principale)
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
con
,
non potrebbe usare
: la catena sarebbe lunga 3
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
con
,
non potrebbe usare
: la catena sarebbe lunga 3
Catene di riferimenti
Per decodificare la lista di
serve la lista di
, che può avere a sua volta un riferimento, e così via
In lettura sequenziale non costa niente: le ultime
liste decodificate si tengono in memoria
Nell'accesso diretto, invece, una lunga catena vuol dire decodificare molte liste
Si fissa la lunghezza massima
delle catene: il compressore non usa riferimenti che la superano
regola spazio e velocità: con
si comprime al massimo, ma l'accesso diretto può diventare lentissimo
Con
fissato la scelta, lista per lista, è avida (
greedy
): allargare
può anche peggiorare
per decodificare
servono, una dopo l'altra, 4 liste precedenti
con
,
non potrebbe usare
: la catena sarebbe lunga 3
Demo: comprimere un grafo
Interactive Demo
La matrice di adiacenza di un piccolo grafo e i bit per arco con le diverse codifiche. Si possono cambiare ordine, finestra W, catene R, e trasporre.
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Rispetto a un grafo aleatorio
Un grafo con
nodi e
archi è uno dei
possibili: per un grafo aleatorio servono
bit
Se
è molto più piccolo di
:
, quindi
, e
Per il crawl del 2015 sono circa 25 bit per arco; con un buon ordine dei nodi il web ne usa 0,9, il 3,6%
Per scorrerlo bastano 10 GB invece di 367: il web di un continente sta in un portatile
Il trasposto si comprime ancora meglio, 0,72 bit per arco: le pagine principali di un sito sono puntate da pagine consecutive
Il web è molto lontano da un grafo aleatorio: siti e link navigazionali sono ridondanza, che un buon ordine permette di sfruttare
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit
uk-2014
1,03 bit
it-2004
1,41 bit
gsh-2015
1,61 bit
eu-2015-host
3,13 bit
uk-2014-host
6,87 bit
hollywood-2011
4,88 bit
ljournal-2008
10,91 bit
itwiki-2013
11,04 bit
fb-current
12,30 bit
enwiki-2025
13,09 bit
twitter-2010
13,90 bit
web
host
reti sociali
Wikipedia
Quanto si comprime il web
Grafi del web raccolti da crawler e compressi con queste tecniche (e altre, come gli intervalli di successori consecutivi)
Numeri ottenuti dopo un buon riordinamento dei nodi, che vedremo
Il web: meno di 2 bit per arco
Grafi degli host (un nodo per sito): già molto meno comprimibili; poi reti sociali, Wikipedia
Fra parentesi: la percentuale del limite per un grafo aleatorio con gli stessi
e
eu-2015
0,90 bit (4%)
uk-2014
1,03 bit (4%)
it-2004
1,41 bit (6%)
gsh-2015
1,61 bit (6%)
eu-2015-host
3,13 bit (16%)
uk-2014-host
6,87 bit (34%)
hollywood-2011
4,88 bit (31%)
ljournal-2008
10,91 bit (55%)
itwiki-2013
11,04 bit (66%)
fb-current
12,30 bit (53%)
enwiki-2025
13,09 bit (67%)
twitter-2010
13,90 bit (64%)
web
host
reti sociali
Wikipedia
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Perché Wikipedia no
Wikipedia in inglese: 13 bit per arco, il 67% del limite per un grafo aleatorio
Ed è già ben riordinata: anche con il miglior ordine noto resta oltre i 10 bit per arco
I link fra voci sono semantici, non navigazionali: si parla di una cosa, si mette un link a quella cosa
Quindi c'è poca ridondanza: anche nel miglior ordine, poche liste simili e pochi successori consecutivi
In ordine alfabetico dei titoli andrebbe molto peggio: niente località, niente somiglianza
Lo stesso vale per le reti sociali: Twitter 13,9 bit per arco, Facebook 12,3
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
ordine qualunque
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Riordinare i nodi
Vogliamo un ordine in cui nodi vicini abbiano liste simili, e successori vicini fra loro
Un qualunque algoritmo di
clustering
aiuta: si numerano di seguito i nodi di ogni cluster
Archi dentro un cluster: scarti piccoli, liste che si somigliano; i riferimenti trovano buone liste da copiare
Con un clustering gerarchico si ordina ricorsivamente anche dentro i cluster
Nella demo, Wikipedia ordinata per argomento si comprime molto meglio che in ordine alfabetico
nodi dello stesso cluster numerati di seguito
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Propagazione di etichette
Propagazione di etichette
(
label propagation
): un clustering semplicissimo
All'inizio ogni nodo ha un'etichetta diversa; gli archi si considerano senza verso
A turno, in ordine casuale, ogni nodo prende l'etichetta più diffusa fra i suoi vicini (a parità, se può tiene la sua)
Si ripete finché nessun nodo cambia: i nodi di un cluster, molto collegati fra loro, finiscono con la stessa etichetta
Poi si numerano di seguito i nodi con la stessa etichetta
Non usa gli URL: funziona per qualunque grafo
un momento della propagazione
→
prende il blu
Demo: propagazione di etichette
Interactive Demo
Un grafo con cluster nascosti, numerato a caso; a destra la matrice di adiacenza, con i nodi ordinati per etichetta.
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL
Riepilogo
CSR: tutte le liste in fila e un vettore di offset; 32 o 64 bit per arco
Scarti fra successori ordinati, con il grado in testa, scritti con un codice a lunghezza variabile: allineato al byte, o bit per bit come
Ordine per URL: località (scarti piccoli), consecutività (scarti uguali a 1), somiglianza (liste che si ripetono)
Riferimenti: la lista di copia, o i blocchi di copia, più i successori aggiuntivi; finestra
e catene di lunghezza al più
Ben riordinato, il web scende sotto i 2 bit per arco; Wikipedia e le reti sociali restano oltre i 10
Un buon ordine viene da un clustering, come la propagazione di etichette, anche senza URL