Please use this identifier to cite or link to this item:
Title: Construcción paralela de estructuras de datos sucintas
Authors: Ferres, Leo , supervisor de grado
Fuentes Sepúlveda, José Sebastian
Keywords: Ciencias de la Computación
Estructuras de Datos (Ciencia de la Computacion)
Algoritmos Paralelos
Issue Date: 2016
Publisher: Universidad de Concepción . Facultad de Ingeniería
Abstract: 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.
Description: This work was supported the doctoral scholarship of CONICYT (21120974) and in part by the Emerging Leaders in the Americas scholarship programme
Appears in Collections:Ingeniería - Tesis Doctorado

Files in This Item:
File Description SizeFormat 
Tesis_Construccion_paralela_de_Estructuras.Image.Marked.pdf2,82 MBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.