Optimal Lower and Upper Bounds for Representing Sequences
Optimal Lower and Upper Bounds for Representing Sequences
Sequence representations supporting the 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 …