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

AF：中：用次线性算法驯服海量数据

• 批准号: 1065125
• 负责人: Ronitt Rubinfeld
• 金额: $ 116.09万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-03-01 至 2016-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1065125&HistoricalAwards=false
• 关键词: AF; Medium; Taming; Masssive; Data

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.

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