Optimal Lower and Upper Bounds for Representing Sequences
Authors:
Open Access
- 13 April 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 11 (4) , 1-21
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.Keywords
All Related Versions
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:
- Efficient Fully-Compressed Sequence RepresentationsAlgorithmica, 2012
- Succinct indexes for strings, binary relations and multilabeled treesACM Transactions on Algorithms, 2011
- Compressing and indexing labeled trees, with applicationsJournal of the ACM, 2009
- Compressed data structures: Dictionaries and data-aware measuresTheoretical Computer Science, 2007
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisetsACM Transactions on Algorithms, 2007
- Compressed representations of sequences and full-text indexesACM Transactions on Algorithms, 2007
- A simple storage scheme for strings achieving entropy boundsTheoretical Computer Science, 2007
- Large alphabets and incompressibilityInformation Processing Letters, 2006
- Indexing compressed textJournal of the ACM, 2005
- An analysis of the Burrows—Wheeler transformJournal of the ACM, 2001