NSF-BSF: AF: Small: New Frontiers in Distance Sketching

Modern datasets are massive, posing a serious challenge to processing and storage. A principled approach for dealing with massive (metric) data is distance sketching. A distance sketch of a metric space (or a graph) is a compact structure that approximately preserves the distances between every pair of points (or vertices). The two most basic compactness measures are the size (i.e., the number of edges) and weight (i.e., the total edge weights) of the sketch. The compactness makes distance sketching a powerful primitive for countless algorithmic tasks. The most basic distance sketch is a spanner, a graph preserving all pairwise distances. Spanners have found many applications over the years, for example, in wireless and sensor networks and distributed computing. Despite its compactness, the structure of a spanner could still be too complex for a wide range of applications. Two other important structural sketches include tree cover and locality-sensitive ordering, composed of a few trees and paths, respectively. Trees and paths are arguably the simplest types of graphs, and hence, structural distance sketches open up a much broader range of applications. The results in this project will impact applications such navigation maps and routing on wireless networks. The project will also train undergraduate and graduate students. This project proposes to study three research directions to expand the understanding of distance sketching on three fronts. First, the project aims to design new algorithms for constructing instance-optimal spanners, which are optimal with respect to every input instance. In contrast, known constructions of distance sketches are only optimal existentially. Second, the project will study spanning tree covers and locality-sensitive orderings, aiming to achieve the same theoretical guarantees of spanners; existing constructions of tree covers and locality-sensitive orderings are inferior to spanners despite their superior structural simplicity. Third, the project seeks to design new algorithms for efficiently constructing distance sketches in different models of computation; many state-of-the-art constructions are very slow, even in the most basic models of computation, including the static or dynamic settings. The techniques expected to develop in this proposal revolve around several different areas: graph theory, discrete geometry, dynamic algorithms, and approximation algorithms, and therefore, this project will potentially impact these areas as well. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.