AF: SMALL: Fundamental Data Structures

New York University, New York NY

Investigators

Abstract

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.