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

DOI10.1016/j.jda.2017.04.001zbMath1407.68111OpenAlexW2604604482MaRDI QIDQ2397146

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

parallelsuffix arraywavelet treelightweightFM indexinduced sorting

Mathematics Subject Classification ID

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

Related Items (7)

Parallel lightweight wavelet tree, suffix array and FM-index construction ⋮ Parallel construction of succinct trees ⋮ Practical Wavelet Tree Construction ⋮ Fast and compact planar embeddings ⋮ Parallel computation of the Burrows Wheeler transform in compact space ⋮ Improved parallel construction of wavelet trees and rank/select structures ⋮ Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies

Uses Software

• CMU Benchmarks

Cites Work

• Fast construction of wavelet trees
• On the maximum length of Huffman codes
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Parallel algorithms for Burrows-Wheeler compression and decompression
• Wavelet trees for all
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• Faster suffix sorting
• Parallel External Memory Suffix Sorting
• Suffix Arrays: A New Method for On-Line String Searches
• Scalable Parallel Suffix Array Construction
• Wavelet Trees Meet Suffix Trees
• Combinatorial Pattern Matching
• Unnamed Item
• Unnamed Item
• Unnamed Item

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