RIA: Problems Arising in Persistent Data Structures

近年来，持久化数据结构的工作已经产生了有趣的算法，并应用于许多实际感兴趣的领域。已经给出了使数据结构类持久化的技术，并且已经发现并解决了一个重要的潜在问题--顺序维护问题(OMP)。这个项目探索了改进现有算法的方法。消除列表标记和一般持久化技术中的摊销，以及开发用于OMP推广的优化算法是两个方面。希望这种新算法不仅在理论上，而且在实际中也是有用的。此外，该项目还探讨了与持久化数据结构相关的下限问题。这些下限将证实现有算法在某些方面是最优的。许多证明技术也适用于其他数据结构问题。

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.