CAREER: Advanced Data Structures for Shortest Paths, Routing, and Self-Adjusting Computation

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

The field of data structures concerns the mathematical problems of efficiently representing, manipulating, and answering queries about a typically long-lived corpus of data. For decades data structures have been used to facilitate everything from mundane bookkeeping tasks to important high-level applications such as analyzing biological data, web search, and routing in networks. The goals of this research program are (1) to design and understand the limits of data structures that represent various types of metric spaces, and (2) to analyze and understand self-adjusting (aka self-organizing) data structures. A metric is an object that abstracts the intuitive notions of space and distance; examples include geodesic distance on a globe, evolutionary distance between species, and the distance between DNA sequences. Perhaps the most important class of metrics today are those that correspond to distance (or latency or monetary cost) in networks, such as computer networks, road networks, or social networks. All networks with some physical basis in reality are prone to congestion and spontaneous failure, whether due to benign causes or coordinated sabotage. Examples include malfunctioning network routers, blockage on road networks, and collapsing bridges. One aim of this research is to design versatile metric data structures that are capable of answering distance, shortest path, and reachability queries in the presence of fluctuations in congestion, topology, and other features. Broadly speaking, a self-adjusting data structure is one that automatically reorganizes its internal state in response to the environment in order to optimize its performance. The PIs research goals are to settle some decades-old conjectures regarding the optimality of self-adjusting data structures and to apply the self-adjusting design philosophy more widely. The PI plans to improve the way data structures are taught at the University of Michigan and to develop curricular materials for undergraduate and graduate courses in the design and analysis of data structures.