EUVIMEDEUVIMED entdecken
Crossref

Optimal Lower and Upper Bounds for Representing Sequences

Djamal Belazzougui, Gonzalo Navarro

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →