CAREER: Pushing the Theoretical Limits of Scalable Distributed Algorithms

科学和工程越来越依赖于分析庞大的数据集。处理这些数据集通常需要使用许多机器，例如在云上，这意味着需要重新设计用于数据处理的算法和软件，以有效地使用大量机器。这个项目将为分布式计算模型（又名框架）提供算法技术，比如Spark。这样的框架使程序员能够轻松地将算法部署到数万台机器上，只要算法符合框架的计算限制。所开发的算法原语将成为算法设计者和程序员可以利用的工具，以分析许多机器上的大量数据。这将影响越来越依赖大数据分析的工业、科学和经济。研究成果将与教育相结合，包括在商业分析项目的本科和硕士科学数据分析的最新研究。像Spark和MapReduce这样的大规模分布式框架是处理大型数据集的关键技术。这些系统传统上被用来解决相对简单的问题。最近的研究表明，它们可能对更丰富的应用程序有用。有了这种概念验证的潜力，该项目将发现针对这些框架量身定制的算法技术，以释放其潜在的力量并扩大其适用性。最近开发的计算理论模型将用于驱动算法技术的开发，旨在利用框架的独特功能。新的算法和技术将用于为图形处理、数据挖掘和生物信息学中出现的关键问题提供可扩展的解决方案。具体来说，该项目将开发在大规模图上计算最短路径的算法，生物序列的局部对齐算法和一些可证明可扩展的分层聚类算法。实现这些目标可以影响实践和理论研究，类似于流算法等其他领域的成功。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Science and engineering are becoming more reliant on analyzing data sets that have massive size. Processing these data sets typically requires using many machines, such as on the cloud, meaning that algorithms and software for data processing need to be redesigned to efficiently use a large number of machines. This project will give algorithmic techniques for distributed computing models (aka frameworks) such as Spark. Such a framework enables programmers to easily deploy algorithms on tens to thousands of machines as long as the algorithm fits into the computational restrictions of the framework. The algorithmic primitives developed will be tools that algorithm designers and programmers can leverage to analyze large amounts of data on many machines. This will impact industry, science and the economy that is increasingly reliant on large data analysis. Research outcomes will be integrated with education by including the latest research on data analytics in the undergraduate and master of science in business analytics programs. Massively distributed frameworks such as Spark and MapReduce are a key technology for processing large data sets. These systems have traditionally been used to solve relatively simple problems. Recent investigation has shown they are potentially useful for a richer class of applications. With this potential as a proof-of-concept, this project will discover algorithmic techniques tailored to these frameworks to unlock their underlying power and broaden their applicability. A recently developed theoretical model of computation will be used to drive the development of algorithmic techniques designed to leverage the unique features of the frameworks. The new algorithms and techniques will be used to offer scalable solutions for key problems arising in graph processing, data mining, and bioinformatics. Specifically, the project will develop algorithms to compute shortest paths on massive graphs, algorithms for local alignment of biological sequences and some of the first provably scalable algorithms for hierarchical clustering. Achieving these goals can influence practice and theoretical research similarly to successes in other areas such as streaming algorithms.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.