CAREER: Faster and Smaller Sketches for Bigger Data

点击翻译按钮获取中文摘要

The advent of new sensing and tracking technologies and expansive use of social networks detailing every walk of life have generated enormous new datasets. The difficulty in dealing with new datasets arises from not only the sheer volume but also the speed required for the analysis and the complex and heterogeneous nature of the data. Underlying these challenges is the need for suitable representations of the data that facilitate efficient computation and are sufficiently compact for storage and communication. This project aims to address fundamental gaps in our understanding of these representations (so-called sketches) and develops both new data representations and new algorithms for massive datasets in a holistic fashion. The project builds on techniques from a wide variety of areas including mathematical analysis, information theory, coding theory, combinatorics, and optimization, and enriches the deep connections among them. Undergraduate and graduate students will be trained and equipped with technical tools to work in these areas. The PI and the students involved in the project will also distill new findings into general audience surveys and give talks at workshops in different technical areas for broadest possible dissemination of information.This project aims to study sketching algorithms by focusing on three main thrusts:(a) Study time complexity of sketches in streaming algorithms in both upper and lower bounds.(b) Develop new forms of sketches for distributed environments. The project focuses on sketching for submodular functions, a popular model for machine learning, computer vision, economics, etc. Problems in these applications are modeled as submodular maximization subject to various types of constraints. (c) Study space complexity of linear sketches in sparse recovery with respect to different recovery guarantees.