Optimal Lower and Upper Bounds for Representing Sequences

Authors:

Abstract
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 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, the 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.
Funding Information
  • Research Council of Finland (250345 (Co-ECGR))
  • FONDECYT (1-110066)
  • French ANR-2010-COSI-004 MAPPI Project

This publication has 21 references indexed in Scilit: