Optimal lower bounds for rank and select indexes

No abstract is available for this paper.

• Publication year

  2006

• Venue

  Theoretical Computer Science

• Publication date

  2006-07-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2007.07.041
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lower bounds on the size of selection and rank indexes

  2005cited by this paper
• Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

  2002cited by this paper
• Space Efficient Suffix Trees

  1998cited by this paper
• Compact pat trees

  1998cited by this paper
• Succinct static data structures

  1988influential reference

• Theory Meets Practice for Bit Vectors Supporting Rank and Select

  2025influential citation
• Ranking and unranking algorithms for derangements based on lexicographical order

  2025cites this paper
• Zombit: Exploiting Runs in Bitvectors

  2025cites this paper
• (Worst-case) Optimal Adaptive Dynamic Bitvectors

  2024cites this paper
• Pfp-fm: an accelerated FM-index

  2024cites this paper
• Dynamic “Succincter”

  2023cites this paper
• of generation, ranking and unranking left-child sequences in lexico-graphic

  2023cites this paper
• A Learned Approach to Design Compressed Rank/Select Data Structures

  2022cites this paper
• A "Learned" Approach to Quicken and Compress Rank/Select Dictionaries

  2021cites this paper
• A comprehensive analysis of wavelet tree based indexing schemes in GIR systems

  2021cites this paper
• Rank/Select Queries over Mutable Bitmaps

  2020cites this paper
• Bitvectors with Runs and the Successor/Predecessor Problem

  2020cites this paper
• Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster

  2019cites this paper
• Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order

  2019cites this paper
• Highly Succinct Dynamic Data Structures

  2019cites this paper
• Space Efficient Construction of Lyndon Arrays in Linear Time

  2019cites this paper
• Space-Efficient DFS and Applications: Simpler, Leaner, Faster

  2018cites this paper
• Optimal succinct rank data structure via approximate nonnegative tensor decomposition

  2018cites this paper
• In-Memory Storage for Labeled Tree-Structured Data

  2017cites this paper
• Rank-Select Indices Without Tears

  2017cites this paper
• Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order

  2016cites this paper
• Succinct Indices for Path Minimum, with Applications

  2016cites this paper
• Succinct Choice Dictionaries

  2016cites this paper
• Rank and Select Operations on Binary Strings

  2016cites this paper
• Succinct Data Structures ... Potential for Symbolic Computation?

  2016cites this paper
• Data structures for temporal graphs based on compact sequence representations

  2015cites this paper
• Statistical and repetition-based compressed data structures

  2015cites this paper
• Sampling from Discrete Distributions and Computing Frechet Distances

  2015cites this paper
• An Opportunistic Text Indexing Structure Based on Run Length Encoding

  2015cites this paper
• Succinct Indices for Path Minimum, with Applications to Path Reporting

  2014cites this paper
• Indexed Matching Statistics and Shortest Unique Substrings

  2014cites this paper
• The Range 1 Query (R1Q) Problem

  2014cites this paper
• Array Range Queries

  2013cites this paper
• Selection from read-only memory with limited workspace

  2013cites this paper
• Random Access to High-Order Entropy Compressed Text

  2013cites this paper
• Succinct sampling from discrete distributions

  2013cites this paper
• From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures

  2013cites this paper
• A Survey of Data Structures in the Bitprobe Model

  2013cites this paper
• Space-Efficient Data Structures in the Word-RAM and Bitprobe Models

  2013cites this paper
• Optimal Prefix Free Code in Linear Time

  2012cites this paper
• Compact binary relation representations with rich functionality

  2012cites this paper
• Wavelet trees: A survey

  2012cites this paper
• Fast, Small, Simple Rank/Select on Bitmaps

  2012cites this paper
• Wavelet trees for all

  2012influential citation
• Advanced rank/select data structures: succinctness, bounds and applications

  2012cites this paper
• New Lower and Upper Bounds for Representing Sequences

  2011cites this paper
• On compressing permutations and adaptive sorting

  2011cites this paper
• Succinct representations of permutations and functions

  2011cites this paper
• Succinct representation of dynamic trees

  2011cites this paper
• Theory and practice of monotone minimal perfect hashing

  2011cites this paper
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays

  2011cites this paper
• Optimal Lower and Upper Bounds for Representing Sequences

  2011cites this paper
• Optimal Indexes for Sparse Bit Vectors

  2011cites this paper
• Advantages of Shared Data Structures for Sequences of Balanced Parentheses

  2010cites this paper
• Cell-probe lower bounds for succinct partial sums

  2010cites this paper
• Optimal Trade-Offs for Succinct String Indexes

  2010cites this paper
• Colored range queries and document retrieval

  2010cites this paper
• Entropy-bounded representation of point grids

  2010influential citation
• LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations

  2010cites this paper
• On Space Efficient Two Dimensional Range Minimum Data Structures

  2010cites this paper
• Data Structures: Time, I/Os, Entropy, Joules!

  2010cites this paper
• A Data Structure for Sponsored Search

  2009cites this paper
• Efficient Fully-Compressed Sequence Representations

  2009cites this paper
• Compressed Representations of Permutations, and Applications

  2009cites this paper
• Theory and Practise of Monotone Minimal Perfect Hashing

  2009cites this paper
• New algorithms for exact and approximate text matching

  2009cites this paper
• Succinct Representation of Trees and Graphs

  2009cites this paper
• Wee LCP

  2009cites this paper
• Faster entropy-bounded compressed suffix trees

  2009cites this paper
• A Lower Bound for Succinct Rank Queries

  2009cites this paper
• Succinct Representations of Trees

  2009cites this paper
• More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries

  2009cites this paper
• Succincter

  2008cites this paper
• Upper and Lower Bounds for Text Upper and Lower Bounds for Text Indexing Data Structures

  2008influential citation
• Error-Correcting Data Structures

  2008cites this paper
• Broadword Implementation of Rank/Select Queries

  2008cites this paper
• Optimal Succinctness for Range Minimum Queries

  2008cites this paper
• RODRIGO RENATO GONZÁLEZ DEL BARRIO

  2008cites this paper
• Succinct Indexes

  2008cites this paper
• On the Redundancy of Succinct Data Structures

  2008influential citation
• Succinct indexes for strings, binary relations and multilabeled trees

  2007cites this paper
• On the Size of Succinct Indices

  2007cites this paper
• A Compressed Text Index on Secondary Memory ∗

  2007cites this paper
• Compressed full-text indexes

  2007influential citation
• A simple storage scheme for strings achieving entropy bounds

  2007cites this paper
• Rank and select revisited and extended

  2007cites this paper
• A Succinct Indexes for Strings , Binary Relations and Multi-labeled Trees

  2007influential citation
• The Latest Trend of Compressed Data Structures

  2006cites this paper
• Practical Entropy-Compressed Rank/Select Dictionary

  2006cites this paper
• Rank and Select Operations on Binary Strings ( 1974 ; Elias )

  year unknowncites this paper
• Some Experimental Results on Data Structure Compression

  year unknowncites this paper