AF: Small: Graphs and structures for distance estimation

AF：小：用于距离估计的图形和结构

• 批准号: 1740525
• 负责人: Virginia Williams
• 金额: $ 21.9万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-01-20 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1740525&HistoricalAwards=false
• 关键词: AF; Small; Graphs; structures; distance

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.

网络中的距离计算和估计是网络分析中最基本和最基本的任务之一。但是，存储图的每对节点之间的距离是不可行的，尤其是对于当今的“大数据”。已经开发了图的小草图，以便可以从草图中检索任何成对距离的良好估计。该项目旨在推动此类草图的最新技术。研究的主要对象是跨度，距离甲骨文及其耐断层的变体。扳手是一个稀疏的子图，它不会延伸原始图的任何距离。距离Oracle是一种具有较小空间使用情况的数据结构，并且能够有效地回答（近似）距离查询。跨度和距离甲骨文都会压缩距离信息。它们之间的主要区别在于，一个人仍然可以在扳手上运行图形算法，而在距离甲骨文上不能运行距离，而在距离上可以立即获得距离距离甲骨文的任何距离，但是在扳手中，一个人必须实际对其进行计算。在实践中，网络本质上是动态的。为了解决这个问题，图形草图必须忍受故障，即边缘和顶点删除。跨越跨度和距离甲壳有容忍的版本 - 这些结构估计了任何给定的（通常固定尺寸）的失败边缘或节点子集的距离。该项目将提供算法，用于构建具有改进保证的新的低空跨度和甲壳，并努力开发新技术以进行故障容忍和距离估计。跨度和距离甲骨文有许多应用，例如在非同步网络中的距离计算，网络路由和模拟同步协议的并行和分布式算法中。更好地了解沿短路的网络路由可以指导下一代互联网协议的设计。该研究也与度量嵌入领域紧密相关，因此超出了计算机科学的严格界限。这项研究的材料将纳入核心本科和研究生课程，并将导致有关该主题的新课程的发展。该讲义和项目材料将在课程网站上为公众提供。