AF: SMALL: Fundamental Data Structures

高效存储和访问数据的需求是现代计算的核心。 加快基本问题的实际性能不仅限于为用户提供更好的体验;它还涉及更有效地使用计算机资源。更快的算法和数据结构意味着更少的能耗，以及所需的更少的物理计算资源。这个项目将研究发现可证明的最佳数据结构的几个基本问题。 字典、优先队列和压缩存储器阵列是本项目中考虑的三种抽象数据结构。 字典支持有序数据的有效插入、删除和搜索。优先级队列支持插入和删除最小元素。对于二叉搜索树，本文的研究将在寻找动态最优搜索树、证明二叉搜索树的上下界、发明联合收割机组合二叉搜索树的方法以及将分摊的二叉搜索树转化为最坏情况下的二叉搜索树等基础问题上取得实质性进展.在堆的情况下，该项目将分析自然模型中减键操作的性能界限，搜索堆的几何视图，研究动态最优性，并改进配对堆的分析。具有接近最优减键操作的高速缓存无关堆和高效的封装存储器阵列（PMA）结构是许多高速缓存无关算法的两个基本构建块。这个项目将开发在具有特定类型的顺序的序列上表现良好的PMA，并构建一个随机结构，其运行时间超过确定性结构的下限。该项目还将研究入度在指针模型持久性中的作用，并为缓存无关持久性开发通用转换。 数据结构是算法的基础。 改进基础数据结构将对计算实践产生深远而广泛的影响。数据结构的进步是本科生可以访问的，PI将在这项研究中吸引代表性不足的学生。

The need to efficiently store and access data is central to modern computing. Speeding up the actual performance of fundamental problems is not limited to better experience for users; it is also about using computer resources more efficiently. Faster algorithms and data structures mean less energy consumption, and less physical computing resources needed. This project will investigate the discovery of provably best data structures for several fundamental problems. The dictionary, priority queue and packed memory array are three abstract data structures considered in this project. The dictionary supports the efficient insertion, deletion, and search of ordered data. The priority queue supports insertion and the removal of the minimum element. The packed-memory array keeps ordered data in sorted order in a limited amount of space.For binary search trees (BSTs), this research will make substantial progress on many fundamental problems that include finding a dynamically optimal search tree, proving better explicit upper and lower bounds on BSTs, inventing methods to combine BSTs, and transforming amortized BSTs into ones with good worst-case runtimes. In the case of heaps, the project will analyze performance bounds for decrease-key operations in natural models, search for a geometric view of heaps, investigate dynamic optimality, and improve the analysis of pairing heaps. Cache-oblivious heaps with close to optimal decrease-key operations, and efficient packed memory array (PMA) structure are two fundamental building blocks of many cache-oblivious algorithms. This project will develop PMAs that perform well on sequences with certain types of order, and construct a randomized structure whose runtime beats the lower bound for deterministic structures. The project will also examine the role of in-degree in pointer-model persistence and develop general transformations for cache-oblivious persistence. Data structures are foundational for algorithms. Improving fundamental data structures will have profound broader impact on computing practice. Advances in data structures are accessible to undergraduates and the PI will engage under-represented students in this research.