AF: Small: New directions in the design of local computation algorithms

AF：小：局部计算算法设计的新方向

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

Dealing with big data is formidable when attempting to solve computations in which both the inputs and outputs are large. Nonetheless, frequently it is the case that only small parts of the solution are needed at any stage. Local computation algorithms were recently introduced in order to allow a user to quickly access the portions of the output that are required, without performing the full computation. The aim of local computation algorithms is to provide useful answers to the user in a manner that is significantly faster than what is required even for the simple task of viewing the whole input or output.The proposed research will expand the scope of local computation algorithms to allow such fast processing for new problems from combinatorial optimization. One class of local computation algorithms that will be studied are those that provide query access to a sparse subgraph of the input graph which preserves connectivity and distance properties of the original graph. A second class of local computation algorithms "clean up" data to have certain desirable properties, such as graph connectivity. New techniques will be developed to approach basic computational problems that can be used as tools in solving a wide array of other problems.The broader impacts of this project are in the education and mentoring of young researchers. The PI will engage in Computer Science Unplugged activities at local elementary schools. The PI will work actively to ensure greater participation of women and minority students in the project. Material from sub-linear time algorithms will be integrated into undergraduate and graduate algorithms courses.

当尝试求解输入和输出都大的计算时，处理大数据是可实现的。但是，通常情况下，任何阶段都只需要溶液的一小部分。最近引入了本地计算算法，以允许用户快速访问所需的输出部分，而无需执行完整的计算。本地计算算法的目的是，即使在查看整个输入或输出的简单任务中，该方式也要以明显快的速度为用户提供有用的答案。拟议的研究将扩大本地计算算法的范围，从而从组合优化中允许对新问题进行此类快速处理。将研究的一类本地计算算法是提供对输入图的稀疏子图的查询访问的算法，该算法可保留原始图的连接性和距离属性。第二类本地计算算法“清理”数据具有某些理想的属性，例如图形连接。将开发新技术来解决基本的计算问题，这些问题可以用作解决各种其他问题的工具。该项目的更广泛影响在于年轻研究人员的教育和指导。 PI将在当地小学从事计算机科学插电活动。 PI将积极努力，以确保妇女和少数族裔学生在项目中的更多参与。亚线性时间算法的材料将集成到本科和研究生算法课程中。