A Lower Bound for Succinct Rank Queries

Details A Lower Bound for Succinct Rank Queries A Lower Bound for Succinct Rank Queries

2009-07-06

arxiv.org/abs/0907.1103v1

Computer Science

Data Structures and Algorithms

7 pages

Scientific paper

The rank problem in succinct data structures asks to preprocess an array A[1..n] of bits into a data structure using as close to n bits as possible, and answer queries of the form rank(k) = Sum_{i=1}^k A[i]. The problem has been intensely studied, and features as a subroutine in a majority of succinct data structures. We show that in the cell probe model with w-bit cells, if rank takes t time, the space of the data structure must be at least n + n/w^{O(t)} bits. This redundancy/query trade-off is essentially optimal, matching our upper bound from [FOCS'08].

Affiliated with

Also associated with

No associations

Rating

A Lower Bound for Succinct Rank Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Lower Bound for Succinct Rank Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Lower Bound for Succinct Rank Queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355180