Optimal Trade-Off for Succinct String Indexes

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Accepted at ICALP 2010

Scientific paper

Let s be a string whose symbols are solely available through access(i), a read-only operation that probes s and returns the symbol at position i in s. Many compressed data structures for strings, trees, and graphs, require two kinds of queries on s: select(c, j), returning the position in s containing the jth occurrence of c, and rank(c, p), counting how many occurrences of c are found in the first p positions of s. We give matching upper and lower bounds for this problem, improving the lower bounds given by Golynski [Theor. Comput. Sci. 387 (2007)] [PhD thesis] and the upper bounds of Barbay et al. [SODA 2007]. We also present new results in another model, improving on Barbay et al. [SODA 2007] and matching a lower bound of Golynski [SODA 2009]. The main contribution of this paper is to introduce a general technique for proving lower bounds on succinct data structures, that is based on the access patterns of the supported operations, abstracting from the particular operations at hand. For this, it may find application to other interesting problems on succinct data structures.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Optimal Trade-Off for Succinct String Indexes 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 Optimal Trade-Off for Succinct String Indexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Trade-Off for Succinct String Indexes will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-617062

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.