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.