Rapid advances in sensing technologies and the increasing ubiquity of computing in peoples' lives have led to new opportunities and challenges in the management and analysis of data. Many data sets, such as GPS traces of vehicles, are inherently geometric, while many other kinds of data, such as color histograms of images, are best represented in a geometric space. Therefore, geometric algorithms are needed to handle a variety of problems in data analysis, including computing useful representations, computing maps between data sets, answering queries, and parallel processing of data. This talk will discuss a few of these problems, with an emphasis on the problem of computing maps between data sets.

 

We will discuss two variants of the problem of computing maps between data sets. First, we will describe a near-linear time approximation algorithm for computing dynamic time warping maps between point sequences, a central problem in the analysis of trajectories and other curves. Next, we will describe fast approximation algorithms for computing transportation maps, a widely used method for comparing and relating two distributions. In both cases our goal is to develop simple, fast, hopefully near-linear-time approximation algorithms. We will conclude the talk by briefly discussing recent algorithms for a few other geometric data-analysis problems as well as mentioning some of the directions of future research in this area.