Parallel computation of the Burrows Wheeler Transform in compact space
Artículo

Open/ Download
Access note
Acceso Abierto
Publication date
2020Metadata
Show full item record
Cómo citar
Fuentes Sepúlveda, José
Cómo citar
Parallel computation of the Burrows Wheeler Transform in compact space
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.
Patrocinador
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
CONICYT FONDECYT
3170534
Basal Funds, CONICYT, Chile
FB0001
Indexation
Artículo de publicación ISI Artículo de publicación SCOPUS
Quote Item
Theoretical Computer Science 812(2020)123–136
Collections
The following license files are associated with this item: