New Paths from Splay to Dynamic Optimality

Abstract

Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. In this work, we attempt to lay the foundations for a proof of the dynamic optimality conjecture.

Central to our methods are simulation embeddings and approximate monotonicity. A simulation embedding maps each execution to a list of keys that induces a target algorithm to simulate the execution. Approximately monotone algorithms are those whose cost does not increase by more than a constant factor when keys are removed from the list. Approximately monotone algorithms with simulation embeddings are dynamically optimal. Building on these concepts, we present the following results:

1. We build a simulation embedding for Splay by inducing Splay to perform arbitrary subtree transformations. Thus, if Splay is approximately monotone then it is dynamically optimal. We also show that approximate monotonicity is a necessary condition for dynamic optimality.

2. We show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests.

3. We prove that a known lower bound on optimal execution cost by Wilber is approximately monotone.

4. We speculate about how one might establish dynamic optimality by adapting the proof of approximate monotonicity from the lower bound to Splay.

5. We show that the related traversal and deque conjectures also follow if Splay is approximately monotone, and generalize our main results to a broad class of "path-based" algorithms.