Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

合作研究：AF：小型：高效大规模并行算法

• 批准号: 2218678
• 负责人: Mohammad Hajiaghayi
• 金额: $ 29.82万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2218678&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Efficient

Modern computing systems have moved beyond single-coresingle-processor devices to more modern multicore processors operatingin networked systems and available in warehouse-scale cloudspopularized by companies such as Amazon or Google. Future advances incomputing power will likely come not mainly from faster devices, butby processing in inherently parallel and distributed environments, andby understanding how to exploit the parallelism inherent in manyalgorithmic problems. Simultaneously, the world has entered the era of``big data'' with large data sets on which previously unthinkablesized problems with great economic and social impact need to besolved. This new parallel, interconnected, big-data world speciallyrequires fundamental research on their algorithms, which are bothparallel and distributed.The algorithms in this project address thisimportant research challenge by building and developing new generalframeworks for massively parallel computation.As the main thrust of this project, the investigators will designfundamental and efficient algorithms for core massively parallelcomputations especially in the practical Massively ParallelComputation (MPC) framework. In particular, they will consider methodsfor reducing the number of rounds in the MPC model as well astradeoffs between rounds, memory, number of machines, andcommunication time. They seek to find new MPC algorithms for basicgraph problems such as connectivity, matching, vertex cover, maximalindependent set, as well as other basic string matching problems suchas suffix trees, edit distance, and longest commonsubsequence. Another focus is dynamic algorithms for massivelyparallel computation, which modify the output efficiently in aparallel/distributed setting based on frequent modifications of theinput and with direct applications in evolving social networks, theWorld Wide Web, road networks, scheduling systems among others. Theinvestigators will augmenting current parallelenvironments/architectures with better data structures andabstractions to allow simplified and fast implementations of thecurrent fundamental algorithms that can be used in practicevia open-source codes. The discoveries in this project will beintegrated into existing and new courses and books about parallelalgorithms, distributed algorithms, and foundations of big data. Thewealth of attractive open problems in these areas will provide bothchallenging research topics and intuitive accessible problems toinspire students to enter research in computer science andmathematics. In particular the project will involve Ph.D. students andpost-docs, undergraduate students, and even high-school students(especially students among minorities and women), many of whom willcontinue their research at other academic institutions and researchcenters, further broadening the impact of this research.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.

现代计算系统已经超越了单台处理器设备，转移到了更现代的多核心处理器上，操作网络系统，并在诸如亚马逊或Google等公司的仓库规模的Cloudspopular中获得。未来的进步不构成能力可能不是主要来自更快的设备，Butby在固有的并行和分布式环境中进行处理，并理解如何利用许多Algorithmic问题固有的并行性。同时，全世界都进入了“ big数据”的时代，其中大量数据集以前不可想象的问题对经济和社会影响进行了巨大的影响，需要解决。这项新的平行，相互联系，大数据世界是对其算法的基础研究，它们都是比较和分布的。该项目中的算法解决了这一重要的研究挑战，通过构建和开发新的拼写器来建立新的拼写器，以进行大规模并行计算，这是该项目的主要推力，这是该项目的主要推力，这些项目将众多算法和有效的算法，并有效地构建了有效的算法。并行计算（MPC）框架。特别是，他们将考虑减少MPC模型中的回合数量的方法，以及在回合，内存，计算机数量和通信时间之间的AstradeOffs。他们试图为基本问题找到新的MPC算法，例如连接性，匹配，顶点封面，最大独立设置，以及其他基本的字符串匹配问题，例如后缀树，编辑距离和最长的CommonSubSequence。另一个重点是用于大规模比较计算的动态算法，它基于输入的频繁修改以及在不断发展的社交网络，世界宽的网络，道路网络，调度系统等方面有效地在Aparallow/Assistate设置中有效地修改输出。评估器将通过更好的数据结构和缩放量来扩大当前的并行环境/架构，以允许简化且快速实现thecurrent基本算法，这些算法可用于实践开源代码代码。该项目中的发现将纳入现有的和新的课程和书籍和书籍，这些课程和书籍以及大数据的基础分布式算法和基础。在这些领域中，有吸引力的开放问题的范围将为启发研究主题和直观的可访问问题，以使学生进入计算机科学和音乐学的研究。特别是该项目将涉及博士学位。学生和职员教育委员会，本科生，甚至是高中生（尤其是少数族裔和女性中的学生），其中许多人将在其他学术机构和研究中心进行研究，进一步扩大了这项研究的影响。这奖反映了NSF的法规任务，并被认为是通过基金会的知识优点和广泛的评估来进行评估，这是值得通过评估来进行评估的。

项目成果

Generalized Stochastic Matching

广义随机匹配

• DOI: 10.1609/aaai.v36i9.21239
• 发表时间: 2022
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Farhadi, Alireza;Gilbert, Jacob;Hajiaghayi, MohammadTaghi
• 通讯作者: Hajiaghayi, MohammadTaghi

Adaptive Massively Parallel Algorithms for Cut Problems

用于解决问题的自适应大规模并行算法

• DOI: 10.1145/3490148.3538576
• 发表时间: 2022
• 期刊: (SPAA
• 作者: Hajiaghayi, MohammadTaghi;Knittel, Marina;Olkowski, Jan;Saleh, Hamed
• 通讯作者: Saleh, Hamed

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

有界树编辑距离的 (n poly(k)) 时间算法

• DOI: 10.1109/focs54457.2022.00071
• 发表时间: 2022
• 期刊: FOCS
• 作者: Das, Debarati;Gilbert, Jacob;Hajiaghayi, MohammadTaghi;Kociumaka, Tomasz;Saha, Barna;Saleh, Hamed
• 通讯作者: Saleh, Hamed

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce

• DOI: 10.1145/3456807
• 发表时间: 2021
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
• 通讯作者: Seddighin, Saeed

Improved communication complexity of fault-tolerant consensus

提高容错共识的通信复杂度

• DOI: 10.1145/3519935.3520078
• 发表时间: 2022
• 期刊: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Hajiaghayi, Mohammad T.;Kowalski, Dariusz R.;Olkowski, Jan
• 通讯作者: Olkowski, Jan