  The wavelet tree has become a very useful data structure to efficiently
represent and query large volumes of data in many different domains, from
bioinformatics to geographic information systems. One problem with wavelet
trees is their construction time. In this paper, we introduce two algorithms
that reduce the time complexity of a wavelet tree's construction by taking
advantage of nowadays ubiquitous multicore machines.
  Our first algorithm constructs all the levels of the wavelet in parallel in
$O(n)$ time and $O(n\lg\sigma + \sigma\lg n)$ bits of working space, where $n$
is the size of the input sequence and $\sigma$ is the size of the alphabet. Our
second algorithm constructs the wavelet tree in a domain-decomposition fashion,
using our first algorithm in each segment, reaching $O(\lg n)$ time and
$O(n\lg\sigma + p\sigma\lg n/\lg\sigma)$ bits of extra space, where $p$ is the
number of available cores. Both algorithms are practical and report good
speedup for large real datasets.
