Mapa

Comprimiendo Grafos de la Web Gonzalo Navarro ´ de la Web Centro de Investigacion ´ Departamento de Ciencias de la Computacion Universidad de Chile ´ con los estudiantes Francisco Claude y Rodrigo Gonzalez ´ En colaboracion

G. Navarro

Comprimiendo Grafos de la Web

Mapa

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

Mapa

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

Mapa

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

Mapa

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

Mapa

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion Estructuras de Datos Compactas I

Modificadas para ocupar poco espacio.

I

´ Y eso no es compresion?

I

Deben retener su funcionalidad y acceso directo.

I

´ si la memoria es tan barata? Para que,

I

Mejora el rendimiento debido a la jerarqu´ıa de memoria. ´ populares por motivos tecnologicos. ´ Cada vez mas

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion Estructuras de Datos Compactas I

Modificadas para ocupar poco espacio.

I

´ Y eso no es compresion?

I

Deben retener su funcionalidad y acceso directo.

I

´ si la memoria es tan barata? Para que,

I

Mejora el rendimiento debido a la jerarqu´ıa de memoria. ´ populares por motivos tecnologicos. ´ Cada vez mas

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion Estructuras de Datos Compactas I

Modificadas para ocupar poco espacio.

I

´ Y eso no es compresion?

I

Deben retener su funcionalidad y acceso directo.

I

´ si la memoria es tan barata? Para que,

I

Mejora el rendimiento debido a la jerarqu´ıa de memoria. ´ populares por motivos tecnologicos. ´ Cada vez mas

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion Estructuras de Datos Compactas I

Modificadas para ocupar poco espacio.

I

´ Y eso no es compresion?

I

Deben retener su funcionalidad y acceso directo.

I

´ si la memoria es tan barata? Para que,

I

Mejora el rendimiento debido a la jerarqu´ıa de memoria. ´ populares por motivos tecnologicos. ´ Cada vez mas

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion Estructuras de Datos Compactas I

Modificadas para ocupar poco espacio.

I

´ Y eso no es compresion?

I

Deben retener su funcionalidad y acceso directo.

I

´ si la memoria es tan barata? Para que,

I

Mejora el rendimiento debido a la jerarqu´ıa de memoria. ´ populares por motivos tecnologicos. ´ Cada vez mas

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion Estructuras de Datos Compactas I

Modificadas para ocupar poco espacio.

I

´ Y eso no es compresion?

I

Deben retener su funcionalidad y acceso directo.

I

´ si la memoria es tan barata? Para que,

I

Mejora el rendimiento debido a la jerarqu´ıa de memoria. ´ populares por motivos tecnologicos. ´ Cada vez mas

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Motivacion ´ de Grafos Compresion I

Util para ejecutar, en memoria principal, algoritmos sobre grafos grandes.

I

´ Algoritmos como que?

I

