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.