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