Sampling on the Fly From Massive Data

从海量数据中动态采样

• 批准号: 0310805
• 负责人: Ravindran Kannan
• 金额: $ 25万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-05-01 至 2007-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0310805&HistoricalAwards=false
• 关键词: Sampling; Fly; Massive; Data

The sizes of problems that need to be solved in modern applicationshave grown enormously. Sampling to draw a (small) subset of the datato store in main memory and process in detail is thus a naturalalternative to computing on the entire data.The project addresses the questions of how well the answers from asample approximates answers to the full problem for many optimizationproblems that go under the name of Constraint Satisfaction Problems. The project also considers problems where the input data consists ofmatrices or higher dimensional arrays. Here adaptive sampling (wherethe probability of sampling a piece of the data depends on itsrelative importance) has been successfully used by the PI and othersrecently. The existing results are to be improved. Adaptive samplingcalls for making more than one pass through the data. The project willstudy models of computation, where the number of passes is measured asan important resource. This is expected to contribute to thediscussion of models to handle large data.A third part of the proposal is to continue the PI's study of rapidly mixing Markov Chains, bothby developing new general techniques and applying tospecific problems like the computation of volumes ofconvex sets.Broader Impact: The research is expected to have broadimpact since the processing of massive data via sampling is ofenormous importance in modern computing. ThePI teaches specialized courses at Yale and hopes to disseminate the results ofthe research to students through the courses.

在现代应用中需要解决的问题的规模已经大大增加了。抽样来绘制数据的一个（小）子集存储在主存储器中并详细处理，因此是对整个数据进行计算的自然替代方案。该项目解决的问题是，样本的答案在多大程度上近似于许多优化问题的答案，这些问题被称为约束满足问题。该项目还考虑了输入数据由矩阵或高维数组组成的问题。在这里，自适应采样（其中采样数据的概率取决于其相对重要性）最近已被PI和其他人成功地使用。现有的结果有待改进。自适应采样要求对数据进行多次传递。该项目将研究计算模型，其中通过次数是衡量的重要资源。这将有助于讨论处理大数据的模型。提案的第三部分是继续PI对快速混合马尔可夫链的研究，既开发新的通用技术，又将其应用于特定问题，如凸集体积的计算。更广泛的影响：该研究预计将产生广泛的影响，因为通过采样处理大量数据在现代计算中非常重要。该学院在耶鲁大学教授专业课程，并希望通过这些课程向学生传播研究成果。