AF: Small: Local Computation Algorithms

AF：小：本地计算算法

• 批准号: 1217423
• 负责人: Ronitt Rubinfeld
• 金额: $ 25万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217423&HistoricalAwards=false
• 关键词: AF; Small; Local; Computation; Algorithms

The ubiquitousness of massive data sets presentsgreat challenges. The difficulty of dealing with massive datasets is especially formidable when attempting tosolve computational problems in which both the inputsand the outputs to the computation are large.In such a situation, it would be useful if one could findfaster ways of computing just the portion of the output that is requiredby the user.This project aims to study "local computation algorithms",namely algorithms that quickly compute only the portions of theoutput that are required by the user,without performing the full computation.In particular, local computation algorithmsview only a miniscule portion of the input.The PI considers a broad based approach, studying the application oflocal computation algorithms to a range of problems andsettings within algorithm design.The focus of this research is on the question of when local computationscan be done in time that is sub-linear in the size of the input and output.The proposed research will develop techniques for constructingsuch algorithms and for understanding when such algorithms arenot possible.The project will leverage known results from sub-linear timealgorithms, which for the most part have focused on the somewhatdifferent setting of computationalproblems in which the inputs are large but the outputs are small.In addition, the project will investigate well-studiedclasses of algorithmic techniques and focus on modifying them foruse in this new setting. Such classes include algorithmic techniquesfirst developed for parallel and distributed algorithms, as well as theextensively used greedy method.Problems from combinatorial optimization, graph theory and compressibilityof strings will be studied.

大规模数据集的无处不在提出了挑战。 在尝试解决计算问题时，处理大规模数据集的困难尤其令人难以置信，在这些问题中，输入和计算的输出都很大。通过用户，不执行完整的计算。特别是，本地计算算法浏览仅一部分输入的部分。PI考虑了一种基于广泛的方法，研究了局部计算算法的应用到算法设计中的一系列问题和设置对本地研究的重点。在当地的问题上，该问题的范围是按时间限制的。研究将开发用于构造算法的技术，并了解何时可能发生这种算法。该项目将利用次线性timealgorithms的已知结果，在大多数情况下，这些结果集中在计算问题的某种情况下，这些计算问题的设置很大，但这些输出很大，但这些项目却很小。在这个新环境中进行福特。 这样的类包括针对并联和分布式算法开发的算法技术，以及将研究的远程算法。

项目成果

Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling

通过边缘采样计算星子图的次线性时间算法

• DOI: 10.1007/s00453-017-0287-3
• 发表时间: 2018
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Aliakbarpour, Maryam;Biswas, Amartya Shankha;Gouleakis, Themis;Peebles, John;Rubinfeld, Ronitt;Yodpinyanee, Anak
• 通讯作者: Yodpinyanee, Anak