Optimal lower and upper bounds for representing sequences

DOI10.1145/2629339MaRDI QIDQ4962192zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui, Gonzalo Navarro

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.2621

zbMATH Keywords

string compressionsuccinct data structurestext indexing

Mathematics Subject Classification ID

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

Abstract: Sequence representations supporting queries $access$, $select$ and $rank$ are at the core of many data structures. There is a considerable gap between the various upper bounds and the few lower bounds known for such representations, and how they relate to the space used. In this article we prove a strong lower bound for $rank$, which holds for rather permissive assumptions on the space used, and give matching upper bounds that require only a compressed representation of the sequence. Within this compressed space, operations $access$ and $select$ can be solved in constant or almost-constant time, which is optimal for large alphabets. Our new upper bounds dominate all of the previous work in the time/space map.

Recommendations

• New lower and upper bounds for representing sequences
• Optimal lower bounds for rank and select indexes
• Optimal Lower Bounds for Rank and Select Indexes

Cited in

(39)

• Bounds for parametric sequence comparison
• The nearest colored node in a tree
• Succinct data structures for nearest colored node in a tree
• Fast compressed self-indexes with deterministic linear-time construction
• Range majorities and minorities in arrays
• Space-efficient Huffman codes revisited
• Space efficient merging of de Bruijn graphs and Wheeler graphs
• r-indexing the eBWT
• Compressed dynamic range majority and minority data structures
• Block trees
• Refining the \(r\)-index
• The alternating BWT: an algorithmic perspective
• Grammar compressed sequences with rank/select support
• Length lower bounds for reflecting sequences and universal traversal sequences
• Optimal lower bounds for rank and select indexes
• Grammar-compressed indexes with logarithmic search time
• New lower and upper bounds for representing sequences
• Optimal Lower Bounds for Rank and Select Indexes
• Optimal rank and select queries on dictionary-compressed text
• A new class of searchable and provably highly compressible string transformations
• Tree path majority data structures
• Efficient and compact representations of some non-canonical prefix-free codes
• A new class of string transformations for compressed text indexing
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Lower bounds on lengths of checking sequences
• Random access in persistent strings and segment selection
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• r-indexing the eBWT
• Simplified tight bounds for monotone minimal perfect hashing
• Tight bounds for monotone minimal perfect hashing
• Faster path queries in colored trees via sparse matrix multiplication and min-plus product
• Co-lexicographically ordering automata and regular languages. I
• Approximate suffix-prefix dictionary queries
• Optimal-time queries on BWT-runs compressed indexes
• Lempel-Ziv-78 compressed string dictionaries
• Succinct data structures for Baxter permutation and related families
• Enhancing generalized compressed suffix trees, with applications
• Optimal static fully indexable dictionaries
• Tree path majority data structures

This page was built for publication: Optimal lower and upper bounds for representing sequences

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