We present parallel lightweight algorithms to construct wavelet trees, rank and select
structures, and suffix arrays in a shared-memory setting. The work and depth of our first …

We present new sequential and parallel algorithms for wavelet tree construction based on a
new bottom-up technique. This technique makes use of the structure of the wavelet trees …

Existing parallel algorithms for wavelet tree construction have a work complexity of O (n log⁡
σ). This paper presents parallel algorithms for the problem with improved work complexity …

Given a text, rank and select queries return the number of occurrences of a character up to a
position (rank) or the position of a character with a given rank (select). These queries have …

The block tree [Belazzougui et al. J. Comput. Syst. Sci.'21] is a compressed text index that
can answer access (extract a character at a position), rank (number of occurrences of a …

The wavelet tree is a compact data structure that supports various types of operations on a
sequence of n integers in 0, σ). Although Munro et al.(SPIRE 2014 and Theoretical …

The wavelet tree (Grossi et al.[SODA, 2003]) and wavelet matrix (Claude et al.[Inf. Syst., 47:
15–32, 2015]) are compact indices for texts over an alphabet [0, σ) that support rank, select …

Indexing is one of the key components of any search tool to be optimized for searching
documents. Among the existing indexing techniques, inverted indexing is one of the best …

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 …

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 …