AF: Small: Local Computation Algorithms -- New Directions and Techniques

AF：小：局部计算算法——新方向和技术

• 批准号: 1423034
• 负责人: Ning Xie
• 金额: $ 22.91万
• 依托单位: Florida International University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423034&HistoricalAwards=false
• 关键词: AF; Small; Local; Computation; Algorithms

Processing and analysis of large data sets presents substantial computational challenges. New computational models which distill the essence of computing over massive data sets are needed to address the challenges. "Local computation algorithm" (LCA) is a new computation model proposed by the PI and his collaborators. LCAs are randomized algorithms computing required portion of the output super-efficiently.In this project, the PI aims to extend LCAs to new frontiers such as error correction codes, matrix analysis, approximation algorithms. The PI also plans to improve upon prior results by applying tools and techniques from other fields such as Monte Carlo Markov chains, online and distributed algorithms, and local graph partitioning.The broader impacts of the project include mentoring of undergraduate and graduate students from under-represented groups in theoretical computer science and other computationally-oriented scientific fields.

处理和分析大型数据集提出了大量的计算挑战。为了应对这些挑战，需要新的计算模型，这些模型从海量数据集中提炼出计算的本质。“局部计算算法”（LCA）是PI及其合作者提出的一种新的计算模型。lca是一种随机算法，可以超高效地计算所需的输出部分。在这个项目中，PI的目标是将lca扩展到新的领域，如纠错码，矩阵分析，近似算法。PI还计划通过应用其他领域的工具和技术，如蒙特卡洛马尔可夫链、在线和分布式算法以及局部图分区，来改进先前的结果。该项目更广泛的影响包括指导来自理论计算机科学和其他以计算为导向的科学领域中代表性不足的群体的本科生和研究生。