Time-Space Trade-Offs for Predecessor Search

Details Time-Space Trade-Offs for Predecessor Search Time-Space Trade-Offs for Predecessor Search

2006-03-10

arxiv.org/abs/cs/0603043v1

Computer Science

Computational Complexity

29 pages. Full version (preliminary) of a paper appearing in STOC'06

Scientific paper

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity. Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. Given a set Y of n integers of l bits each, the goal is to efficiently find predecessor(x) = max{y in Y | y <= x}, by representing Y on a RAM using space S. In external memory, it follows that the optimal strategy is to use either standard B-trees, or a RAM algorithm ignoring the larger block size. In the important case of l = c*lg n, for c>1 (i.e. polynomial universes), and near linear space (such as S = n*poly(lg n)), the optimal search time is Theta(lg l). Thus, our lower bound implies the surprising conclusion that van Emde Boas' classic data structure from [FOCS'75] is optimal in this case. Note that for space n^{1+eps}, a running time of O(lg l / lglg l) was given by Beame and Fich [STOC'99].

Affiliated with

Also associated with

No associations

Rating

Time-Space Trade-Offs for Predecessor Search 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 Time-Space Trade-Offs for Predecessor Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time-Space Trade-Offs for Predecessor Search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-114622