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

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

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.