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

Parallel External Memory Wavelet Tree and Wavelet Matrix Construction

DOI pdf code

Abstract

We present the first parallel external memory wavelet tree and matrix construction algorithm. The algorithm’s throughput is nearly the same as the hard disk drives’ throughput, using six cores. We also present the fastest (parallel) semi-external construction algorithms for both wavelet trees and matrices.

BibTeX

@inproceedings{Kurpicz2019SPIRE,
  author    = {Jonas Ellert and Florian Kurpicz},
  title     = {Parallel External Memory Wavelet Tree and Wavelet Matrix Construction},
  booktitle = {SPIRE},
  series    = {Lecture Notes in Computer Science},
  volume    = {11811},
  pages     = {392–406},
  publisher = {Springer},
  doi       = {10.1007/978-3-030-32686-9 28},
  year      = {2019}
}

PDF