Practical Wavelet Tree Construction

DOI10.1145/3457197MaRDI QIDQ5102058zbMATH OpenOpenAlexFDO

Authors Patrick Dinklage, Jonas Ellert, Johannes Fischer, Florian Kurpicz, Marvin Löbel

Publication date 6 September 2022

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3457197

zbMATH Keywords

data structuresdistributed memoryexternal memoryshared memorytext indexing

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10)

Recommendations

• On wavelet tree construction
• Fast wavelet tree construction in practice
• Fast construction of wavelet trees
• Tree wavelet approximations with applications
• The myriad virtues of wavelet trees
• The Myriad Virtues of Wavelet Trees
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Online construction of wavelet trees

Cites work

• A Method for the Construction of Minimum-Redundancy Codes
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory
• Fast construction of wavelet trees
• Fast wavelet tree construction in practice
• Faster average case low memory semi-external construction of the Burrows-Wheeler transform
• Fixed block compression boosting in FM-indexes: theory and practice
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1033260 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Improved parallel construction of wavelet trees and rank/select structures
• Indexing compressed text
• Large alphabets and incompressibility
• On wavelet tree construction
• Online construction of wavelet trees
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Permuted Longest-Common-Prefix Array
• Position-restricted substring searching over small alphabets
• Rank and select revisited and extended
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Suffix Arrays: A New Method for On-Line String Searches
• The myriad virtues of wavelet trees
• Wavelet trees for all
• Wavelet trees meet suffix trees

Cited in

(9)

• The myriad virtues of wavelet trees
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Fast construction of wavelet trees
• Online construction of wavelet trees
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Wavelet trees meet suffix trees
• Fast wavelet tree construction in practice
• Parallel external memory wavelet tree and wavelet matrix construction
• Improved parallel construction of wavelet trees and rank/select structures

This page was built for publication: Practical Wavelet Tree Construction

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