Florian Kurpicz
Paper Accepted at ALENEX 2020

Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory

Our paper "Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory" was accepted to be presented at ALENEX 2020. Here, we present distributed wavelet tree and wavelet matrix algorithms that are loosely based on our shared memory wavelet tree and matrix construction algorithms, which you can find here. The paper can be found here (DOI)..

Abstract

The wavelet tree (Grossi et al. [SODA, 2003]) is a compact index for texts that provides rank, select, and access operations. This leads to many applications in text indexing, computational geometry, and compression. We present the first distributed memory wavelet tree construction algorithms, which allow us to process inputs that are orders of magnitude larger than what current shared memory construction algorithms can work with. In addition, our algorithms can easily be adapted to compute the wavelet matrix (Claude et al. [Inf. Syst., 47:15–32,2015]), an alternative representation of the wavelet tree. In practice, one of our distributed memory wavelet matrix construction algorithms is the first parallel algorithm that can compute the wavelet matrix for alphabets of arbitrary size.