Optimal Lower and Upper Bounds for Representing Sequences
ACM Transactions on Algorithms · 23.06.2015 · 11 (4) · 1-21
DOI: 10.1145/2629339 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 13.04.2015. Verfasst von Djamal Belazzougui und 1 weiteren Autor:innen. Die Arbeit wurde bisher 41-mal zitiert (Crossref) und nennt 38 Literaturangaben. Gefördert von: Academy of Finland, Fondecyt, French ANR-2010-COSI-004 MAPPI Project.
Abstract (Originalsprache)
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.
Förderung
- Academy of Finland
- Fondecyt
- French ANR-2010-COSI-004 MAPPI Project
Zitieren
APA
Belazzougui, D., & Navarro, G. (2015). Optimal Lower and Upper Bounds for Representing Sequences. ACM Transactions on Algorithms, 11(4), 1-21. https://doi.org/10.1145/2629339
Vancouver
Belazzougui D, Navarro G. Optimal Lower and Upper Bounds for Representing Sequences. ACM Transactions on Algorithms. 2015;11(4):1-21. doi:10.1145/2629339
BibTeX
@article{Belazzougui2015,
author = {Belazzougui, Djamal and Navarro, Gonzalo},
title = {Optimal Lower and Upper Bounds for Representing Sequences},
journal = {ACM Transactions on Algorithms},
year = {2015},
volume = {11},
number = {4},
pages = {1--21},
doi = {10.1145/2629339}
}
EUVIMED