A wavelet trees is a compact data structure that can be used to answer rank and select queries on texts of arbitrary size (among others). We are interested in the efficient construction of wavelet trees (and wavelet matrices) in different models of computation.
We have implemented sequential, shared memory parallel, and parallel (semi-) external memory construction algorithms for wavelet trees. Additionally, we have sequential and shared memory parallel construction algorithms for Huffman-shaped wavelet trees. Since our algorithms are base on our novel approach, the bottom-up construction, we can easily extend the algorithms to compute the wavelet matrix instead. The wavelet matrix is a different representation of the wavelet tree that can answer queries faster in practice.
All implementations are available at https://github.com/kurpicz/pwm.