Lightweight data indexing and compression in external memory
From MaRDI portal
Publication:2429367
DOI10.1007/s00453-011-9535-0zbMath1241.68062OpenAlexW2011699809MaRDI QIDQ2429367
Paolo Ferragina, Giovanni Manzini, Travis Gagie
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9535-0
data compressionBurrows-Wheeler transformcompressed indexesspace-efficient algorithmsexternal memory scan-based algorithms
Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items
Extended suffix array construction using Lyndon factors ⋮ Engineering a lightweight external memory suffix array construction algorithm ⋮ Faster average case low memory semi-external construction of the Burrows-Wheeler transform ⋮ The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words ⋮ Optimal in-place suffix sorting ⋮ Suffix array and Lyndon factorization of a text ⋮ Parallel algorithms for Burrows-Wheeler compression and decompression ⋮ Faster semi-external suffix sorting ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ Burrows-Wheeler transform and LCP array construction in constant space ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ Bidirectional Text Compression in External Memory ⋮ On the Value of Multiple Read/Write Streams for Data Compression ⋮ Prefix-Free Parsing for Building Big BWTs ⋮ Inducing Suffix and LCP Arrays in External Memory ⋮ LCP Array Construction in External Memory ⋮ Faster Compressed Suffix Trees for Repetitive Collections
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
- A space and time efficient algorithm for constructing compressed suffix arrays
- Burrows-Wheeler transform and Sturmian words
- Selection and sorting with limited storage
- Linear probing and graphs
- Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
- Fast BWT in small space by blockwise suffix sorting
- Algorithms and Data Structures for External Memory
- Compressed representations of sequences and full-text indexes
- Space-Conscious Compression
- Compression, Indexing, and Retrieval for Massive String Data
- On the Value of Multiple Read/Write Streams for Data Compression
- Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
- Pushdown Compression
- Better external memory suffix array construction
- In-Place Suffix Sorting
- The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
- On the sorting-complexity of suffix tree construction
- An introduction to Kolmogorov complexity and its applications
- A theoretical and experimental study on the construction of suffix arrays in external memory
