Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies

DOI10.1145/3035540zbMath1369.68166OpenAlexW2582314531MaRDI QIDQ5270943

Enno Ohlebusch, Timo Beller, Uwe Baier

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

parallel algorithmsalgorithm engineeringsuccinct tree representationbalanced parentheses sequencecompressed text index

Mathematics Subject Classification ID

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

Related Items

Parallel computation of the Burrows Wheeler transform in compact space ⋮ Fast matching statistics in small space ⋮ Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of elements to reorder when updating a suffix array
• Combined data structure for previous- and next-smaller-values
• Replacing suffix trees with enhanced suffix arrays
• Faster entropy-bounded compressed suffix trees
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Compressed suffix trees with full functionality
• Parallel External Memory Suffix Sorting
• Compressed representations of sequences and full-text indexes
• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• Optimal Succinctness for Range Minimum Queries
• Permuted Longest-Common-Prefix Array
• The Parallel Evaluation of General Arithmetic Expressions
• Faster External Memory LCP Array Construction
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• A Simple Parallel Cartesian Tree Algorithm and its Application to Suffix Tree Construction
• Linear time construction of compressed text indices in compact space
• Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
• Engineering a compressed suffix tree implementation

This page was built for publication: Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies