The need to efficiently store and access data is central to modern computing, and the design and analysis of methods to store and access data constitutes the field of data structures. This project will investigate the discovery of provably best data structures for several fundamental problems, including the dictionary and the priority queue. The dictionary supports the efficient insertion, deletion, and search of ordered data. The priority queue supports insertion and the removal of the minimum element.

Data structures will be designed and analyzed under the paradigm of instance-based optimality. In this model, a data structure's performance on a sequence of operations is evaluated based on how well it compares to the speed of the best structure for that sequence among a naturally-defined class of structures. The classes of structures that will be examined include binary search trees and heaps. Binary search trees and heaps are arguably the most fundamental nontrivial classes of data structures in computer science. Despite their origins at the dawn of computing, a complete understanding of these classes of structures has remained elusive to this day.

Other operations on fundamental data structures will be investigated. The ability to decrease the value of an item in a heap is vital to some algorithms, notably Dijkstra's algorithm for finding single-source shortest paths in a graph. Yet, it is not completely understood what types of structures can support this operation efficiently. Also, there is no known efficient method to support the splitting and merging of dictionaries; one goal of this project is to design a comparison-based dictionary do this in amortized logarithmic time.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1018370
Program Officer
Tracy J. Kimbrel
Project Start
Project End
Budget Start
2010-07-01
Budget End
2014-06-30
Support Year
Fiscal Year
2010
Total Cost
$393,443
Indirect Cost
Name
New York University
Department
Type
DUNS #
City
New York
State
NY
Country
United States
Zip Code
10012