Output details
11 - Computer Science and Informatics
University of Leicester
Return to search
Output 0 of 0 in the submission
Output title
Optimal Trade-Offs for Succinct String Indexes
Type
E - Conference contribution
Name of conference/published proceedings
Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I
Volume number
-
Issue number
-
First page of article
678
ISSN of proceedings
-
Year of publication
2010
URL
-
Number of additional authors
2
Additional information
<12>We give (almost) matching upper and lower bounds on time-space tradeoffs for succinct indices for the fundamental rank and select operations on strings. The lower bound technique, which surpasses limitations of previous ones (Golynski [TCS'07,SODA'09]) was subsequently generalized to other related problems by Orlandi (PhD thesis, Pisa). The upper bound is a "plug-in" improvement of a well-known result of Barbay et al. [SODA'07] and, as such, is used in a number of more recent results e.g. Gagie et al. [TCS'13], Belazzougui and Navarro [ESA'11,'12], Hon et al. [CPM'13], Barbay et al. [Algorithmica'13].
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
4
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
