CAREER: New Directions for Sketching and Stream Computation

各种技术趋势，如更快的网络，更便宜的数据存储和无处不在的数据记录，使我们能够访问大量的数据。 如果我们要利用这些数据，这就产生了两个需要解决的基本问题：（a）如何处理这些数据？ 在监控Gbps网络流量、挖掘PB级搜索引擎数据或处理分布在多个低功耗传感器上的数据时，需要重新考虑传统的计算模型和效率概念。(b)如何计算这些数据？ 通常，最快积累的数据是嘈杂的、受内部不一致性困扰的或冗余的数据。如何从这些数据中提取有用的信息？在过去的十年中，草图（一种基于线性投影的压缩形式）和流计算（空间有限的计算，其中输入被顺序处理）的研究试图解决上述问题的各个方面。 该项目的研究目标是为这些计算模型开创和追求各种新的方向。 其中包括（a）通过寻求问题易处理性的广泛特征和开发解决整个相关问题系列的“超级概要”，对现有模型中的计算有更系统的理解。 (b)扩展和定制现有模型，以解决更广泛的应用，如处理随机生成的数据。 (c)建立一个通用的和智力上有趣的抽象计算的挑战与大量的数据集，包括素描和流计算。在这些研究目标相结合，该项目包括各种教育和更广泛的影响倡议，旨在确保研究成果的广泛传播，并培养研究生和本科生。

Various technological trends, such as faster networks, cheaper data storage, and ubiquitous data logging, have given us access to massive amounts of data. This gives rise to two fundamental questions that need to be addressed if we are to exploit this data: (a) How to process such data? Traditional models of computation and notions of efficiency need to be reconsidered when monitoring Gbps network traffic, mining petabytes of search engine data, or processing data that is distributed across multiple low-power sensors. (b) What to compute about such data? Often the data that is quickest to accumulate is data that is noisy, plagued by internal inconsistencies, or redundant. How can useful information be extracted from such data? Over the last decade, the study of sketching (a form of compression based on linear projection) and stream computation (space-bounded computation where the input is processed sequentially) has sought to address aspects of the above questions. The research goal of this project is to initiate and pursue a variety of new directions for these computational models. These include (a) Developing a more systematic understanding of computation in the existing models by seeking broad characterizations of problem tractability and developing "super synopses" that solve entire families of related problems. (b) Extending and tailoring existing models in order to address a wider range of applications such as processing stochastically generated data. (c) Establishing a general and intellectually intriguing abstraction of the challenges of computing with massive data sets that subsumes sketching and stream computation.In conjunction with these research goals, the project includes various educational and broader impact initiatives that are designed to ensure a wide dissemination of research results and to train graduate and undergraduate students.