Engineering a lightweight external memory suffix array construction algorithm

DOI10.1007/S11786-016-0281-1MaRDI QIDQ2363989zbMATH OpenOpenAlexFDO

Authors Juha Kärkkäinen, Dominik Kempa

Publication date 17 July 2017

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11786-016-0281-1

zbMATH Keywords

algorithm engineeringexternal memory algorithmssuffix array construction

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• A theoretical and experimental study on the construction of suffix arrays in external memory
• Engineering a lightweight suffix array construction algorithm
• Better external memory suffix array construction
• Better external memory LCP array construction
• Inducing suffix and LCP arrays in external memory

Cites work

• A theoretical and experimental study on the construction of suffix arrays in external memory
• Algorithms and data structures for external memory
• Alphabet partitioning for compressed rank/select and applications
• Better external memory suffix array construction
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Compressed representations of sequences and full-text indexes
• External memory generalized suffix and LCP arrays construction
• Fast BWT in small space by blockwise suffix sorting
• Fast Pattern Matching in Strings
• Indexing compressed text
• Inducing suffix and LCP arrays in external memory
• LCP array construction in external memory
• Lightweight data indexing and compression in external memory
• Linear work suffix array construction
• New lower and upper bounds for representing sequences
• Replacing suffix trees with enhanced suffix arrays
• String range matching
• String-matching on ordered alphabets
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(16)

• Engineering a lightweight suffix array construction algorithm
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• Faster average case low memory semi-external construction of the Burrows-Wheeler transform
• Faster semi-external suffix sorting
• Fast lightweight suffix array construction and checking
• Lightweight parameterized suffix array construction
• scientific article; zbMATH DE number 1947433 (Why is no real title available?)
• Faster External Memory LCP Array Construction
• Better external memory LCP array construction
• External memory BWT and LCP computation for sequence collections with applications
• Engineering External Memory Induced Suffix Sorting
• Lightweight distributed suffix array construction
• LCP array construction in external memory
• Faster compressed suffix trees for repetitive collections
• Better external memory suffix array construction
• A theoretical and experimental study on the construction of suffix arrays in external memory

Describes a project that uses

Uses Software

• libdivsufsort

This page was built for publication: Engineering a lightweight external memory suffix array construction algorithm

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