Non-Adaptive and Memoryless Bounds for Dynamic Predecessor
Non-Adaptive and Memoryless Bounds for Dynamic Predecessor
Joe Boninger, Owen Kephart, and Joshua Brody
Many important problems in theoretical computer science are known as data structure problems -- in these problems, you are given a set of data and must store it in a way which allows you to quickly respond to queries about it. In a dynamic data structure problem, there is the added responsibility of quickly changing the data in response to update requests. One well-studied dynamic data structure problem is Dynamic Predecessor, in which the data stored is a subset S of the integers {1, ... , m}. Updates require the user to insert and delete integers in the subset, and queries of the form query(x) require the user to return the largest element in S that is less than or equal to x.
In our research we looked at two restrictive classes of algorithms: non-adaptive and memoryless. An algorithm is non-adaptive if the memory locations it accesses depend only on its input, and not on the contents of other memory locations it reads. An algorithm is memoryless if the content it writes to a memory location depends only on its input and on the previous contents of that same memory location, and not on the contents of any other locations. These two algorithm types appear naturally in solutions to many other data structure problems, and have been used to produce high lower bounds [2].
Our Results:
- Dynamic Predecessor can be solved non-adaptively with O(log(m)) updates and queries.
- Using memoryless updates, queries for Dynamic Predecessor are Omega(m/w), regardless of update time.
- Any non-adaptive data structure for Dynamic Predecessor has either update or query time Omega(log(m)/loglog(m))
In addition to the bounds above, we developed two potential approaches for proving lower bounds for solutions to Dynamic Predecessor that are non-adaptive but not memoryless. As there are currently no known, general techniques which can find lower bounds for non-adaptive data structures, we believe our methods could potentially be very useful.
Literature cited:
[1] Paul Beame and Faith E. Fich. Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci., 65(1):38-72, August 2002.
[2] Joshua Brody and Kasper Green Larsen. Adapt or die: Polynomial lower bounds for non-adaptive dynamic data structures. CoRR, abs/1208.2846, 2012.
