Improvements to Online Learning Algorithms with Applications to Binary Search Trees

Abstract

In this work we are motivated by the question: "How to automatically adapt to, or learn, structure in the past inputs of an algorithm?". This question might arise from the need to decrease the amount of consumed resources, such as run-time or money. In addition, we also consider, in part, the growing significance of the IO-issues in computation. A major focus is on studying data structures, such as binary search trees (BSTs). They are a common and practical solution to the problem of representing data such as sets; hence it is important to understand their properties.

For the most part we work with algorithms which continuously serve requests under uncertainty about future inputs. These algorithms are called online algorithms. To analyze their performance we use the competitive analysis. In it the uncertainty over future inputs is not necessarily modeled stochastically, but rather we deal with the uncertainty by comparing our own performance to how well we could have done had we known the input sequence.