RIA: Problems Arising in Persistent Data Structures

点击翻译按钮获取中文摘要

In recent years, work in persistent data structures had yielded interesting algorithms with applications to many areas of practical interest. Techniques have been given for making classes of data structures persistent, and an important underlying problem, the order maintenance problem (OMP), has been discovered and solved. This project explores ways to improve existing algorithms. The elimination of amortization in list labeling and in general persistence techniques, and the development of an optimal algorithm for a generalization of OMP are two parties. The hope is that this new algorithm will be useful in a practical as well as in a theoretical sense. In addition, the project explores lower bound problems associated with persistent data structures. These lower bounds will confirm that existing algorithms are in some ways optimal. and many produce proof techniques applicable to other data structure problems.