
Banff International Research Station for Mathematical Innovation and Discovery
Brody, Joshua
—
2017-09-18
Unreviewed
Non UBC
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 non-adaptive 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 adaptive data structure of van Emde Boas solves dynamic predecessor search in $O(\log \log m)$ probes. For dynamic data structures which make non-adaptive updates, we show the cell probe complexity is $O(min{ (log m)/(log(w/log m)$, $(n log m)/w) })$. We also give a nearly-matching $\Omega( min {(log m)/(log w)$, $(nlog m)/(w log w) })$ lower bound. We also give an $\Omega(m)$ 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.
Joint work with Joe Boninger and Owen Kephart.
Faculty
Author affiliation: Swarthmore College
http://creativecommons.org/licenses/by-nc-nd/4.0/