Improved parallel construction of wavelet trees and rank/select structures

DOI10.1016/J.IC.2020.104516MaRDI QIDQ776833zbMATH OpenOpenAlexWikidataFDO

Authors Julian Shun

Publication date 13 July 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.03524

zbMATH Keywords

parallel algorithmssuccinct data structuresrank and selectwavelet treewavelet matrix

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Abstract: Existing parallel algorithms for wavelet tree construction have a work complexity of $O(nlogsigma)$. This paper presents parallel algorithms for the problem with improved work complexity. Our first algorithm is based on parallel integer sorting and has either $O(nloglognlceillogsigma/sqrtlognloglognceil)$ work and polylogarithmic depth, or $O(nlceillogsigma/sqrtlognceil)$ work and sub-linear depth. We also describe another algorithm that has $O(nlceillogsigma/sqrtlognceil)$ work and $O(sigma+logn)$ depth. We then show how to use similar ideas to construct variants of wavelet trees (arbitrary-shaped binary trees and multiary trees) as well as wavelet matrices in parallel with lower work complexity than prior algorithms. Finally, we show that the rank and select structures on binary sequences and multiary sequences, which are stored on wavelet tree nodes, can be constructed in parallel with improved work bounds, matching those of the best existing sequential algorithms for constructing rank and select structures.

Recommendations

• Practical Wavelet Tree Construction
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Wavelet trees meet suffix trees
• On wavelet tree construction

Cites work

• scientific article; zbMATH DE number 4215352 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Compressed representations of sequences and full-text indexes
• Fast wavelet tree construction in practice
• Improved deterministic parallel integer sorting
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Parallel algorithms for Burrows-Wheeler compression and decompression
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Rank and select revisited and extended
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• The Parallel Evaluation of General Arithmetic Expressions
• Wavelet trees for all
• Wavelet trees meet suffix trees
• When indexing equals compression

Cited in

(4)

• Parallel external memory wavelet tree and wavelet matrix construction
• Practical Wavelet Tree Construction
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Parallel lightweight wavelet tree, suffix array and FM-index construction

This page was built for publication: Improved parallel construction of wavelet trees and rank/select structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776833)