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及其合作者提出的新计算模型。 LCAS是输出超高效的随机算法计算所需的部分。在此项目中，PI旨在将LCA扩展到新的边界，例如误差校正代码，矩阵分析，近似算法。 PI还计划通过应用其他领域的工具和技术来改善先前的结果，例如蒙特卡洛·马尔可夫（Monte Carlo Markov）链条，在线和分布式算法以及本地图形分区。该项目的更广泛影响包括对理论计算机科学和其他计算科学领域的本科生和研究生群体的指导和研究生群体的指导。