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

数据结构领域涉及有效表示、操作和回答有关典型的长期数据语料库的查询的数学问题。 几十年来，数据结构已经被用来促进一切，从平凡的簿记任务到重要的高级应用程序，例如分析生物数据、网络搜索和网络路由。 该研究计划的目标是（1）设计和理解代表各种类型度量空间的数据结构的局限性，以及（2）分析和理解自调整（又称自组织）数据结构。 度量是抽象空间和距离直观概念的对象；例如地球上的测地距离、物种之间的进化距离以及 DNA 序列之间的距离。 也许当今最重要的一类指标是那些与网络（例如计算机网络、道路网络或社交网络）中的距离（或延迟或金钱成本）相对应的指标。 现实中所有具有一定物理基础的网络都容易出现拥塞和自发故障，无论是由于良性原因还是协调性破坏。 例子包括网络路由器故障、道路网络堵塞和桥梁倒塌。 这项研究的目的之一是设计通用的度量数据结构，能够在拥塞、拓扑和其他特征波动的情况下回答距离、最短路径和可达性查询。从广义上讲，自调整数据结构是一种能够根据环境自动重组其内部状态以优化其性能的数据结构。 PI 的研究目标是解决几十年来关于自调整数据结构最优性的猜想，并更广泛地应用自调整设计理念。PI 计划改进密歇根大学数据结构的教学方式，并为本科生和研究生的数据结构设计和分析课程开发课程材料。

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.