AF: SMALL: Fundamental Data Structures

高效存储和访问数据的需求是现代计算的核心。加快基本问题的实际执行，不仅是为了给用户带来更好的体验，也是为了更有效地利用计算机资源。更快的算法和数据结构意味着更少的能源消耗和更少的物理计算资源。这个项目将研究发现几个基本问题的最佳数据结构。字典、优先级队列和分组存储数组是本项目中考虑的三种抽象数据结构。该词典支持高效地插入、删除和搜索有序数据。优先级队列支持最小元素的插入和移除。对于二叉搜索树(BST)，本研究将在许多基本问题上取得实质性进展，包括寻找动态最优的搜索树，证明BST的更好的显式上下界，发明组合BST的方法，以及将分期的BST转换为具有良好最坏运行时间的BST。在堆的情况下，该项目将分析自然模型中减键操作的性能界限，搜索堆的几何视图，研究动态最优化，并改进配对堆的分析。具有接近最佳减键操作的高速缓存无关堆和高效的压缩内存阵列(PMA)结构是许多高速缓存无关算法的两个基本构建块。这个项目将开发在具有某些类型的顺序的序列上表现良好的PMAS，并构建一个运行时间超过确定性结构的下界的随机结构。该项目还将研究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.