New Lower and Upper Bounds for Representing Sequences

Details New Lower and Upper Bounds for Representing Sequences New Lower and Upper Bounds for Representing Sequences

2011-11-10

arxiv.org/abs/1111.2621v1

Computer Science

Data Structures and Algorithms

15 pages

Scientific paper

Sequence representations supporting queries $access$, $select$ and $rank$ are at the core of many data structures. There is a considerable gap between different upper bounds, and the few lower bounds, known for such a representation, and how they interact with the space used. In this article we prove a strong lower bound for $rank$, which holds for rather permissive assumptions on the space, and give matching upper bounds that require only a compressed representation of the sequence. Within this compressed space, operations $access$ and $select$ can be solved within almost-constant time.

Affiliated with

Also associated with

No associations

Rating

New Lower and Upper Bounds for Representing Sequences 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 New Lower and Upper Bounds for Representing Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Lower and Upper Bounds for Representing Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-139060