CAREER: Efficient Distance Sketching on Graphs with Geometric Structures

Distance computation and estimation are among the simplest tasks performed daily by billions of humans and machines worldwide. They are also crucial steps in various optimization algorithms including routing, network design, and information clustering. Compared to distances between higher-dimensional data in abstract spaces, distances in real-life networks possess additional structures which often lead to extremely efficient algorithms that are impossible to achieve otherwise. This project aims to develop novel methods to represent, compress, and sketch distances on networks when geometry is present. This is a timely response to the ever-growing need to summarize massive geometric data. By focusing on simple and practical algorithmic solutions, the project provides a useful toolbox for algorithm designers, addressing important open questions at the frontier of human knowledge. In addition, the integrated education and mentoring plan sets the goal to enhance mathematical literacy and critical thinking skills among local college and high-school students in the New Hampshire and Vermont area. Geometric constraints on graph metrics arise from the interaction between the graph and its ambient space that often comes with simple topological or Euclidean structures. The project focuses on various types of geometric metrics, such as planar distances, p-norms (i.e., a norm on suitable real vector spaces given by the pth root of the sum – or integral – of the pth-powers of the absolute values of the vector components) and their generalizations, and hop distances on geometric shapes. These metrics are common in applications like computer graphics, vehicle routing, and shape analysis, and they also appear implicitly in string editing in bioinformatics and configuration spaces in robotics. The main theme is to design a robust and versatile distance sketching toolbox using geometry, with a tradeoff option between accuracy and efficiency, while remaining lightweight in resource usage. The techniques are involved and rely on the interplay between different research fields, such as metric embeddings, topological graph theory, and geometric algorithms, aiming to study optimization from a graph partitioning perspective. These tools will then be used to tackle problems where current algorithmic solutions are inefficient, inaccurate, or nonexistent. The long-term goal is to provide a systematic way to examine distance-related problems, choose the most effective tools, and estimate resource usage before implementation. This project is jointly funded by Algorithmic Foundations program and the Established Program to Stimulate Competitive Research (EPSCoR). 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.