SPX: Collaborative Research: Moving Towards Secure and Massive Parallel Computing

SPX：协作研究：迈向安全和大规模并行计算

• 批准号: 1822738
• 负责人: Mohammad Hajiaghayi
• 金额: $ 6.83万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1822738&HistoricalAwards=false
• 关键词: SPX; Collaborative; Research; Moving; Towards

Modern computing systems have moved beyond single-core, single-processor devices to more modern multi-core parallel processors operating in networked systems and available in warehouse-scale clouds popularized by industries and the government. This new parallel, interconnected, big-data world requires fundamental research on multiple levels from algorithms to systems and computer architecture. This project seeks to take initial steps in the study of the expansive set of algorithms and systems issues in this important research challenge by building and developing new general frameworks for massive parallel computation, often involving privacy and security, in real-life scenarios. The investigators? long-term goals include two directions. As the first thrust of this effort, the investigators aim to design fundamental and efficient algorithms for massive parallel computations in the practical MapReduce framework, in particular by reducing the number of rounds in this framework. As the second thrust of this effort, the investigators aim to augment current parallel environments and architectures with better data structures and abstractions to develop simplified and fast implementations of fundamental algorithms such that everyone can use them in practice.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.

现代计算系统已经超越了单核单处理器设备，转移到了在网络系统中运行的更现代的多核并行处理器，并在由行业和政府推广的仓库规模云中可用。这个新的平行，相互联系的大数据世界需要对从算法到系统和计算机体系结构的多个层次进行基础研究。该项目试图通过在现实生活中构建和开发新的通用框架来研究这一重要的研究挑战中广泛的算法和系统问题集合中的初步步骤。调查人员？长期目标包括两个方向。 作为这项工作的第一个主旨，研究人员旨在设计基本，有效的算法，以在实际的MapReduce框架中进行大规模平行计算，尤其是通过减少此框架中的回合数量。作为这项工作的第二个主力，调查人员的目标是增强具有更好数据结构和抽象的当前平行环境和架构，以开发基本算法的简化和快速实施，以便每个人都可以在实践中使用它们。这奖反映了NSF的法定任务，并且已经具有法定任务并具有使用基金会的知识分子优点和更广泛的审查标准，被认为值得通过评估来支持。

项目成果

String Matching with Wildcards in the Massively Parallel Computation Model

大规模并行计算模型中通配符的字符串匹配

• DOI: 10.1145/3409964.3461793
• 发表时间: 2021
• 期刊: SPAA'21
• 作者: Hajiaghayi, Mohammad

Scalable Equilibrium Computation in Multi-agent Influence Games on Networks

网络多主体影响博弈中的可扩展均衡计算

• 发表时间: 2021
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Hajiaghayi, Mohammad

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence

• DOI: 10.4230/lipics.icalp.2021.54
• 发表时间: 2021
• 作者: Kuan Cheng;Alireza Farhadi;M. Hajiaghayi;Zhengzhong Jin;Xin Li;Aviad Rubinstein;Saeed Seddighin;Yu Zheng

Fair Allocation of Indivisible Goods: Improvement

• DOI: 10.1287/moor.2020.1096
• 发表时间: 2021-04
• 期刊: Math. Oper. Res.
• 作者: M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami

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