AF: SMALL: Fundamental Data Structures

高效存储和访问数据的需求是现代计算的核心。提速实际性能的根本问题不局限于为用户提供更好的体验；它还涉及到更有效地利用计算机资源。更快的算法和数据结构意味着更少的能耗和更少的物理计算资源。这个项目将调查几个基本问题的可证明的最佳数据结构的发现。字典、优先队列和打包内存数组是本项目考虑的三种抽象数据结构。字典支持有序数据的高效插入、删除和搜索。优先级队列支持插入和删除最小元素。打包内存数组在有限的空间中按排序顺序保存有序的数据。对于二叉搜索树（BSTs），本研究将在许多基本问题上取得实质性进展，包括寻找动态最优搜索树，证明更好的二叉搜索树的显式上界和下界，发明组合二叉搜索树的方法，以及将平摊二叉搜索树转换为具有良好最差情况运行时间的二叉搜索树。在堆的情况下，该项目将分析自然模型中减少键操作的性能界限，搜索堆的几何视图，研究动态最优性，并改进配对堆的分析。具有接近最优减键操作的缓参无关堆和高效的打包内存数组（PMA）结构是许多缓参无关算法的两个基本组成部分。本项目将开发在具有特定类型顺序的序列上表现良好的pma，并构建一个运行时间优于确定性结构下界的随机结构。该项目还将研究in-degree在指针模型持久化中的作用，并为缓参无关持久化开发通用转换。数据结构是算法的基础。改进基本数据结构将对计算实践产生深远而广泛的影响。本科生可以接触到数据结构方面的进展，而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.