Sampling on the Fly From Massive Data

在现代应用中需要解决的问题的规模已经大大增加。因此，对存储在主内存中的(小)数据子集进行采样并进行详细处理是对整个数据进行计算的一种自然选择。该项目解决的问题是，对于许多以约束满足问题为名的优化问题，从样本中得到的答案与整个问题的答案有多接近。该项目还考虑了输入数据由矩阵或更高维数组组成的问题。在这里，自适应抽样(其中抽样一段数据的概率取决于它的相对重要性)最近被PI和其他人成功地使用。现有的结果还有待改进。自适应抽样要求对数据进行多次采样。该项目将研究计算模型，其中传球次数是作为一项重要资源来衡量的。该提案的第三部分是继续PI的快速混合马尔可夫链的研究，通过开发新的通用技术和应用于特定的问题，如计算凸集的体积。广泛的影响：由于通过抽样处理海量数据在现代计算中非常重要，因此这项研究有望取得进展。该协会在耶鲁大学教授专业课程，希望通过这些课程将研究成果传播给学生。

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.