Efficient Adaptive Data Structures

• Applicant: Professor Dr. László Kozma
• Subject Area: Theoretical Computer Science
• Term: since 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 430150252

Fundamental data structures are critical components of the modern computing infrastructure, including databases, file systems, web servers; efficient storage and retrieval is crucial in all data-intensive applications. Besides the immediate practical impact, the design and analysis of data structures has revealed a rich mathematical theory, with connections to combinatorics, information theory, algebra, and analysis. Adaptive data structures take advantage of regularities in the input, and can be more efficient than what their worst-case analysis would suggest. Binary search trees and heaps are two well-studied and fundamental classes of data structures, with many applications. Self-adjusting trees and heaps are particularly attractive, due to their simplicity. The most prominent data structure in this family is the splay tree, invented by Sleator and Tarjan in 1985. Splay trees have many known adaptive properties, furthermore, they are conjectured to be instance-optimal (i.e. as good on any input as any dynamic tree, up to a constant factor). This is the famous dynamic optimality conjecture. For heaps, several ingenious designs were proposed throughout the years, and Fibonacci heaps and their variants achieve theoretically optimal amortized running times. Compared to search trees, far less is known about the adaptive properties of heaps. In general, self-adjusting data structures are not fully understood, due to the lack of tools for describing their behavior. The objective of the proposal is to deepen the understanding of adaptive data structures, with focus on self-adjusting binary search trees and heaps. In preliminary work by the PI, his collaborators, and others, several new algorithms, models, and connections between the two families of data structures were introduced. These recent results bring new techniques to the study of self-adjusting data structures and open up new areas for investigation. Some of the topics that we wish to study are the following: (1) The design and analysis of heaps with adaptive properties, and the theoretical limits of adaptivity and efficiency in heaps. (2) The study of the dynamic optimality conjecture, its various corollaries and related questions. (3) The study of possible structure in input to which data structures can adapt, and comparisons of data structures with respect to their adaptive properties. (4) Novel techniques for data structure analysis.

• DFG Programme: Research Grants