Doctora en Ciencias, Mención Computación / Con la popularidad de la Web y, mas recientemente, el amplio uso de las redes sociales, la
necesidad de procesar y encontrar información en grafos muy grandes impone varios desafíos:
Cómo procesar grafos muy grandes e cientemente, dado que probablemente son muy grandes
para la memoria disponible, o incluso si la memoria es su ciente, realizar un paso sobre el
grafo es todavía caro computacionalmente? Cómo almacenar esos grafos e cientemente, para
ser archivados, o para ejecutar algoritmos de grafos? Cómo descubrir información relevante
tal como componentes densos, comunidades, u otras estructuras?
Se han propuesto tres enfoques para manejar grafos grandes. El primero es usar formatos
de grafos comprimidos que permiten consultas de navegación básicas directamentee sobre la
estructura comprimida, sin la necesidad de descompresión. Esto permite simular cualquier
algoritmo de grafo en memoria principal usando mucho menos espacio que la representación
plana. Una segunda línea de investigación se focaliza en usar modelos de stream o semi-
stream de datos de manera de procesar secuencialmente, idealmente en un paso sobre el
disco, usando una cantidad limitada de memoria principal.
La tercera línea es el uso de
sistemas distribuidos y paralelos donde la memoria es agregada sobre múltiples unidades de
procesamiento para procesar el grafo en paralelo.
En esta tesis presentamos varios enfoques para manejar grafos grandes (con arcos sin
etiquetas) considerando los tres enfoques.
Primero, buscamos por patrones que aparecen
en grafos de la Web y redes sociales los que podemos representar en forma compacta, en
particular mostramos como generalizar algoritmos para encontrar cliques o bicliques para
encontrar sub-estructuras densas que comprimen ambas. Segundo, basado en estos subgrafos
densos, proponemos esquemas comprimidos que soportan consultas de vecinos directos y
reversos, así como otras consultas mas complejas sobre subgrafos densos.
Algunas de las
contribuciones combinan técnicas del estado del arte mientras otras incluyen representaciones
comprimidas novedosas basadas en estructuras de datos compactas.
Encontrar subgrafos
densos es una tarea que consume tiempo y espacio, así que proporcionamos algoritmos de
streaming and algoritmos de memoria externa para descubrir subgrafos densos, asi como
también algoritmos distribuidos para construir las estructuras básicas que usamos para las
representaciones comprimidas.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/131839 |
| Date | January 2014 |
| Creators | Hernández Rivas, Cecilia Paola |
| Contributors | Navarro Badino, Gonzalo, Marín Caihuán, Mauricio, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ciencias de la Computación, Bustos Cárdenas, Benjamín, Pérez Rojas, Jorge, Vigna, Sebastiano |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0016 seconds