Optimal lower bounds for rank and select indexes

DOI10.1016/j.tcs.2007.07.041zbMath1144.68016OpenAlexW1977986119MaRDI QIDQ2465065

Alexander Golynski

Publication date: 19 December 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.041

zbMATH Keywords

lower boundssuccinct data structuresfully indexable dictionary

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (27)

Succinct indices for path minimum, with applications ⋮ The range 1 query (R1Q) problem ⋮ The function-inversion problem: barriers and opportunities ⋮ Compact binary relation representations with rich functionality ⋮ Entropy-bounded representation of point grids ⋮ Colored range queries and document retrieval ⋮ An Opportunistic Text Indexing Structure Based on Run Length Encoding ⋮ On compressing permutations and adaptive sorting ⋮ Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms ⋮ Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order ⋮ Succinct representations of permutations and functions ⋮ Wavelet trees for all ⋮ Succinct Representations of Arbitrary Graphs ⋮ Efficient fully-compressed sequence representations ⋮ Optimal indexes for sparse bit vectors ⋮ Rank and select revisited and extended ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ On space efficient two dimensional range minimum data structures ⋮ Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order ⋮ Wee LCP ⋮ Selection from read-only memory with limited workspace ⋮ Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster ⋮ From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures ⋮ Random Access to High-Order Entropy Compressed Text ⋮ A Survey of Data Structures in the Bitprobe Model ⋮ Array Range Queries

Cites Work

• Space Efficient Suffix Trees
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Unnamed Item

This page was built for publication: Optimal lower bounds for rank and select indexes