Skip navigation
Please use this identifier to cite or link to this item:
Title: New Paths from Splay to Dynamic Optimality
Authors: Levy, Caleb
Advisors: Tarjan, Robert E
Contributors: Applied and Computational Mathematics Department
Keywords: Additive Overhead
Approximate Monotonicity
Dynamic Optimality
Simulation Embedding
Splay Trees
Subtree Transformations
Subjects: Computer science
Applied mathematics
Issue Date: 2019
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Levy_princeton_0181D_13029.pdf1.14 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.