AF: Small: Graphs and structures for distance estimation

网络中距离的计算和估计是网络分析中最基本、最基本的任务之一。然而，存储图中每一对节点之间的距离是不可行的，特别是对于今天的“大数据”。已经开发出图形的小草图，以便可以从草图中检索到对任意成对距离的良好估计。这个项目旨在推动这类素描的艺术水平。主要的研究对象是扳手、距离先知及其容错变体。扳手是一种稀疏子图，它不会将原始图的任何距离拉伸太多。距离预言是一种空间使用量很小的数据结构，能够有效地回答(近似)距离查询。扳手和距离预言都压缩了距离信息。它们之间的主要区别是，人们仍然可以在扳手上运行图形算法，但不能在距离预言上运行，而人们可以立即获得距离距离的任何距离，但在扳手中，人们必须实际计算它。实际上，网络本质上是动态的。为了解决这个问题，图形草图将不得不容忍错误，即边和顶点的删除。有一些容错版本的扳手和距离预言--这些结构估计任何给定(通常是固定大小)的故障边或结点子集的距离。该项目将提供建造新的低空间扳手和先知的算法，并改进保证，并将努力开发新的容错和距离估计技术。Spanner和距离预言有许多应用，例如用于距离计算、网络路由和模拟非同步网络中的同步协议的并行和分布式算法。更好地理解沿短路径的网络路由可以指导下一代互联网协议的设计。这项研究也与度量嵌入领域密切相关，因此超出了计算机科学的严格边界。这项研究的材料将被整合到本科生和研究生的核心课程中，并将导致这一主题的新课程的开发。课堂讲稿和项目材料将在课程网站上向公众提供。

Distance computation and estimation in networks is one of the most basic and fundamental tasks in network analysis. However, storing the distance between every pair of nodes of a graph is infeasible, especially for today's "big data." Small sketches of a graph have been developed so that a good estimate of any pairwise distance can be retrieved from the sketch. This project aims to advance the state-of-the art of such sketches. The main objects of study are spanners, distance oracles and their fault-tolerant variants. A spanner is a sparse subgraph that does not stretch any distance of the original graph by much.  A distance oracle is a data structure that has small space usage and is capable of answering (approximate) distance queries efficiently. Both spanners and distance oracles compress the distance information. The main difference between them is that one can still run graph algorithms on a spanner, but not on a distance oracle, whereas one can obtain any distance from a distance oracle instantly, but in a spanner one would have to actually compute it.In practice, networks are dynamic in nature. To address this, graph sketches would have to tolerate faults, i.e. edge and vertex deletions. There are fault-tolerant versions of spanners and distance oracles-- these structures estimate distances for any given (typically fixed size) subset of failed edges or nodes. This project will provide algorithms for constructing new low-space spanners and oracles with improved guarantees and will strive to develop new techniques for fault-tolerance and distance estimation in general. Spanners and distance oracles have many applications, e.g. in parallel and distributed algorithms for distance computation, network routing, and simulating synchronized protocols in unsynchronized networks. A better understanding of network routing along short paths could guide the design of next-generation Internet protocols. The research is also closely tied to the field of metric embedding, and thus extends beyond the strict boundaries of computer science. Material from this research will be integrated into core undergraduate and graduate courses, and will lead to the development of new courses on the topic. The lecture notes and project materials will be available on the course website for the general public.