AF: Small: Collaborative Research: Algorithmic and Computational Frontiers of MapReduce for Big Data Analysis

现代科学和工程在很大程度上依赖于处理大量数据集，数据的大小要求应用程序使用分布式计算框架运行。 然而，许多现有的方法必不可少的应用程序不容易适应分布式环境中工作。该项目旨在开发在广泛使用的分布式计算平台上处理大型数据集的新的有效方法。该项目将揭示处理各种复杂的大规模数据集的新方法，并允许各种应用程序扩展到大输入。这项工作有可能从根本上改变分布式计算中使用的算法技术，帮助塑造大数据研究，计算行业以及依赖大数据分析的不断增长的经济。研究成果将通过编写关于新发现中使用的核心算法思想的广泛调查/教程与教育相结合，以使算法开发人员和从业者对这些思想透明。PI将使一些发现的算法思想甚至对本科生也可以访问，帮助他们准备科普大型数据集分布式计算中的算法挑战。将作出特别努力，将妇女和少数民族纳入咨询和指导计划，该项目的主要目标是通过开发新算法，找到释放MapReduce这一流行分布式平台潜在力量的新方法。所开发的算法应具有可证明的强保证，并通过实证实验证明其有效性。考虑到大数据分析需求的不断增长，建立一个坚实的理论MapReduce模型并开发新的算法思想将有可能为分布式计算建立更快和内存效率更高的算法。PI将考虑在MapReduce设置中仔细选择的问题的集合，这些问题不仅与理论工作有很强的联系，而且在真实的世界大数据应用中具有潜在的高影响力：集群，分布式动态编程和MapReduce的局限性。这将与更好地理解目前已开发的被接受的MapReduce模型的尝试同时进行，并可能进一步完善它们，以更好地将模型与实践联系起来。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern science and engineering heavily relies on processing massive data sets and the size of the data requires applications to run using distributed computing frameworks. However, many existing methods essential to the applications are not easily adapted to work in distributed settings. This project aims to develop new efficient ways of processing large data sets in widely used distributed computing platforms. The project will reveal new methods for processing diverse and complex data sets of massive size and allow for various applications scale to large inputs. The work has the potential to fundamentally change algorithmic techniques used in distributed computing, helping to shape big data research, the computing industry, and the growing economy reliant on big data analysis. Research outcomes will be integrated with education by writing an extensive survey/tutorial on the core algorithmic ideas used in the new discoveries to make the ideas transparent to the algorithmic developers and practitioners. The PIs will make some of the discovered algorithmic ideas accessible even to undergraduate students, helping them get prepared to cope with algorithmic challenges in distributed computing for large data sets. Special efforts will be made to include women and minorities in advising and mentoring plans.The main goal of the project is to find new ways of unlocking the underlying power of MapReduce, a popular distributed platform, through the development of new algorithmics. The developed algorithms should have provably strong guarantees and demonstrate the effectiveness via empirical experiments. Considering the increasing demand for large data analysis, establishing a solid theoretical MapReduce model and developing new algorithmic ideas will have the potential to establish faster and memory efficient algorithms for distributed computing. The PIs will consider a collection of carefully chosen problems to understand in the MapReduce setting that not only have strong connections to theoretical work but also have the potential for high impact in real world Big Data applications: Clustering, Distributed Dynamic Programming, and Limitations of MapReduce. This will be done in parallel with the attempt to better understand the currently accepted MapReduce models that have been developed and to perhaps further refine them to better connect models with practice.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.