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.

Paper Accepted at ALENEX 2020

Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory2020-01-06

Paper Accepted at SPIRE 2019

Parallel External Memory Wavelet Tree and Wavelet Matrix Construction2019-10-09

Talk at 75. Workshop über Algorithmen und Komplexität

On Parallel Wavelet Tree Construction 2018-04-10

Presentation at ALENEX 2018

Simple, Fast and Lightweight Parallel Wavelet Tree Construction 2018-01-08

Talk at Workshop on Memory-Efficient Algorithms

Simple, Fast and Lightweight Parallel Wavelet Tree Construction 2017-11-15