Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.udec.cl/jspui/handle/11594/2094
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.contributor.advisorFerres, Leo; supervisor de gradoes
dc.contributor.authorFuentes Sepúlveda, José Sebastianes
dc.date.accessioned2017-04-24T13:23:13Z
dc.date.accessioned2019-12-18T15:54:31Z-
dc.date.available2017-04-24T13:23:13Z
dc.date.available2019-12-18T15:54:31Z-
dc.date.issued2016
dc.identifier.other227948
dc.identifier.urihttp://repositorio.udec.cl/jspui/handle/11594/2094-
dc.descriptionThis work was supported the doctoral scholarship of CONICYT (21120974) and in part by the Emerging Leaders in the Americas scholarship programmees
dc.description.abstractAs 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.es
dc.language.isospaes
dc.publisherUniversidad de Concepción.es
dc.rightsCreative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional)-
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es-
dc.subjectCiencias de la Computaciónes
dc.subjectEstructuras de Datos (Ciencia de la Computacion)es
dc.subjectAlgoritmos Paraleloses
dc.titleConstrucción paralela de estructuras de datos sucintases
dc.typeTesises
dc.description.facultadIngeniería Tesis - Doctoradoes
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