CAREER: Pushing the Theoretical Limits of Scalable Distributed Algorithms

职业：突破可扩展分布式算法的理论极限

• 批准号: 1845146
• 负责人: Benjamin Moseley
• 金额: $ 50万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845146&HistoricalAwards=false
• 关键词: CAREER; Pushing; Theoretical; Limits; Scalable

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.

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

项目成果

Predictive Flows for Faster Ford-Fulkerson

• DOI: 10.48550/arxiv.2303.00837
• 发表时间: 2023-03
• 作者: Sami Davies;Benjamin Moseley;Sergei Vassilvitskii;Yuyan Wang

A Framework for Parallelizing Hierarchical Clustering Methods

• DOI: 10.1007/978-3-030-46150-8_5
• 发表时间: 2019-09
• 作者: Silvio Lattanzi;Thomas Lavastida;Kefu Lu;Benjamin Moseley

Practically Efficient Scheduler for Minimizing Average Flow Time of Parallel Jobs

实用高效的调度程序，可最大限度地减少并行作业的平均流程时间

• DOI: 10.1109/ipdps.2019.00024
• 发表时间: 2019
• 期刊: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS
• 作者: Agrawal, Kunal;Lee, I-Ting Angelina;Li, Jing;Lu, Kefu;Moseley, Benjamin
• 通讯作者: Moseley, Benjamin

An Approximation Algorithm for the Matrix Tree Multiplication Problem

• DOI: 10.4230/lipics.mfcs.2021.6
• 发表时间: 2021
• 作者: Mahmoud Abo Khamis;Ryan R. Curtin;Sungjin Im;Benjamin Moseley;H. Ngo;K. Pruhs;Alireza Samadian

Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks

• DOI: 10.1109/infocom41043.2020.9155537
• 发表时间: 2020-01
• 期刊: IEEE INFOCOM 2020 - IEEE Conference on Computer Communications
• 作者: M. Dinitz;Benjamin Moseley