###
Parallel Computation of the Burrows Wheeler Transform in Compact Space

####
José Fuentes-Sepúlveda, Gonzalo Navarro, and Yakov Nekrich

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 *s*, it requires *O(n lg s)* 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 s)* 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 sqrt(lg n))* work, *O(lg^3 n / lg s)* depth,
and *O(n lg s)* bits.