Logarithmic Lower Bounds in the Cell-Probe Model

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Second version contains significant changes to the presentation. 32 pages, 1 figure. Journal version of two conference publica

Scientific paper

We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per operation for several data structural problems on n elements, including partial sums, dynamic connectivity among disjoint paths (or a forest or a graph), and several other dynamic graph problems (by simple reductions). Such a lower bound breaks a long-standing barrier of Omega(lg n / lglg n) for any dynamic language membership problem. It also establishes the optimality of several existing data structures, such as Sleator and Tarjan's dynamic trees. We also prove the first Omega(log_B n) lower bound in the external-memory model without assumptions on the data structure (such as the comparison model). Our lower bounds also give a query-update trade-off curve matched, e.g., by several data structures for dynamic connectivity in graphs. We also prove matching upper and lower bounds for partial sums when parameterized by the word size and the maximum additive change in an update.

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

Logarithmic Lower Bounds in the Cell-Probe Model 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 Logarithmic Lower Bounds in the Cell-Probe Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logarithmic Lower Bounds in the Cell-Probe Model will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-28050

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