Document Type

Book Chapter

Publication Date

2018

Published In

37th IARCS Annual Conference On Foundations Of Software Technology And Theoretical Computer Science

Series Title

Leibniz International Proceedings In Informatics

Abstract

In this work, we continue the examination of the role non-adaptivity plays in maintaining dynamic data structures, initiated by Brody and Larsen. We consider non-adaptive data structures for predecessor search in the w-bit cell probe model. In this problem, the goal is to dynamically maintain a subset T of up to n elements from {1, ..., m}, while supporting insertions, deletions, and a predecessor query Pred(x), which returns the largest element in T that is less than or equal to x. Predecessor search is one of the most well-studied data structure problems. For this problem, using non-adaptivity comes at a steep price. We provide exponential cell probe complexity separations between (i) adaptive and non-adaptive data structures and (ii) non-adaptive and memoryless data structures for predecessor search. A classic data structure of van Emde Boas solves dynamic predecessor search in log(log(m)) probes; this data structure is adaptive. For dynamic data structures which make non-adaptive updates, we show the cell probe complexity is O(log(m)/log(w/log(m))). We also give a nearly-matching Omega(log(m)/log(w)) lower bound. We also give an m/w lower bound for memoryless data structures. Our lower bound technique is tailored to non-adaptive (as opposed to memoryless) updates and might be of independent interest.

Keywords

dynamic data structures, lower bounds, predecessor search, non-adaptivity

Published By

Schloss Dagstuhl

Editor(s)

S. Lokam and R. Ramanujam

Conference

37th IARCS Annual Conference On Foundations Of Software Technology And Theoretical Computer Science

Conference Dates

December 12-14, 2017

Conference Location

Kanpur, India

Creative Commons License

Creative Commons Attribution 3.0 License
This work is licensed under a Creative Commons Attribution 3.0 License.

Download

Share

COinS