Lightweight data indexing and compression in external memory

DOI10.1007/S00453-011-9535-0MaRDI QIDQ2429367zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

data compressioncompressed indexesBurrows-Wheeler transformspace-efficient algorithmsexternal memory scan-based algorithms

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

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

Cites work

• scientific article; zbMATH DE number 910869 (Why is no real title available?)
• A space and time efficient algorithm for constructing compressed suffix arrays
• A theoretical and experimental study on the construction of suffix arrays in external memory
• Algorithms and data structures for external memory
• Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
• An introduction to Kolmogorov complexity and its applications
• Better external memory suffix array construction
• Breaking a time-and-space barrier in constructing full-text indices
• Burrows-Wheeler transform and Sturmian words
• Compressed representations of sequences and full-text indexes
• Compression, indexing, and retrieval for massive string data
• Data streams: algorithms and applications.
• Fast BWT in small space by blockwise suffix sorting
• In-Place Suffix Sorting
• Linear probing and graphs
• On the sorting-complexity of suffix tree construction
• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
• Pushdown compression
• Selection and sorting with limited storage
• Space-Conscious Compression
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression

Cited in

(19)

• Parallel algorithms for Burrows-Wheeler compression and decompression
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Engineering a lightweight external memory suffix array construction algorithm
• Suffix array and Lyndon factorization of a text
• Extended suffix array construction using Lyndon factors
• Faster semi-external suffix sorting
• Faster compressed suffix trees for repetitive collections
• Full-text indexes for high-throughput sequencing
• Prefix-free parsing for building big BWTs
• The Burrows-Wheeler transform between data compression and combinatorics on words
• Lightweight data indexing and compression in external memory
• Bidirectional Text Compression in External Memory
• Lightweight merging of compressed indices based on BWT variants
• Faster average case low memory semi-external construction of the Burrows-Wheeler transform
• Optimal in-place suffix sorting
• Burrows-Wheeler transform and LCP array construction in constant space
• Inducing suffix and LCP arrays in external memory
• LCP array construction in external memory
• Computing the multi-string BWT and LCP array in external memory

Describes a project that uses

Uses Software

• UbiCrawler

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)