Algorithms for Multi-Dimensional Data via Sketches.
Massive geometric data is increasingly common thanks to the proliferation of ubiquitous data-collecting devices, presenting vexing challenges for algorithmic processing. Our approach to deal with this amount of data is to, given an approximation parameter eps, construct a small-sized sketch S of the input data, then solve the problem on S, and finally extend this solution to a (1+eps)-approximation to the original problem. Our research is divided into three parts, requiring expertise in statistics, computational geometry, learning, combinatorics, and algorithms. First, we consider the combinatorial properties of geometric data that are relevant to build compact sketches. Second, we consider the time and space complexities of constructing accurate sketches of data in high dimensions, based on the combinatorial and geometric understanding. Finally, we show how to use the small sketches in order to improve the accuracy and running time of optimization algorithms.