Lightweight data indexing and compression in external memory
DOI10.1007/S00453-011-9535-0zbMATH Open1241.68062OpenAlexW2011699809MaRDI QIDQ2429367FDOQ2429367
Authors: Paolo Ferragina, Travis Gagie, Giovanni Manzini 
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
Recommendations
- Lightweight data indexing and compression in external memory
- Faster average case low memory semi-external construction of the Burrows-Wheeler transform
- Fast BWT in small space by blockwise suffix sorting
- Lightweight algorithms for constructing and inverting the BWT of string collections
- Lightweight BWT construction for very large string collections
data compressioncompressed indexesBurrows-Wheeler transformspace-efficient algorithmsexternal memory scan-based algorithms
Data structures (68P05) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Algorithms and data structures for external memory
- Compressed representations of sequences and full-text indexes
- Data streams: algorithms and applications.
- Linear probing and graphs
- An introduction to Kolmogorov complexity and its applications
- Selection and sorting with limited storage
- Compression, indexing, and retrieval for massive string data
- Fast BWT in small space by blockwise suffix sorting
- Breaking a time-and-space barrier in constructing full-text indices
- A space and time efficient algorithm for constructing compressed suffix arrays
- Title not available (Why is that?)
- Burrows-Wheeler transform and Sturmian words
- Space-Conscious Compression
- On the sorting-complexity of suffix tree construction
- In-Place Suffix Sorting
- Pushdown compression
- Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
- The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
- Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
- Better external memory suffix array construction
- A theoretical and experimental study on the construction of suffix arrays in external memory
Cited In (20)
- Lightweight algorithms for constructing and inverting the BWT of string collections
- Full-text indexes for high-throughput sequencing
- Parallel algorithms for Burrows-Wheeler compression and decompression
- The Burrows-Wheeler transform between data compression and combinatorics on words
- Bidirectional Text Compression in External Memory
- Computing the multi-string BWT and LCP array in external memory
- Faster semi-external suffix sorting
- Inducing suffix and LCP arrays in external memory
- LCP array construction in external memory
- Lightweight merging of compressed indices based on BWT variants
- Engineering a lightweight external memory suffix array construction algorithm
- Extended suffix array construction using Lyndon factors
- Lightweight data indexing and compression in external memory
- Suffix array and Lyndon factorization of a text
- Faster average case low memory semi-external construction of the Burrows-Wheeler transform
- Optimal in-place suffix sorting
- Prefix-free parsing for building big BWTs
- Faster compressed suffix trees for repetitive collections
- On the Value of Multiple Read/Write Streams for Data Compression
- Burrows-Wheeler transform and LCP array construction in constant space
Uses Software
This page was built for publication: Lightweight data indexing and compression in external memory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429367)
