Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.udec.cl/jspui/handle/11594/2094
Título : Construcción paralela de estructuras de datos sucintas
Autor : Ferres, Leo; supervisor de grado
Fuentes Sepúlveda, José Sebastian
Palabras clave : Ciencias de la Computación;Estructuras de Datos (Ciencia de la Computacion);Algoritmos Paralelos
Fecha de publicación : 2016
Editorial : Universidad de Concepción.
Resumen : As of 31st December, 2013, the total number of accessible Web pages amounted to 14.3 trillions and the total size of accessible data was calculated to be approximately 672EB (exabytes), not including very large private databases. It is safe to assume that the same trend will persist in the coming years: the size of the data available on the Internet will keep growing exponentially. Thus, it now has become imperative to nd ways to solve the problem of reading, processing and storing those enormous amounts of data. To date, two main approaches have been proposed to solve the problem: the traditional increase in the machines’ processing power (led by clock speed up until the beginning of the millenium, and superseded by adding processors as of 2004), and the more modern, algorithm-based minimization of the space required to store data. In this thesis, we will combine both approaches, constructing succinct data structures on multicore architectures. In particular, three succinct data structures will be addressed: wavelet trees, succinct ordinal trees and triangulated plane graphs. For wavelet trees, we present two construction algorithms that achieves O(n) and O(lg n) time using O(n lg + lg n) and O(n lg +p lg n= lg ) bits of space, respectively, where n is the size of the input, is the alphabet size and p is the number of available threads. For succinct trees, we introduce a practical construction algorithm that takes O(lg n) time and O(n lg n) bits of space for a tree on n nodes. For triangulated plane graphs, we present a parallel algorithm that computes the succinct representation of a triangulated plane graph, with n vertices and a canonical ordering, in O(lg n) time and O(n lg n) bits of space.
Descripción : This work was supported the doctoral scholarship of CONICYT (21120974) and in part by the Emerging Leaders in the Americas scholarship programme
URI : http://repositorio.udec.cl/jspui/handle/11594/2094
metadata.dc.identifier.other: 227948
Aparece en las colecciones: Ingeniería - Tesis Doctorado

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Tesis_Construccion_paralela_de_Estructuras.Image.Marked.pdf2,82 MBAdobe PDFVista previa
Visualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons