Output details
11 - Computer Science and Informatics
University of Leicester
Article title
Optimal Indexes for Sparse Bit Vectors
Type
D - Journal article
Title of journal
Algorithmica
Article number
N/A (online first)
Volume number
N/A (online firs
Issue number
-
First page of article
1
ISSN of journal
0178-4617
Year of publication
2013
URL
-
Number of additional authors
3
Additional information
<12>The conference version of this paper ("On the redundancy of succinct data structures", SWAT'08) opened up the question of determining the redundancy needed to support the fundamental rank/select operations on binary strings in the frequently-occurring situation where the binary string has relatively few 1s, and several authors applied the results presented there. This paper closes off one direction by providing matching upper and lower bounds for the systematic/succinct index case, generalizing the bounds of Golynski [ICALP'06,TCS'07]. The unrestricted case was closed off by Patrascu and Viola [SODA'10] and Patrascu [FOCS'08].
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
