CAREER: Faster and Smaller Sketches for Bigger Data

新的传感和跟踪技术的出现，以及详细描述各行各业的社交网络的广泛使用，产生了巨大的新数据集。处理新数据集的困难不仅来自于庞大的数据量，还来自于分析所需的速度以及数据的复杂性和异构性。这些挑战的基础是需要合适的数据表示，以促进有效的计算，并且对于存储和通信来说足够紧凑。该项目旨在解决我们对这些表示（所谓的草图）的理解中的根本差距，并以整体的方式为大规模数据集开发新的数据表示和新算法。该项目建立在包括数学分析、信息论、编码理论、组合学和优化在内的广泛领域的技术基础上，并丰富了它们之间的深层联系。本科生和研究生将接受培训，并配备在这些领域工作的技术工具。PI和参与该项目的学生还将把新发现提炼成一般听众调查，并在不同技术领域的讲习班上发表演讲，以尽可能广泛地传播信息。本项目旨在研究速写算法，主要关注三个方面：(a)研究流算法中速写的上界和下界时间复杂度。(b)为分布式环境发展新形式的草图。该项目专注于绘制子模块功能的草图，这是机器学习、计算机视觉、经济学等领域的流行模型。这些应用中的问题被建模为受各种类型约束的子模块最大化。(c)研究不同恢复保证下稀疏恢复线性草图的空间复杂度。

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.