2026-08-17T06:34:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8389 2024-03-06T10:41:57Z ddc:004 open_access

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Boninger, Joseph Brody, Joshua Kephart, Owen dynamic data structures lower bounds predecessor search non-adaptivity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joseph Boninger and Joshua Brody and Owen Kephart 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.20 urn:nbn:de:0030-drops-83892 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.20 eng https://creativecommons.org/licenses/by/3.0/legalcode