Optimal Lower Bounds for Rank and Select Indexes

DOI10.1007/11786986_33MaRDI QIDQ3613774zbMATH OpenOpenAlexFDO

Authors Alexander Golynski

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_33

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Optimal lower bounds for rank and select indexes
• Lower bounds on the size of selection and rank indexes
• Optimal indexes for sparse bit vectors
• Optimal lower and upper bounds for representing sequences
• Optimal trade-offs for succinct string indexes

Cited in

(12)

• Faster entropy-bounded compressed suffix trees
• Rank-select indices without tears
• Wavelet trees for all
• Optimal lower bounds for rank and select indexes
• From time to space: fast algorithms that yield small and fast data structures
• New lower and upper bounds for representing sequences
• Lower bounds on the size of selection and rank indexes
• Optimal trade-offs for succinct string indexes
• Optimal lower and upper bounds for representing sequences
• Succinct representation of dynamic trees
• (Worst-case) optimal adaptive dynamic bitvectors
• A simple storage scheme for strings achieving entropy bounds

This page was built for publication: Optimal Lower Bounds for Rank and Select Indexes

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