Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-050 | 15th March 2017 20:15

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

RSS-Feed




TR17-050
Authors: Joe Boninger, Joshua Brody, Owen Kephart
Publication: 16th March 2017 06:27
Downloads: 1324
Keywords: 


Abstract:

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. 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 [vEB75] solves dynamic predecessor search in O(\log \log m) probes; this data structure is adaptive. For dynamic data structures which make nonadaptive updates, we show the cell probe complexity is O\left(\min\{\frac{\log m}{\log(w/\log m)}, \frac{n\log m}{w}\}\right). We also give a nearly-matching \Omega\left(\min\{\frac{\log m}{\log w}, \frac{n \log m}{w \log w}\}\right) lower bound. We also give an \Omega(m) lower bound for memoryless data structures.
Our lower bound technique is tailored to nonadaptive (as opposed to memoryless) updates and should be of independent interest.



ISSN 1433-8092 | Imprint