Show simple item record

Professor Guidedc.contributor.advisorNavarro Badino, Gonzalo
Authordc.contributor.authorClaude Faust, Francisco José 
Staff editordc.contributor.editorFacultad de Ciencias Físicas y Matemáticas
Staff editordc.contributor.editorDepartamento de Ciencias de la Computación
Associate professordc.contributor.otherBustos Cárdenas, Benjamín
Associate professordc.contributor.otherMarín Caihuan, Mauricio
Associate professordc.contributor.otherBarbay, Jeremy
Admission datedc.date.accessioned2012-12-04T19:12:51Z
Available datedc.date.available2012-12-04T19:12:51Z
Publication datedc.date.issued2008
Identifierdc.identifier.urihttp://repositorio.uchile.cl/handle/2250/111736
General notedc.descriptionMagíster en Ciencias, Mención Computación
Abstractdc.description.abstractLa estructura de la Web se puede modelar como un grafo, donde las páginas son los nodos y los hipervínculos las aristas. Estos grafos Web son ampliamente utilizados para diversas tareas de análisis de la Web, tales como el cálculo de Page-Rank o la detección de spam en la Web, entre otras. Una de las limitantes que se presentan al trabajar con estos grafos es su tamaño, por ejemplo, el 2005 se calculó que la Web pública y estática tenía 11.5 mil millones de nodos, y unas 15 aristas por nodo, lo que requiere más de 600 GB para su representación plana. De aquí surge la motivación de este trabajo, que consiste en la creación de estructuras de datos comprimidas para representar grafos de la Web. Una estructura comprimida busca almacenar la mayor cantidad de datos en el menor espacio posible, ya sea en memoria principal o en disco, soportando las consultas de interés sin la necesidad de descomprimir la estructura en su totalidad. La principal ventaja de estas estructuras es que se puede evitar mantener la información en disco o se disminuye la cantidad de transferencias necesarias. Esto es de vital importancia dado que el disco puede llegar a ser un millón de veces más lento que la memoria principal. Entre los resultados más importantes de este trabajo se presenta una estructura comprimida para grafos de la Web que mejora el estado del arte, ofreciendo el mejor compromiso espacio-tiempo conocido para recuperar listas de adyacencia. Además se muestra cómo extender esta estructura para soportar consultas más complejas, como vecinos reversos, manteniendo los requerimientos de espacio. Como productos agregados se incluyen resultados experimentales y propuestas para el problema de Rank y Select sobre secuencias generales, incluyendo estructuras no implementadas antes. Los resultados derivan en mejoras inmediatas para índices comprimidos para texto, en los cuales se reduce el espacio utilizado por los mejores índices existentes, a veces incluso sin penalización en el tiempo de búsqueda. Además se presenta un algoritmo aproximado para comprimir utilizando el método Re-Pair cuando la memoria principal es limitada. También se obtienen resultados en estructuras comprimidas para relaciones binarias, presentándose una nueva propuesta que, además de utilizar espacio proporcional a la entropía de la relación binaria, permite dinamizar la estructura, vale decir, aceptar inserciones y borrados de pares en la relación.es_CL
Lenguagedc.language.isoeses_CL
Publisherdc.publisherUniversidad de Chilees_CL
Keywordsdc.subjectEstructuras de datos (Ciencia de la computación)es_CL
Keywordsdc.subjectTeoría de grafoses_CL
Keywordsdc.subjectCompresión de datos (Ciencia de la computación)es_CL
Keywordsdc.subjectRelaciones binariases_CL
Títulodc.titleEstructuras comprimidas para grafos de la Webes_CL
Document typedc.typeTesises_CL


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record