Florian Kurpicz

Wavelet Trees

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.

Posts Related to Wavelet Tree Construction

Paper Accepted at ALENEX 2020

Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory
Paper Accepted at SPIRE 2019

Parallel External Memory Wavelet Tree and Wavelet Matrix Construction
Talk at 75. Workshop über Algorithmen und Komplexität

On Parallel Wavelet Tree Construction
Presentation at ALENEX 2018

Simple, Fast and Lightweight Parallel Wavelet Tree Construction
Talk at Workshop on Memory-Efficient Algorithms

Simple, Fast and Lightweight Parallel Wavelet Tree Construction