Inducing Suffix and LCP Arrays in External Memory

DOI10.1145/2975593zbMath1365.68169OpenAlexW2519490418MaRDI QIDQ5266606

Johannes Fischer, Vitaly Osipov, Timo Bingmann

Publication date: 16 June 2017

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

Full work available at URL: https://publikationen.bibliothek.kit.edu/1000038067

zbMATH Keywords

suffix arrayexternal memoryLCP arraysecondary memoryI/O-efficient

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (3)

Engineering a lightweight external memory suffix array construction algorithm ⋮ Burrows-Wheeler transform and LCP array construction in constant space ⋮ Inducing enhanced suffix arrays for string collections

Uses Software

• STXXL
• SeqAn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• The buffer tree: A technique for designing batched external data structures
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Engineering a lightweight suffix array construction algorithm
• Lightweight data indexing and compression in external memory
• Space efficient linear time construction of suffix arrays
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Suffix Arrays on Words
• Optimal Succinctness for Range Minimum Queries
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Permuted Longest-Common-Prefix Array
• Lightweight LCP Construction for Next-Generation Sequencing Datasets
• Inducing the LCP-Array
• Inducing Suffix and LCP Arrays in External Memory
• Fast and Lightweight LCP-Array Construction Algorithms
• An efficient, versatile approach to suffix sorting
• Better external memory suffix array construction
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Algorithm Theory - SWAT 2004
• Dynamic LCA Queries on Trees
• Fast priority queues for cached memory
• On the sorting-complexity of suffix tree construction

This page was built for publication: Inducing Suffix and LCP Arrays in External Memory