Parallel lightweight wavelet tree, suffix array and FM-index construction

DOI10.1016/J.JDA.2017.04.001MaRDI QIDQ2397146zbMATH OpenOpenAlexFDO

Authors Julian Labeit, Julian Shun, Guy E. Blelloch

Publication date 29 May 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2017.04.001

zbMATH Keywords

FM indexinduced sortinglightweightparallelsuffix arraywavelet tree

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Practical Wavelet Tree Construction
• Improved parallel construction of wavelet trees and rank/select structures
• Fast wavelet tree construction in practice
• Lightweight distributed suffix array construction

Cites work

• Combinatorial Pattern Matching
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• Fast construction of wavelet trees
• Faster suffix sorting
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• On the maximum length of Huffman codes
• Parallel algorithms for Burrows-Wheeler compression and decompression
• Parallel External Memory Suffix Sorting
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Scalable Parallel Suffix Array Construction
• Suffix Arrays: A New Method for On-Line String Searches
• Wavelet trees for all
• Wavelet trees meet suffix trees

Cited in

(10)

• Parallel computation of the Burrows Wheeler transform in compact space
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Parallel construction of succinct trees
• Practical Wavelet Tree Construction
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Space-efficient parallel construction of succinct representations of suffix tree topologies
• Parallel external memory wavelet tree and wavelet matrix construction
• Fast, parallel, and cache-friendly suffix array construction
• Generic non-recursive suffix array construction
• Improved parallel construction of wavelet trees and rank/select structures

Describes a project that uses

Uses Software

• CMU Benchmarks

This page was built for publication: Parallel lightweight wavelet tree, suffix array and FM-index construction

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