AF: Medium: Taming Masssive Data with Sub-Linear Algorithms

海量数据集的迅猛增长给数据处理和分析带来了新的挑战。为了科普这种现象，必须开发能够从如此巨大的输入中分析和提取值的次线性时间和次线性空间算法。该项目旨在从统一的角度研究次线性时空算法，利用协同效应，以获得更好的理解，从而导致更快，更节省空间和更广泛适用的算法。拟议的研究有两个核心部分。 第一个组成部分是研究大型数据集的稀疏表示。 稀疏表示对于快速分析和处理数据非常有用。 这个组件本身将有两个部分。首先，它将导致更好地理解来自简洁描述的分布的数据的次线性时间采样算法。 考虑的简洁的描述包括由少量参数定义的那些，如幂律，高斯和直方图分布。其次，它将改善流算法，数据草图，压缩感知和稀疏恢复技术的知识现状。 这样的技术将例如对用于获取和处理图像、音频和网络数据的算法产生影响。第二部分旨在设计新的统计技术，用于理解描述常用结构化对象（如图形）的各种分布量。 本部分的重点将放在估计图形参数的次线性时间和空间算法上。 本项目将在有限资源的情况下，大幅推进算法的算法基础，开发用于分析海量数据集的高效算法。本项目将在有限资源的情况下，大幅推进计算的算法基础。 它将开发高效的算法，用于分析电子商务、健康、网络安全和科学数据收集等不同领域的大量数据集。该项目的更广泛影响是对年轻研究人员（包括代表性不足的群体）的教育和指导。 社区外展活动将向小学生介绍有趣的数学和计算机科学概念。

The rampant growth of massive data sets presents new challenges for data processing and analysis. To cope with this phenomenon, sublinear time and sublinear space algorithms that are capable of analyzing and extracting value from such immense inputs must be developed. This project aims to study sublinear time and space algorithms from a unified perspective, using the synergies in order to gain a better understanding that will lead to faster, space efficient and more widely applicable algorithms.The proposed research has two core components. The first component is the study of sparse representations of large data sets. Sparse representations are useful for quickly analyzing and processing data. This component itself will have two parts. First, it will lead to a better understanding of sublinear time sampling algorithms for data coming from a succinctly described distribution. The succinct descriptions considered include those defined by a small number of parameters, such as power laws, Gaussians, and histogram distributions. Second, it will improve the current state of knowledge of streaming algorithms, data sketching, compressive sensing and sparse recovery techniques. Such techniques will for example have an impact on algorithms for acquiring and processing images, audio and network data. The second component aims to design novel statistical techniques for understanding various distributional quantities describing commonly used structured objects such as graphs. The focus in this component will be on sublinear time and space algorithms that estimate parameters of graphs. This project will significantly advance the algorithmic foundations of algorithms with limited resources, and develop highly efficient algorithms for analyzing massive data sets.This project will significantly advance the algorithmic foundations of computation with limited resources. It will develop highly efficient algorithms for analyzing massive data sets that arise in diverse areas including electronic commerce, health, network security, and scientific data collection.The broader impacts of this project are in the education and mentoring of young researchers including underrepresented groups. Community outreach activities will introduce primary school children to interesting mathematical and computer science ideas.