New lower and upper bounds for representing sequences. (English) Zbl 1365.68260

Belazzougui, Djamal; Navarro, Gonzalo

Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 181-192 (2012).

Summary: Sequence representations supporting queries access, select and rank are at the core of many data structures. There is a considerable gap between different upper bounds, and the few lower bounds, known for such representations, and how they interact with 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, operations access and select can be solved within almost-constant time.
For the entire collection see [Zbl 1246.68031].

MSC:

68Q12	Quantum algorithms and complexity in the theory of computing
05C40	Connectivity
05C85	Graph algorithms (graph-theoretic aspects)
68Q05	Models of computation (Turing machines, etc.) (MSC2010)