CCF:AF:EAGER Algorithmic Paradigms for Computation on MapReduce

传感技术的快速发展以及在线社交和信息网络的普遍存在，导致需要存储和处理的数据集的规模和数量前所未有地增加。研究人员才刚刚开始应对现代系统产生的数据规模。这为以前所未有的规模设计和实现算法提供了独特的机会，从而带来了独特的挑战。这个项目的重点是为（可以说）大数据的主要计算范式MapReduce及其变体设计算法。尽管它在各行各业得到了广泛的应用，但在为这些系统开发理论模型或为大数据应用中出现的自然优化问题开发算法方面的工作却很少。该项目旨在发展对大规模数据处理的强大理论理解，以及在这些设置中进行算法设计的原则方法。MapReduce类型平台的关键挑战在于，它们合并并修改了几种计算范式的各个方面，例如流和并行计算，这导致了对此类系统建模和开发适用于跨平台的算法设计原则的重大挑战。主要研究者（PI）首先试图定义MapReduce算法的复杂性度量。PI接下来的目标是找到与更经典和广泛研究的模型（如并行随机存取机（PRAM），流式计算和I/O高效计算模型）的联系和区别，寻求发现此过程中的常见算法设计原则和计算限制。通过这个过程，PI将为大数据环境中出现的图论和统计优化问题开发有效的算法，并将为这些问题开发一套实用的实现。 在这个建议中考虑的问题是根本性的，因为它们在理论计算机科学，并行计算和数据库中的长期和历史根源。 计算科学将从这项研究中受益。 其他更广泛的影响包括研究生和本科生在研究和教育方面的培训。

Rapid advances in sensing technologies, as well as the ubiquity of online social and information networks, have led to unprecedented increase in the size and quantity of data sets that need to be stored and processed. Researchers are only beginning to grapple with the scale of data that modern systems generate. This provides a unique opportunity to design and implement algorithms at a scale that wasn't witnessed before, leading to unique challenges. The focus of this project is on designing algorithms for (arguably) the dominant computing paradigm for big data, MapReduce, and its variants. Despite its broad adoption across industries, there is very little work on developing theoretical models for these systems, or developing algorithms for natural optimization problems that arise in big-data applications. This project seeks to develop a strong theoretical understanding of large-scale data processing and a principled approach to algorithm design in these settings. The key challenge with MapReduce-type platforms is that they incorporate and modify aspects from several computing paradigms, such as streaming and parallel computing, which leads to significant challenges in modeling such systems and in developing algorithm design principles that apply across platforms. The principal investigator (PI) first seeks to define complexity measures for MapReduce algorithms. The PI next aims to find connections to and differentiate from more classical and widely studied models such as the Parallel Random Access Machine (PRAM), streaming computation, and I/O-efficient computation models, seeking to discover common algorithm design principles and computational limitations in this process. Via this process, the PI will develop efficient algorithms for classes of graph theoretic and statistical optimization problems that arise in big-data settings, and will also develop a suite of practical implementations for these. The problems considered in this proposal are of fundamental nature, as evinced by their long and historic roots in theoretical computer science, parallel computation, and databases. Computational science will benefit from this research. Other broader impacts include graduate and undergraduate training in research and education.