Flexible indexing of repetitive collections

DOI10.1007/978-3-319-58741-7_17MaRDI QIDQ2011648zbMATH OpenOpenAlexFDO

Authors Fabio Cunial, Travis Gagie, Nicola Prezza, Djamal Belazzougui, Mathieu Raffinot

Publication date 4 August 2017

Full work available at URL https://orbit.dtu.dk/en/publications/9d82245e-1742-429a-a17a-b16b809cf4aa

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 6850405
• Self-indexing based on LZ77
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Indexing highly repetitive collections
• On compressing and indexing repetitive sequences

Cites work

• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Combinatorial Pattern Matching
• Composite repetition-aware data structures
• Indexing compressed text
• LZ77-based self-indexing with faster pattern matching
• Linear time construction of compressed text indices in compact space
• Log-logarithmic worst-case range queries are possible in space theta(N)
• On compressing and indexing repetitive sequences
• On maximal repeats in strings
• Orthogonal range searching on the RAM, revisited
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Self-indexing based on LZ77
• Stronger Lempel-Ziv based compressed text indexing
• Succinct representation of balanced parentheses and static trees
• The Complexity of Some Simple Retrieval Problems

Cited in

(13)

• Document Listing on Repetitive Collections with Guaranteed Performance
• Indexing highly repetitive collections
• Storage and Retrieval of Individual Genomes
• Self-indexing based on LZ77
• Universal compressed text indexing
• Optimal construction of compressed indexes for highly repetitive texts
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• scientific article; zbMATH DE number 1216206 (Why is no real title available?)
• On compressing and indexing repetitive sequences
• Document listing on repetitive collections with guaranteed performance
• Contextual Pattern Matching
• Composite repetition-aware data structures

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: Flexible indexing of repetitive collections

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