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

数据结构领域涉及有效地表示、操作和回答关于典型的长期数据语料库的查询的数学问题。几十年来，数据结构被用来促进从普通的簿记任务到重要的高级应用程序（如分析生物数据、web搜索和网络路由）的一切工作。本研究计划的目标是(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.