AF: Small: Collaborative Research: Algorithmic and Computational Frontiers of MapReduce for Big Data Analysis

AF：小型：协作研究：用于大数据分析的 MapReduce 算法和计算前沿

• 批准号: 1617653
• 负责人: Sungjin Im
• 金额: $ 24.72万
• 依托单位: University of California - Merced
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617653&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Algorithmic

Modern science and engineering heavily relies on processing massive data sets and the size of the data requires applications to run using distributed computing frameworks. However, many existing methods essential to the applications are not easily adapted to work in distributed settings. This project aims to develop new efficient ways of processing large data sets in widely used distributed computing platforms. The project will reveal new methods for processing diverse and complex data sets of massive size and allow for various applications scale to large inputs. The work has the potential to fundamentally change algorithmic techniques used in distributed computing, helping to shape big data research, the computing industry, and the growing economy reliant on big data analysis. Research outcomes will be integrated with education by writing an extensive survey/tutorial on the core algorithmic ideas used in the new discoveries to make the ideas transparent to the algorithmic developers and practitioners. The PIs will make some of the discovered algorithmic ideas accessible even to undergraduate students, helping them get prepared to cope with algorithmic challenges in distributed computing for large data sets. Special efforts will be made to include women and minorities in advising and mentoring plans.The main goal of the project is to find new ways of unlocking the underlying power of MapReduce, a popular distributed platform, through the development of new algorithmics. The developed algorithms should have provably strong guarantees and demonstrate the effectiveness via empirical experiments. Considering the increasing demand for large data analysis, establishing a solid theoretical MapReduce model and developing new algorithmic ideas will have the potential to establish faster and memory efficient algorithms for distributed computing. The PIs will consider a collection of carefully chosen problems to understand in the MapReduce setting that not only have strong connections to theoretical work but also have the potential for high impact in real world Big Data applications: Clustering, Distributed Dynamic Programming, and Limitations of MapReduce. This will be done in parallel with the attempt to better understand the currently accepted MapReduce models that have been developed and to perhaps further refine them to better connect models with practice.

现代科学和工程在很大程度上依赖于处理大量数据集，并且数据的大小需要使用分布式计算框架运行的应用程序。 但是，许多对应用程序必不可少的现有方法不容易适应分布式设置的工作。该项目旨在开发新的有效方法来处理广泛使用的分布式计算平台中的大型数据集。该项目将揭示用于处理庞大大小的多样化和复杂数据集的新方法，并允许各种应用程序扩展到大型输入。这项工作有可能从根本上改变用于分布式计算的算法技术，有助于塑造大数据研究，计算行业以及依赖大数据分析的不断增长的经济。研究成果将通过撰写有关新发现中使用的核心算法思想的广泛调查/教程，以使这些想法与算法开发人员和从业者透明。 PI将使一些发现的算法想法甚至可以访问本科生，从而帮助他们准备应对大型数据集的分布式计算时应对算法挑战。将要采取特殊努力，包括妇女和少数民族在为计划提供建议和指导计划中。该项目的主要目标是通过开发新算法的开发来找到新的方法来解锁MapReduce的潜在力量，这是一个受欢迎的分布式平台。开发的算法应证明具有强大的保证，并通过经验实验证明了有效性。考虑到对大型数据分析的需求不断增长，建立一个可靠的理论MAPREDUCE模型并开发新的算法思想将有可能建立更快，更快的记忆有效算法来分布式计算。 PI将考虑在MapReduce设置中理解的精心选择的问题的集合，这些问题不仅与理论工作具有牢固的联系，而且还具有在现实世界中的大数据应用中产生高影响的潜力：聚类，分布式动态编程和MapReduce的局限性。这将与尝试更好地理解已开发的当前接受的MapReduce模型的尝试同时完成，并可能进一步完善它们以更好地将模型与练习联系起来。

项目成果

Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution

• DOI: 10.1137/1.9781611975994.170
• 发表时间: 2020-01
• 作者: Sungjin Im;Maryam Shadloo

Online Knapsack with Frequency Predictions

带有频率预测的在线背包

• 发表时间: 2021
• 期刊: Advances in neural information processing systems
• 作者: Im, Sungjin;Kumar, Ravi;Montazer Qaem, Mahshid;Purohit, Manish
• 通讯作者: Purohit, Manish

Instance Optimal Join Size Estimation

实例最佳连接大小估计

• DOI: 10.1016/j.procs.2021.11.019
• 发表时间: 2021
• 期刊: Procedia Computer Science
• 作者: Abo-Khamis, Mahmoud;Im, Sungjin;Moseley, Benjamin;Pruhs, Kirk;Samadian, Alireza
• 通讯作者: Samadian, Alireza

A Relational Gradient Descent Algorithm For Support Vector Machine Training

支持向量机训练的关系梯度下降算法

• DOI: 10.1137/1.9781611976489.8
• 发表时间: 2021
• 期刊: Symposium on Algorithmic Principles of Computer Systems (APOCS
• 作者: Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
• 通讯作者: Samadian, A.

Faster Matchings via Learned Duals

• 发表时间: 2021-07
• 期刊: ArXiv
• 作者: M. Dinitz;Sungjin Im;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii