dc.creator | Fuentes Sepúlveda, José | |
dc.creator | Navarro, Gonzalo | |
dc.creator | Nekrich, Yakov | |
dc.date.accessioned | 2020-05-18T22:27:38Z | |
dc.date.available | 2020-05-18T22:27:38Z | |
dc.date.created | 2020-05-18T22:27:38Z | |
dc.date.issued | 2020 | |
dc.identifier | Theoretical Computer Science 812(2020)123–136 | |
dc.identifier | 10.1016/j.tcs.2019.09.030 | |
dc.identifier | https://repositorio.uchile.cl/handle/2250/174815 | |
dc.description.abstract | The Burrows-Wheeler Transform (BWT) has become since its introduction a key tool for representing large text collections in compressed space while supporting indexed searching: on a text of length n over an alphabet of size sigma, it requires O (n lg sigma) bits of space, instead of the O (n lg n) bits required by classical indexes. A challenge for its adoption is to build it within O (n lg sigma) bits as well. There are some sequential algorithms building it within this space, but no such a parallel algorithm. In this paper we present a PRAM CREW algorithm to build the BWT using O (n root lgn) work, O(lg(3)n/lg sigma) depth, and O (n lg sigma) bits. | |
dc.language | en | |
dc.publisher | Elsevier | |
dc.rights | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | |
dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | |
dc.source | Theoretical Computer Science | |
dc.subject | Burrows-Wheeler Transform | |
dc.subject | Suffix arrays | |
dc.subject | Parallel construction | |
dc.subject | Compact data structures | |
dc.title | Parallel computation of the Burrows Wheeler Transform in compact space | |
dc.type | Artículo de revista | |