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.

Implementation

All implementations are available at https://github.com/kurpicz/pwm.

Posts Related to Wavelet Tree Construction

Article Available in ACM Journal of Experimental Algorithmics
2021-07-12

Practical Wavelet Tree Construction
Paper Accepted at ALENEX 2020
2020-01-06

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

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

On Parallel Wavelet Tree Construction
Presentation at ALENEX 2018
2018-01-08

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

Simple, Fast and Lightweight Parallel Wavelet Tree Construction