Research Initiation Award: Making Data Structures Persistent

本研究的目的是设计使普通数据结构持久的通用方法。普通数据结构是短暂的，因为对它们的任何更改都会破坏旧版本，只留下经过修改的新版本。持久数据结构记住它们过去的版本，允许对任何版本进行访问和更新操作。已知的一些通用方法可以将链接的数据结构转换为高效的持久数据结构。本研究的目的是设计新的方法使数据结构持久，特别是某些任意程度的链接结构，没有这样的方法已知。持久数据结构在许多领域都很有用，包括计算几何、非常高级语言的实现和文本编辑。

The purpose of this study is to devise general methods for making ordinary data structures persistent. Ordinary data structures are ephemeral in that any change to them destroys the old version, leaving only the new, modified version. Persistent data structures remember their past versions allowing both access and update operations to any version. Some general methods are known that can transform linked data structures into efficient persistent data structures. This study aims to devise new methods for making data structures persistent, in particular certain linked structures with arbitrary in degree for which no such methods are known. Persistent data structures are useful in numerous areas, including computational geometry, the implementation of very high level languages, and text editing.