Skip to main content Link Search Menu Expand Document (external link)
Florian Kurpicz

Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory

DOI pdf code

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.

BibTeX 

@inproceedings{Kurpicz2020ALENEX,
  author    = {Patrick Dinklage and Johannes Fischer and Florian Kurpicz},
  title     = {Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory},
  booktitle = {ALENEX},
  pages     = {214–228},
  publisher = {SIAM},
  doi       = {10.1137/1.9781611976007.17},
  year      = {2020}
}

PDF