Descubrir comunidades, calcular PageRank, miner´ıa de ´ ejemplos en la charla de Claudio) grafos, ... (mas ´ basicas: ´ Consideraremos las operaciones mas

I

I I I I

Obtener los vecinos de un nodo u: v , (u, v ) ∈ E. Obtener los vecinos reversos de un nodo u: v , (v , u) ∈ E. Calcular el grado interior/exterior de un nodo u. Verificar la existencia de arista (u, v ) in E.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Entrop´ıa (Emp´ırica) I

Entrop´ıa binaria: si hay n0 ceros y n1 unos en B (n0 + n1 = n = |B|) H0 (B) =

I

n0 n n1 n log + log n n0 n n1

Entrop´ıa de orden cero: si hay na ocurrencias de a en S, X na n H0 (S) = log n na a∈Σ

I

´ de Σ que asigne Cota inferior a cualquier codificacion ´ siempre el mismo codigo al mismo s´ımbolo. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Entrop´ıa (Emp´ırica) I

Entrop´ıa binaria: si hay n0 ceros y n1 unos en B (n0 + n1 = n = |B|) H0 (B) =

I

n0 n n1 n log + log n n0 n n1

Entrop´ıa de orden cero: si hay na ocurrencias de a en S, X na n H0 (S) = log n na a∈Σ

I

´ de Σ que asigne Cota inferior a cualquier codificacion ´ siempre el mismo codigo al mismo s´ımbolo. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Entrop´ıa (Emp´ırica) I

Entrop´ıa binaria: si hay n0 ceros y n1 unos en B (n0 + n1 = n = |B|) H0 (B) =

I

n0 n n1 n log + log n n0 n n1

Entrop´ıa de orden cero: si hay na ocurrencias de a en S, X na n H0 (S) = log n na a∈Σ

I

´ de Σ que asigne Cota inferior a cualquier codificacion ´ siempre el mismo codigo al mismo s´ımbolo. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Entrop´ıa (Emp´ırica)

I

Entrop´ıa de orden k : si SA son los caracteres que siguen a las ocurrencias de A en S, Hk (S) =

1 X |SA |H0 (SA ) n k A∈Σ

I

Cota inferior a codificaciones que consideran los k s´ımbolos precedentes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Entrop´ıa (Emp´ırica)

I

Entrop´ıa de orden k : si SA son los caracteres que siguen a las ocurrencias de A en S, Hk (S) =

1 X |SA |H0 (SA ) n k A∈Σ

I

Cota inferior a codificaciones que consideran los k s´ımbolos precedentes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion Matriz de Incidencia a b c d b

e

a b c d e

a

c

d e

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Matriz de Incidencia I

Con n nodos y e aristas, ocupa n2 bits.

I

Responde existencia en tiempo O(1).

I

Encuentra todos los vecinos directos/reversos en O(n).

I

Calcula grado interior/exterior en O(n).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Matriz de Incidencia I

Con n nodos y e aristas, ocupa n2 bits.

I

Responde existencia en tiempo O(1).

I

Encuentra todos los vecinos directos/reversos en O(n).

I

Calcula grado interior/exterior en O(n).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Matriz de Incidencia I

Con n nodos y e aristas, ocupa n2 bits.

I

Responde existencia en tiempo O(1).

I

Encuentra todos los vecinos directos/reversos en O(n).

I

Calcula grado interior/exterior en O(n).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Matriz de Incidencia I

Con n nodos y e aristas, ocupa n2 bits.

I

Responde existencia en tiempo O(1).

I

Encuentra todos los vecinos directos/reversos en O(n).

I

Calcula grado interior/exterior en O(n).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion Lista de Adyacencia b

a: d,c,b

a: b

b: d,c,a

b: a

c: d

c: a,b,e

d:

d: a,b,c,e

e: d,c

e:

a

c

d e

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Lista de Adyacencia I

Con n nodos y e aristas, ocupa n log e + e log n bits.

I

Encuentra cada vecino en tiempo O(1).

I

Calcula grado exterior en tiempo O(1).

I

Responde existencia en tiempo O(n).

I

Necesita otro tanto para los reversos.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Lista de Adyacencia I

Con n nodos y e aristas, ocupa n log e + e log n bits.

I

Encuentra cada vecino en tiempo O(1).

I

Calcula grado exterior en tiempo O(1).

I

Responde existencia en tiempo O(n).

I

Necesita otro tanto para los reversos.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Lista de Adyacencia I

Con n nodos y e aristas, ocupa n log e + e log n bits.

I

Encuentra cada vecino en tiempo O(1).

I

Calcula grado exterior en tiempo O(1).

I

Responde existencia en tiempo O(n).

I

Necesita otro tanto para los reversos.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Lista de Adyacencia I

Con n nodos y e aristas, ocupa n log e + e log n bits.

I

Encuentra cada vecino en tiempo O(1).

I

Calcula grado exterior en tiempo O(1).

I

Responde existencia en tiempo O(n).

I

Necesita otro tanto para los reversos.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Lista de Adyacencia I

Con n nodos y e aristas, ocupa n log e + e log n bits.

I

Encuentra cada vecino en tiempo O(1).

I

Calcula grado exterior en tiempo O(1).

I

Responde existencia en tiempo O(n).

I

Necesita otro tanto para los reversos.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Relaciones Binarias I

´ Con tecnicas muy novedosas de estructuras sucintas para relaciones binarias...

I

... se puede conseguir e log(n2 /e) (1 + o(1)) bits...

I

... y responder todo en tiempo O(log log n).

I

Obtiene lo mejor de los dos mundos...

I

... pero aun ´ no es demasiado bueno para la Web.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Relaciones Binarias I

´ Con tecnicas muy novedosas de estructuras sucintas para relaciones binarias...

I

... se puede conseguir e log(n2 /e) (1 + o(1)) bits...

I

... y responder todo en tiempo O(log log n).

I

Obtiene lo mejor de los dos mundos...

I

... pero aun ´ no es demasiado bueno para la Web.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Relaciones Binarias I

´ Con tecnicas muy novedosas de estructuras sucintas para relaciones binarias...

I

... se puede conseguir e log(n2 /e) (1 + o(1)) bits...

I

... y responder todo en tiempo O(log log n).

I

Obtiene lo mejor de los dos mundos...

I

... pero aun ´ no es demasiado bueno para la Web.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Relaciones Binarias I

´ Con tecnicas muy novedosas de estructuras sucintas para relaciones binarias...

I

... se puede conseguir e log(n2 /e) (1 + o(1)) bits...

I

... y responder todo en tiempo O(log log n).

I

Obtiene lo mejor de los dos mundos...

I

... pero aun ´ no es demasiado bueno para la Web.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Relaciones Binarias I

´ Con tecnicas muy novedosas de estructuras sucintas para relaciones binarias...

I

... se puede conseguir e log(n2 /e) (1 + o(1)) bits...

I

... y responder todo en tiempo O(log log n).

I

Obtiene lo mejor de los dos mundos...

I

... pero aun ´ no es demasiado bueno para la Web.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Representacion

Algunos ejemplos de bpe’s (crawls reales) Grafo UK EU Arabic Indochina

n 18.5M 860K 23M 7M

e 298M 19M 640M 194M

G. Navarro

Matriz 1.15M 39K 827K 253K

Lista 25.89 20.81 25.51 23.73

2 x Lista 51.78 41.62 51.02 47.46

Comprimiendo Grafos de la Web

Rel. Bin 20.13 15.25 19.66 17.95

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Grafos Planares y Variantes I

Con n nodos, tienen O(n) aristas. ´ Distintas tecnicas para comprimirlos a O(n) bits.

I

Algunas permiten acceso directo.

I

Hay algunos resultados para tipos especiales de grafos.

I

Es improbable que tengan algun ´ impacto en grafos Web.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Grafos Planares y Variantes I

Con n nodos, tienen O(n) aristas. ´ Distintas tecnicas para comprimirlos a O(n) bits.

I

Algunas permiten acceso directo.

I

Hay algunos resultados para tipos especiales de grafos.

I

Es improbable que tengan algun ´ impacto en grafos Web.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Grafos Planares y Variantes I

Con n nodos, tienen O(n) aristas. ´ Distintas tecnicas para comprimirlos a O(n) bits.

I

Algunas permiten acceso directo.

I

Hay algunos resultados para tipos especiales de grafos.

I

Es improbable que tengan algun ´ impacto en grafos Web.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Grafos Planares y Variantes I

Con n nodos, tienen O(n) aristas. ´ Distintas tecnicas para comprimirlos a O(n) bits.

I

Algunas permiten acceso directo.

I

Hay algunos resultados para tipos especiales de grafos.

I

Es improbable que tengan algun ´ impacto en grafos Web.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Grafos Planares y Variantes I

Con n nodos, tienen O(n) aristas. ´ Distintas tecnicas para comprimirlos a O(n) bits.

I

Algunas permiten acceso directo.

I

Hay algunos resultados para tipos especiales de grafos.

I

Es improbable que tengan algun ´ impacto en grafos Web.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Separadores de Grafos I

Mejor exponente: Blandford [PhD Thesis, 2006]

I

Encontrar zonas que se pueden desconectar cortando unas pocas aristas.

I

Renumerar los nodos y comprimirlos separadamente. ´ Pueden obtener 13–16 bits por arista (bpe) y ser mas ´ ´ rapidos que la version descomprimida (por efectos de ´ cache).

I

I

Para vecinos reversos necesitan el grafo traspuesto.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Separadores de Grafos I

Mejor exponente: Blandford [PhD Thesis, 2006]

I

Encontrar zonas que se pueden desconectar cortando unas pocas aristas.

I

Renumerar los nodos y comprimirlos separadamente. ´ Pueden obtener 13–16 bits por arista (bpe) y ser mas ´ ´ rapidos que la version descomprimida (por efectos de ´ cache).

I

I

Para vecinos reversos necesitan el grafo traspuesto.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Separadores de Grafos I

Mejor exponente: Blandford [PhD Thesis, 2006]

I

Encontrar zonas que se pueden desconectar cortando unas pocas aristas.

I

Renumerar los nodos y comprimirlos separadamente. ´ Pueden obtener 13–16 bits por arista (bpe) y ser mas ´ ´ rapidos que la version descomprimida (por efectos de ´ cache).

I

I

Para vecinos reversos necesitan el grafo traspuesto.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Separadores de Grafos I

Mejor exponente: Blandford [PhD Thesis, 2006]

I

Encontrar zonas que se pueden desconectar cortando unas pocas aristas.

I

Renumerar los nodos y comprimirlos separadamente. ´ Pueden obtener 13–16 bits por arista (bpe) y ser mas ´ ´ rapidos que la version descomprimida (por efectos de ´ cache).

I

I

Para vecinos reversos necesitan el grafo traspuesto.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Separadores de Grafos I

Mejor exponente: Blandford [PhD Thesis, 2006]

I

Encontrar zonas que se pueden desconectar cortando unas pocas aristas.

I

Renumerar los nodos y comprimirlos separadamente. ´ Pueden obtener 13–16 bits por arista (bpe) y ser mas ´ ´ rapidos que la version descomprimida (por efectos de ´ cache).

I

I

Para vecinos reversos necesitan el grafo traspuesto.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion Los Grafos Web son Muy Compresibles I

´ sesgada de grados interior/exterior (power Distribucion laws). I

I

Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I

I

Una lista de adyacencia tiene baja entrop´ıa.

´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.

Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I

´ Encontrar una pagina similar y codificar diferencialmente. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Los Grafos Web son Muy Compresibles I

Mejor exponente: Boldi y Vigna [WWW 2006]. I I

I

´ pura 3 bpe para compresion 6 bpe para recuperar cada vecino directo o reverso dentro del microsegundo Esto considera el grafo y su traspuesto

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Los Grafos Web son Muy Compresibles I

Mejor exponente: Boldi y Vigna [WWW 2006]. I I

I

´ pura 3 bpe para compresion 6 bpe para recuperar cada vecino directo o reverso dentro del microsegundo Esto considera el grafo y su traspuesto

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Los Grafos Web son Muy Compresibles I

Mejor exponente: Boldi y Vigna [WWW 2006]. I I

I

´ pura 3 bpe para compresion 6 bpe para recuperar cada vecino directo o reverso dentro del microsegundo Esto considera el grafo y su traspuesto

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

´ de Grafos Compresion

Los Grafos Web son Muy Compresibles I

Mejor exponente: Boldi y Vigna [WWW 2006]. I I

I

´ pura 3 bpe para compresion 6 bpe para recuperar cada vecino directo o reverso dentro del microsegundo Esto considera el grafo y su traspuesto

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Mapa ´ Motivacion ´ Conceptos Basicos Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices Propuesta I: Autoindexamiento Propuesta II: Rank/Select de S´ımbolos Conclusiones

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select Binarios I

Sea B[1, n] un array de bits.

I I

rankb (B, i) = numero de b’s en B[1, i]. ´ ´ del i-esimo ´ selectb (B, i) = posicion b en B.

I

b = 1 por defecto, rank1 (B, i) = i − rank0 (B, i).

I

Ambos se pueden resolver en tiempo constante usando ´ de B. o(|B|) bits ademas

I

E incluso con nH0 (B) + o(n) bits en total. ´ Existen implementaciones practicas.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select de S´ımbolos I

˜ Sea S[1, n] una secuencia sobre el alfabeto Σ de tamano σ.

I I

ranka (S, i) = numero de a’s en S[1, i]. ´ ´ del i-esimo ´ selecta (S, i) = posicion a en S.

I

´ obtener S[i] si la estructura reemplaza S. Ademas,

I

Wavelet trees (generalizados): nH0 (S) + o(n log σ) bits, tiempo O(1 + logloglogσ n ).

I

´ rapido: ´ Mas n log σ + o(n log σ) bits, O(log log σ) rank y acceso, O(1) select. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select de S´ımbolos I

˜ Sea S[1, n] una secuencia sobre el alfabeto Σ de tamano σ.

I I

ranka (S, i) = numero de a’s en S[1, i]. ´ ´ del i-esimo ´ selecta (S, i) = posicion a en S.

I

´ obtener S[i] si la estructura reemplaza S. Ademas,

I

Wavelet trees (generalizados): nH0 (S) + o(n log σ) bits, tiempo O(1 + logloglogσ n ).

I

´ rapido: ´ Mas n log σ + o(n log σ) bits, O(log log σ) rank y acceso, O(1) select. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select de S´ımbolos I

˜ Sea S[1, n] una secuencia sobre el alfabeto Σ de tamano σ.

I I

ranka (S, i) = numero de a’s en S[1, i]. ´ ´ del i-esimo ´ selecta (S, i) = posicion a en S.

I

´ obtener S[i] si la estructura reemplaza S. Ademas,

I

Wavelet trees (generalizados): nH0 (S) + o(n log σ) bits, tiempo O(1 + logloglogσ n ).

I

´ rapido: ´ Mas n log σ + o(n log σ) bits, O(log log σ) rank y acceso, O(1) select. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select de S´ımbolos I

˜ Sea S[1, n] una secuencia sobre el alfabeto Σ de tamano σ.

I I

ranka (S, i) = numero de a’s en S[1, i]. ´ ´ del i-esimo ´ selecta (S, i) = posicion a en S.

I

´ obtener S[i] si la estructura reemplaza S. Ademas,

I

Wavelet trees (generalizados): nH0 (S) + o(n log σ) bits, tiempo O(1 + logloglogσ n ).

I

´ rapido: ´ Mas n log σ + o(n log σ) bits, O(log log σ) rank y acceso, O(1) select. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select de S´ımbolos I

˜ Sea S[1, n] una secuencia sobre el alfabeto Σ de tamano σ.

I I

ranka (S, i) = numero de a’s en S[1, i]. ´ ´ del i-esimo ´ selecta (S, i) = posicion a en S.

I

´ obtener S[i] si la estructura reemplaza S. Ademas,

I

Wavelet trees (generalizados): nH0 (S) + o(n log σ) bits, tiempo O(1 + logloglogσ n ).

I

´ rapido: ´ Mas n log σ + o(n log σ) bits, O(log log σ) rank y acceso, O(1) select. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Rank y Select Rank y Select de S´ımbolos I

˜ Sea S[1, n] una secuencia sobre el alfabeto Σ de tamano σ.

I I

ranka (S, i) = numero de a’s en S[1, i]. ´ ´ del i-esimo ´ selecta (S, i) = posicion a en S.

I

´ obtener S[i] si la estructura reemplaza S. Ademas,

I

Wavelet trees (generalizados): nH0 (S) + o(n log σ) bits, tiempo O(1 + logloglogσ n ).

I

´ rapido: ´ Mas n log σ + o(n log σ) bits, O(log log σ) rank y acceso, O(1) select. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices Comprimidos para Texto Funcionalidad I

I I

Estructuras de datos comprimidas para un texto T = t1 . . . tn . ˜ σ. Sobre un alfabeto Σ de tamano ´ Operaciones basicas soportadas: I I

I

´ Dadas posiciones l, r , mostrar el area de texto tl . . . tr . ´ P = p1 . . . pm , contar las ocurrencias de P Dado un patron en T . Ubicar cada una de esas occ ocurrencias.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices Comprimidos para Texto Funcionalidad I

I I

Estructuras de datos comprimidas para un texto T = t1 . . . tn . ˜ σ. Sobre un alfabeto Σ de tamano ´ Operaciones basicas soportadas: I I

I

´ Dadas posiciones l, r , mostrar el area de texto tl . . . tr . ´ P = p1 . . . pm , contar las ocurrencias de P Dado un patron en T . Ubicar cada una de esas occ ocurrencias.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices Comprimidos para Texto Funcionalidad I

I I

Estructuras de datos comprimidas para un texto T = t1 . . . tn . ˜ σ. Sobre un alfabeto Σ de tamano ´ Operaciones basicas soportadas: I I

I

´ Dadas posiciones l, r , mostrar el area de texto tl . . . tr . ´ P = p1 . . . pm , contar las ocurrencias de P Dado un patron en T . Ubicar cada una de esas occ ocurrencias.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices Comprimidos para Texto Funcionalidad I

I I

Estructuras de datos comprimidas para un texto T = t1 . . . tn . ˜ σ. Sobre un alfabeto Σ de tamano ´ Operaciones basicas soportadas: I I

I

´ Dadas posiciones l, r , mostrar el area de texto tl . . . tr . ´ P = p1 . . . pm , contar las ocurrencias de P Dado un patron en T . Ubicar cada una de esas occ ocurrencias.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices Comprimidos para Texto Funcionalidad I

I I

Estructuras de datos comprimidas para un texto T = t1 . . . tn . ˜ σ. Sobre un alfabeto Σ de tamano ´ Operaciones basicas soportadas: I I

I

´ Dadas posiciones l, r , mostrar el area de texto tl . . . tr . ´ P = p1 . . . pm , contar las ocurrencias de P Dado un patron en T . Ubicar cada una de esas occ ocurrencias.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices Comprimidos para Texto Funcionalidad I

I I

Estructuras de datos comprimidas para un texto T = t1 . . . tn . ˜ σ. Sobre un alfabeto Σ de tamano ´ Operaciones basicas soportadas: I I

I

´ Dadas posiciones l, r , mostrar el area de texto tl . . . tr . ´ P = p1 . . . pm , contar las ocurrencias de P Dado un patron en T . Ubicar cada una de esas occ ocurrencias.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices

I

´ lo indexan. Reemplazan el texto y ademas

I

Es posible hacerlo usando nHk (T ) bits sin el texto.

I

Existen muchos auto´ındices comprimidos para texto.

I

Ej. contar en tiempo O(m log σ), ubicar cada ocurrencia en tiempo O(log n), mostrar en tiempo O(log n + ` log σ).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices

I

´ lo indexan. Reemplazan el texto y ademas

I

Es posible hacerlo usando nHk (T ) bits sin el texto.

I

Existen muchos auto´ındices comprimidos para texto.

I

Ej. contar en tiempo O(m log σ), ubicar cada ocurrencia en tiempo O(log n), mostrar en tiempo O(log n + ` log σ).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices

I

´ lo indexan. Reemplazan el texto y ademas

I

Es posible hacerlo usando nHk (T ) bits sin el texto.

I

Existen muchos auto´ındices comprimidos para texto.

I

Ej. contar en tiempo O(m log σ), ubicar cada ocurrencia en tiempo O(log n), mostrar en tiempo O(log n + ` log σ).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Entrop´ıa ´ Grafos y Compresion Rank, Select, y Auto´ındices

Auto´ındices

I

´ lo indexan. Reemplazan el texto y ademas

I

Es posible hacerlo usando nHk (T ) bits sin el texto.

I

Existen muchos auto´ındices comprimidos para texto.

I

Ej. contar en tiempo O(m log σ), ubicar cada ocurrencia en tiempo O(log n), mostrar en tiempo O(log n + ` log σ).

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Propuesta I: Idea General I

Concatenar las listas de adyacencia en un texto.

I

Construir un auto´ındice comprimido sobre ese texto.

I

Mostrar: vecinos de un nodo

I

Ubicar: vecinos reversos de un nodo

I

Contar: grado interior de un nodo

I

La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Experimental Comparacion

I

Usando el Compressed Suffix Array de Sadakane como auto´ındice.

I

Contra los resultados de Boldi y Vigna.

I

Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.

I

Vecinos: resultados comparables.

I

Reversos: perdemos por 10X

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Experimental Comparacion

I

Usando el Compressed Suffix Array de Sadakane como auto´ındice.

I

Contra los resultados de Boldi y Vigna.

I

Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.

I

Vecinos: resultados comparables.

I

Reversos: perdemos por 10X

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Experimental Comparacion

I

Usando el Compressed Suffix Array de Sadakane como auto´ındice.

I

Contra los resultados de Boldi y Vigna.

I

Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.

I

Vecinos: resultados comparables.

I

Reversos: perdemos por 10X

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Experimental Comparacion

I

Usando el Compressed Suffix Array de Sadakane como auto´ındice.

I

Contra los resultados de Boldi y Vigna.

I

Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.

I

Vecinos: resultados comparables.

I

Reversos: perdemos por 10X

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Experimental Comparacion

I

Usando el Compressed Suffix Array de Sadakane como auto´ındice.

I

Contra los resultados de Boldi y Vigna.

I

Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.

I

Vecinos: resultados comparables.

I

Reversos: perdemos por 10X

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Retrieving neighbors

time per neighbor (ms)

2

ours BV BV (fwd)

1.8 1.6 1.4 1.2 1 0.8 0.6 2

4

6

8

10

12

14

space (bpe) G. Navarro

Comprimiendo Grafos de la Web

16

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Retrieving reverse neighbors

time per neighbor (ms)

30

ours BV

25 20 15 10 5 0 6

7

8

9

10

11

12

13

space (bpe) G. Navarro

Comprimiendo Grafos de la Web

14

15

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos

I

Consideremos de nuevo la secuencia T de listas de adyacencia.

I

Guardamos bitmap H[1, e] marcando los comienzos de listas.

I

Precalculamos rank y select para las secuencias T y H.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos

I

Consideremos de nuevo la secuencia T de listas de adyacencia.

I

Guardamos bitmap H[1, e] marcando los comienzos de listas.

I

Precalculamos rank y select para las secuencias T y H.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos

I

Consideremos de nuevo la secuencia T de listas de adyacencia.

I

Guardamos bitmap H[1, e] marcando los comienzos de listas.

I

Precalculamos rank y select para las secuencias T y H.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

a: d,c,b

b

b: d,c,a a c: d d:

c

e: d,c

T=dcbdcaddc

d e

G. Navarro

H=100100110 Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Usando Rank y Select de S´ımbolos I

´ traducir todas las operaciones: Es facil I I I

I

I

I I I

grado interior (v ): rankv (T , e). grado exterior (v ): select(H, v + 1) − select(H, v ). vecinos(v ): mostrar T [select(H, v ) . . .] hasta que H[i + 1] = 1. vecinos reversos(v ): rank(H, selectv (T , i)), para i’s sucesivos. existe(u, v ): rankv (T , select(H, u + 1) − 1) − rankv (T , select(H, u)) = 1.

Podemos obtener el grafo traspuesto con espacio extra “sublineal” (por ejemplo con tiempo O(log log n)). O lo podemos comprimir a orden cero (Wavelet tree, tiempo O(log n/ log log n)). ´ no es gran cosa (σ es demasiado grande!). La compresion G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos? I

´ Estructuras practicas (Blandford) con 13–16 bpe, sin penalidad aparente.

I

Necesitar´ıan unos 30 bpe para reversos. ´ Estructuras practicas (Boldi & Vigna) con 3–6 bpe, tiempos razonables, incluye reversos. ´ Estructura teorica (relaciones binarias) con n log(n2 /e) bits para todo, tiempos O(log log n), 15–20 bpe como m´ınimo.

I

I

I

I

“Inventamos” otra (rank/select) con e log n bits para todo, tiempos O(log log n), 20–25 bpe como m´ınimo. Para que´ seguir escuchando esta charla?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos? I

´ Estructuras practicas (Blandford) con 13–16 bpe, sin penalidad aparente.

I

Necesitar´ıan unos 30 bpe para reversos. ´ Estructuras practicas (Boldi & Vigna) con 3–6 bpe, tiempos razonables, incluye reversos. ´ Estructura teorica (relaciones binarias) con n log(n2 /e) bits para todo, tiempos O(log log n), 15–20 bpe como m´ınimo.

I

I

I

I

“Inventamos” otra (rank/select) con e log n bits para todo, tiempos O(log log n), 20–25 bpe como m´ınimo. Para que´ seguir escuchando esta charla?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos? I

´ Estructuras practicas (Blandford) con 13–16 bpe, sin penalidad aparente.

I

Necesitar´ıan unos 30 bpe para reversos. ´ Estructuras practicas (Boldi & Vigna) con 3–6 bpe, tiempos razonables, incluye reversos. ´ Estructura teorica (relaciones binarias) con n log(n2 /e) bits para todo, tiempos O(log log n), 15–20 bpe como m´ınimo.

I

I

I

I

“Inventamos” otra (rank/select) con e log n bits para todo, tiempos O(log log n), 20–25 bpe como m´ınimo. Para que´ seguir escuchando esta charla?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos? I

´ Estructuras practicas (Blandford) con 13–16 bpe, sin penalidad aparente.

I

Necesitar´ıan unos 30 bpe para reversos. ´ Estructuras practicas (Boldi & Vigna) con 3–6 bpe, tiempos razonables, incluye reversos. ´ Estructura teorica (relaciones binarias) con n log(n2 /e) bits para todo, tiempos O(log log n), 15–20 bpe como m´ınimo.

I

I

I

I

“Inventamos” otra (rank/select) con e log n bits para todo, tiempos O(log log n), 20–25 bpe como m´ınimo. Para que´ seguir escuchando esta charla?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos? I

´ Estructuras practicas (Blandford) con 13–16 bpe, sin penalidad aparente.

I

Necesitar´ıan unos 30 bpe para reversos. ´ Estructuras practicas (Boldi & Vigna) con 3–6 bpe, tiempos razonables, incluye reversos. ´ Estructura teorica (relaciones binarias) con n log(n2 /e) bits para todo, tiempos O(log log n), 15–20 bpe como m´ınimo.

I

I

I

I

“Inventamos” otra (rank/select) con e log n bits para todo, tiempos O(log log n), 20–25 bpe como m´ınimo. Para que´ seguir escuchando esta charla?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos? I

´ Estructuras practicas (Blandford) con 13–16 bpe, sin penalidad aparente.

I

Necesitar´ıan unos 30 bpe para reversos. ´ Estructuras practicas (Boldi & Vigna) con 3–6 bpe, tiempos razonables, incluye reversos. ´ Estructura teorica (relaciones binarias) con n log(n2 /e) bits para todo, tiempos O(log log n), 15–20 bpe como m´ınimo.

I

I

I

I

“Inventamos” otra (rank/select) con e log n bits para todo, tiempos O(log log n), 20–25 bpe como m´ınimo. Para que´ seguir escuchando esta charla?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Pura Vuelta a Compresion

I I

Hay una forma elegante y efectiva de comprimir T ? ´ repetido en T y Re-Pair: encontrar el par mas reemplazarlo por un nuevo s´ımbolo, hasta que todos los pares sean unicos. ´

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Pura Vuelta a Compresion

I I

Hay una forma elegante y efectiva de comprimir T ? ´ repetido en T y Re-Pair: encontrar el par mas reemplazarlo por un nuevo s´ımbolo, hasta que todos los pares sean unicos. ´

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

aaabcaabaaabcabdabd a a b c b d

a b c a d a

4 5 2 2 2 1

A

ab

a a Ac a Aa a Ac Ad Ad G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair a a Ac a Aa a Ac Ad Ad

aa aA Ac ca Ad cA dA

2 3 2 1 2 1 1

A B

ab aA

a Bc Ba Bc Ad Ad G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

a Bc Ba Bc Ad Ad aB Bc cB Ba cA Ad dA

2 2 1 1 1 2 1

A B C

ab aA Ad

a Bc Ba Bc CC G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

a Bc Ba Bc CC aB Bc cB Ba cC CC

2 2 1 1 1 1

A B C D

ab aA Ad Bc

a DB a DC C G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

a DB a DC C aD DB Ba DC CC

2 1 1 1 1

EBECC

A B C D E

ab aA Ad Bc aD diccionario secuencia comprimida G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

´ Comprime bien, descomprime rapido.

I

Aprovecha la propiedad de copia.

I

Comprime mejor si se codifica T diferencialmente. Mejoramos Re-Pair mismo.

I

I I

Estructura de datos sucinta para el diccionario. ´ Metodo aproximado para secuencias muy grandes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

´ Comprime bien, descomprime rapido.

I

Aprovecha la propiedad de copia.

I

Comprime mejor si se codifica T diferencialmente. Mejoramos Re-Pair mismo.

I

I I

Estructura de datos sucinta para el diccionario. ´ Metodo aproximado para secuencias muy grandes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

´ Comprime bien, descomprime rapido.

I

Aprovecha la propiedad de copia.

I

Comprime mejor si se codifica T diferencialmente. Mejoramos Re-Pair mismo.

I

I I

Estructura de datos sucinta para el diccionario. ´ Metodo aproximado para secuencias muy grandes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

´ Comprime bien, descomprime rapido.

I

Aprovecha la propiedad de copia.

I

Comprime mejor si se codifica T diferencialmente. Mejoramos Re-Pair mismo.

I

I I

Estructura de datos sucinta para el diccionario. ´ Metodo aproximado para secuencias muy grandes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

´ Comprime bien, descomprime rapido.

I

Aprovecha la propiedad de copia.

I

Comprime mejor si se codifica T diferencialmente. Mejoramos Re-Pair mismo.

I

I I

Estructura de datos sucinta para el diccionario. ´ Metodo aproximado para secuencias muy grandes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

´ Comprime bien, descomprime rapido.

I

Aprovecha la propiedad de copia.

I

Comprime mejor si se codifica T diferencialmente. Mejoramos Re-Pair mismo.

I

I I

Estructura de datos sucinta para el diccionario. ´ Metodo aproximado para secuencias muy grandes.

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Mejorando Re-Pair con Estructuras de Datos Sucintas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Mejorando Re-Pair con Estructuras de Datos Sucintas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Mejorando Re-Pair con Estructuras de Datos Sucintas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

El Re-Pair original corre en tiempo lineal, pero necesita 20e bytes!

I

I

Si se usa menos espacio es lent´ısimo. ˜ ´ aproximada para grafos muy Disenamos una version grandes. ´ Los resultados son bastante cercanos al metodo exacto.

I

´ La tecnica se adapta bien a memoria secundaria.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

El Re-Pair original corre en tiempo lineal, pero necesita 20e bytes!

I

I

Si se usa menos espacio es lent´ısimo. ˜ ´ aproximada para grafos muy Disenamos una version grandes. ´ Los resultados son bastante cercanos al metodo exacto.

I

´ La tecnica se adapta bien a memoria secundaria.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

El Re-Pair original corre en tiempo lineal, pero necesita 20e bytes!

I

I

Si se usa menos espacio es lent´ısimo. ˜ ´ aproximada para grafos muy Disenamos una version grandes. ´ Los resultados son bastante cercanos al metodo exacto.

I

´ La tecnica se adapta bien a memoria secundaria.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

El Re-Pair original corre en tiempo lineal, pero necesita 20e bytes!

I

I

Si se usa menos espacio es lent´ısimo. ˜ ´ aproximada para grafos muy Disenamos una version grandes. ´ Los resultados son bastante cercanos al metodo exacto.

I

´ La tecnica se adapta bien a memoria secundaria.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair

I

El Re-Pair original corre en tiempo lineal, pero necesita 20e bytes!

I

I

Si se usa menos espacio es lent´ısimo. ˜ ´ aproximada para grafos muy Disenamos una version grandes. ´ Los resultados son bastante cercanos al metodo exacto.

I

´ La tecnica se adapta bien a memoria secundaria.

I

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair I I I I I

El espacio que sobre en memoria principal se usa para una tabla hash. Se recorre la secuencia y se almacenan los pares y frecuencias. Cuando la tabla se llena se dejan de insertar pares nuevos. ´ frecuentes Al final se recorre la tabla y se eligen los K mas ´ vez. para reemplazar de una sola ´ tenemos mas ´ espacio para la tabla A la siguiente iteracion

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair I I I I I

El espacio que sobre en memoria principal se usa para una tabla hash. Se recorre la secuencia y se almacenan los pares y frecuencias. Cuando la tabla se llena se dejan de insertar pares nuevos. ´ frecuentes Al final se recorre la tabla y se eligen los K mas ´ vez. para reemplazar de una sola ´ tenemos mas ´ espacio para la tabla A la siguiente iteracion

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair I I I I I

El espacio que sobre en memoria principal se usa para una tabla hash. Se recorre la secuencia y se almacenan los pares y frecuencias. Cuando la tabla se llena se dejan de insertar pares nuevos. ´ frecuentes Al final se recorre la tabla y se eligen los K mas ´ vez. para reemplazar de una sola ´ tenemos mas ´ espacio para la tabla A la siguiente iteracion

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair I I I I I

El espacio que sobre en memoria principal se usa para una tabla hash. Se recorre la secuencia y se almacenan los pares y frecuencias. Cuando la tabla se llena se dejan de insertar pares nuevos. ´ frecuentes Al final se recorre la tabla y se eligen los K mas ´ vez. para reemplazar de una sola ´ tenemos mas ´ espacio para la tabla A la siguiente iteracion

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Re-Pair I I I I I

El espacio que sobre en memoria principal se usa para una tabla hash. Se recorre la secuencia y se almacenan los pares y frecuencias. Cuando la tabla se llena se dejan de insertar pares nuevos. ´ frecuentes Al final se recorre la tabla y se eligen los K mas ´ vez. para reemplazar de una sola ´ tenemos mas ´ espacio para la tabla A la siguiente iteracion

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Resultados Experimentales UK: 18.5M nodos, 298M aristas UK Re-Pair Re-Pair (diffs) Plain Compact

0.0005

0.0004

time (mseg/edge)

time (mseg/edge)

0.0005

0.0003 0.0002 0.0001 0

UK

Re-Pair Re-Pair (diffs) BV BV-Memory

0.0004 0.0003 0.0002 0.0001

0

2

4

6 8 space (bits/edge)

10

12

G. Navarro

0

0

5

10

15 20 25 space (bits/edge)

Comprimiendo Grafos de la Web

30

35

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Resultados Experimentales EU: 860K nodos, 19M aristas EU Re-Pair Re-Pair (diffs) Plain Compact

0.0005

0.0004

time (mseg/edge)

time (mseg/edge)

0.0005

0.0003 0.0002 0.0001 0

EU

Re-Pair Re-Pair (diffs) BV BV-Memory

0.0004 0.0003 0.0002 0.0001

0

2

4

6 8 10 space (bits/edge)

12

14

G. Navarro

0

0

5

10

15 20 25 space (bits/edge)

Comprimiendo Grafos de la Web

30

35

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Resultados Experimentales Arabic: 23M nodos, 640M aristas Arabic Re-Pair Re-Pair (diffs) Plain Compact

0.0005

0.0004

time (mseg/edge)

time (mseg/edge)

0.0005

0.0003 0.0002 0.0001 0

Arabic

Re-Pair Re-Pair (diffs) BV BV-Memory

0.0004 0.0003 0.0002 0.0001

0

2

4 6 space (bits/edge)

8

10

G. Navarro

0

0

5

10

15 20 25 space (bits/edge)

Comprimiendo Grafos de la Web

30

35

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Resultados Experimentales Indochina: 7M nodos, 194M aristas Indochina Re-Pair Re-Pair (diffs) Plain Compact

0.0005

0.0004

time (mseg/edge)

time (mseg/edge)

0.0005

0.0003 0.0002 0.0001 0

Indochina

Re-Pair Re-Pair (diffs) BV BV-Memory

0.0004 0.0003 0.0002 0.0001

0

2

4 6 space (bits/edge)

8

10

G. Navarro

0

0

5

10

15 20 25 space (bits/edge)

Comprimiendo Grafos de la Web

30

35

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos?

I

Conseguimos 5–7 bpe y mejor compromiso tiempo/espacio que Boldi & Vigna.

I

Podr´ıamos tener operaciones reversas eficientes con 10–14 bpe.

I

Esto es la mitad del espacio de Blandford.

I

Pero... no podr´ıamos ahora tener rank/select sobre Re-Pair?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos?

I

Conseguimos 5–7 bpe y mejor compromiso tiempo/espacio que Boldi & Vigna.

I

Podr´ıamos tener operaciones reversas eficientes con 10–14 bpe.

I

Esto es la mitad del espacio de Blandford.

I

Pero... no podr´ıamos ahora tener rank/select sobre Re-Pair?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos?

I

Conseguimos 5–7 bpe y mejor compromiso tiempo/espacio que Boldi & Vigna.

I

Podr´ıamos tener operaciones reversas eficientes con 10–14 bpe.

I

Esto es la mitad del espacio de Blandford.

I

Pero... no podr´ıamos ahora tener rank/select sobre Re-Pair?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

´ Donde Estamos?

I

Conseguimos 5–7 bpe y mejor compromiso tiempo/espacio que Boldi & Vigna.

I

Podr´ıamos tener operaciones reversas eficientes con 10–14 bpe.

I

Esto es la mitad del espacio de Blandford.

I

Pero... no podr´ıamos ahora tener rank/select sobre Re-Pair?

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Desaf´ıo Final I

Es posible combinar Re-Pair con Rank/Select?

I

Problema: Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario.

I

I

Vecinos y vecinos reversos: ok (una unidad de trabajo por vecino reportado).

I

Grado exterior/interior eficientes con 1 bpe extra cada uno.

I

(pero son bitmaps compresibles a 0.17–0.25 bpe cada uno).

I

Existe: Muy caro. G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Conclusiones

I I

I

I

Enfoque algor´ıtmico a problemas reales de grafos. ´ Resultados practicos relevantes, algunos desaf´ıos abiertos. ´ ´ Estructuras de datos compactas: area de investigacion reciente y promisoria. ´ basica: ´ ´ basica, ´ Investigacion cuanto mas I I

´ aplicaciones tiene, pero mas ´ dif´ıcil predecirlas. es mas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Conclusiones

I I

I

I

Enfoque algor´ıtmico a problemas reales de grafos. ´ Resultados practicos relevantes, algunos desaf´ıos abiertos. ´ ´ Estructuras de datos compactas: area de investigacion reciente y promisoria. ´ basica: ´ ´ basica, ´ Investigacion cuanto mas I I

´ aplicaciones tiene, pero mas ´ dif´ıcil predecirlas. es mas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Conclusiones

I I

I

I

Enfoque algor´ıtmico a problemas reales de grafos. ´ Resultados practicos relevantes, algunos desaf´ıos abiertos. ´ ´ Estructuras de datos compactas: area de investigacion reciente y promisoria. ´ basica: ´ ´ basica, ´ Investigacion cuanto mas I I

´ aplicaciones tiene, pero mas ´ dif´ıcil predecirlas. es mas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Conclusiones

I I

I

I

Enfoque algor´ıtmico a problemas reales de grafos. ´ Resultados practicos relevantes, algunos desaf´ıos abiertos. ´ ´ Estructuras de datos compactas: area de investigacion reciente y promisoria. ´ basica: ´ ´ basica, ´ Investigacion cuanto mas I I

´ aplicaciones tiene, pero mas ´ dif´ıcil predecirlas. es mas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Conclusiones

I I

I

I

Enfoque algor´ıtmico a problemas reales de grafos. ´ Resultados practicos relevantes, algunos desaf´ıos abiertos. ´ ´ Estructuras de datos compactas: area de investigacion reciente y promisoria. ´ basica: ´ ´ basica, ´ Investigacion cuanto mas I I

´ aplicaciones tiene, pero mas ´ dif´ıcil predecirlas. es mas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

Conclusiones

I I

I

I

Enfoque algor´ıtmico a problemas reales de grafos. ´ Resultados practicos relevantes, algunos desaf´ıos abiertos. ´ ´ Estructuras de datos compactas: area de investigacion reciente y promisoria. ´ basica: ´ ´ basica, ´ Investigacion cuanto mas I I

´ aplicaciones tiene, pero mas ´ dif´ıcil predecirlas. es mas

G. Navarro

Comprimiendo Grafos de la Web

´ Motivacion ´ Conceptos Basicos Propuesta I Propuesta II Conclusiones

e 2

d t 1 n h

1: t h e 2: e n d G. Navarro

T=theend H=100100

Comprimiendo Grafos de la Web