Space-efficient parallel construction of succinct representations of suffix tree topologies

DOI10.1145/3035540MaRDI QIDQ5270943zbMATH OpenOpenAlexFDO

Authors Uwe Baier, Timo Beller, Enno Ohlebusch

Publication date 3 July 2017

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

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

zbMATH Keywords

algorithm engineeringbalanced parentheses sequencecompressed text indexparallel algorithmssuccinct tree representation

Mathematics Subject Classification ID

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

Recommendations

• Parallel construction of succinct trees
• Parallel construction of a suffix tree with applications
• Engineering a compressed suffix tree implementation
• A simple parallel Cartesian tree algorithm and its application to suffix tree construction
• Optimal parallel suffix tree construction

Cites work

• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• A simple parallel Cartesian tree algorithm and its application to suffix tree construction
• Analysis of the average depth in a suffix tree under a Markov model
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Combined data structure for previous- and next-smaller-values
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees with full functionality
• Engineering a compressed suffix tree implementation
• Faster entropy-bounded compressed suffix trees
• Faster External Memory LCP Array Construction
• scientific article; zbMATH DE number 432779 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2087050 (Why is no real title available?)
• scientific article; zbMATH DE number 2119665 (Why is no real title available?)
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• Linear time construction of compressed text indices in compact space
• On the number of elements to reorder when updating a suffix array
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Optimal succinctness for range minimum queries
• Parallel External Memory Suffix Sorting
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Permuted Longest-Common-Prefix Array
• Replacing suffix trees with enhanced suffix arrays
• Space-efficient parallel construction of succinct representations of suffix tree topologies
• The Parallel Evaluation of General Arithmetic Expressions

Cited in

(5)

• Parallel computation of the Burrows Wheeler transform in compact space
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• Fast matching statistics in small space
• Space-efficient parallel construction of succinct representations of suffix tree topologies

This page was built for publication: Space-efficient parallel construction of succinct representations of suffix tree topologies

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