RIA: Problems Arising in Persistent Data Structures

RIA：持久数据结构中出现的问题

• 批准号: 8909667
• 负责人: Paul Dietz
• 金额: $ 3.79万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-01 至 1992-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8909667&HistoricalAwards=false
• 关键词: RIA; Problems; Arising; Persistent; Data

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.

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