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.