Florian Kurpicz
Paper Accepted at SPIRE 2019

Parallel External Memory Wavelet Tree and Wavelet Matrix Construction

Our paper "Parallel External Memory Wavelet Tree and Wavelet Matrix Construction" has been accepted at SPIRE 2019. We present different (semi-)external memory wavelet tree and wavelet matrix construction algorithms. The paper is available here (DIO).

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.