CAREER: Scalable Algorithmic Primitives for Data Science

职业：数据科学的可扩展算法原语

• 批准号: 1846218
• 负责人: Yang Peng
• 金额: $ 45.65万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1846218&HistoricalAwards=false
• 关键词: CAREER; Scalable; Algorithmic; Primitives; Data

This project aims to improve some of the most fundamental algorithms in computing: solving systems of linear equations, optimization on graphs, and maintaining dynamically changing networks. Tools for solving these problems are integral components of high-level programming languages such as MATLAB and Julia, and are frequently taught as basic programming constructs in courses on machine learning, statistics, and data science. Improved algorithms for these problems can provide faster, more robust, and easier-to-use algorithmic primitives, which would in turn enable computing on larger and more diverse data sets in areas such as data mining, image processing, scientific computing, and network science. The proposed works will actively involve graduate students, and their results will be incorporated into courses at both graduate and undergraduate levels. The project will also support the PI's long-time involvement with algorithmic problem-solving outreach activities, with a focus on making these activities more accessible to underrepresented groups, and institutionalizing the involvement of graduate students. The problems that this project proposes to study, linear system solvers and optimization on graphs, are some of the most well-studied problems in algorithm design. Previous work on these topics led to many widely-used algorithms and data structures. The main approach of this project is motivated by progress on combining numerical and combinatorial algorithmic primitives through the graph Laplacian matrix, known as the `Laplacian paradigm' for designing graph algorithms. Recent and ongoing work by the PI and collaborators led to the current best algorithms for many key problems involving graph Laplacians, and more importantly, significantly broadened the scope of problems addressed. An underlying theme in these results is that the most powerful tools work with intermediate algorithmic states, and the focus of this project is a more in-depth study of this phenomenon using ideas from data structures, which also construct and reuse intermediate algorithmic states. These directions of investigation will lead to new algorithmic constructs, give improved tools for computing on static and dynamic data, and enable new applications based on computations on graphs and matrices.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.

该项目旨在改善计算中一些最基本的算法：求解线性方程的系统，图表上的优化以及维护动态变化的网络。解决这些问题的工具是高级编程语言（例如Matlab和Julia）的组成部分，并且经常被教授为机器学习，统计和数据科学课程中的基本编程结构。这些问题的改进算法可以提供更快，更强大且易于使用的算法原始算法，这反过来又可以在数据挖掘，图像处理，科学计算和网络科学等领域的更大和更多样化的数据集上进行计算。拟议的作品将积极参与研究生，其结果将纳入研究生和本科级别的课程中。该项目还将支持PI的长期参与算法解决问题的外展活动，重点是使这些活动更容易被代表性不足的团体访问，并将研究生的参与制度化。该项目提出的研究，在图形上进行线性系统求解器和优化的问题是算法设计中一些最有研究的问题。这些主题的先前工作导致许多广泛使用的算法和数据结构。该项目的主要方法是由通过图拉普拉斯矩阵（称为“ laplacian范式”设计图形算法的“ laplacian范式”组合数字和组合算法基原始的进步。 PI和合作者的最新工作和正在进行的工作导致了许多涉及图形Laplacians的关键问题的最佳算法，更重要的是，显着扩大了所解决的问题范围。这些结果中的一个基本主题是，最强大的工具与中间算法状态一起使用，并且该项目的重点是对这种现象的更深入的研究，它使用数据结构中的思想来构建和重复使用中间算法状态。这些调查方向将导致新的算法结构，提供改进的计算静态和动态数据的工具，并基于图形和矩阵的计算来启用新的应用程序。该奖项反映了NSF的法定任务，并被认为是通过基金会的智力和宽广的影响来评估通过评估的支持，并被认为是值得的。

项目成果

Minor Sparsifiers and the Distributed Laplacian Paradigm

小稀疏器和分布式拉普拉斯范式

• DOI: 10.1109/focs52979.2021.00099
• 发表时间: 2022
• 期刊: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Forster, Sebastian;Goranci, Gramoz;Liu, Yang P.;Peng, Richard;Sun, Xiaorui;Ye, Mingquan
• 通讯作者: Ye, Mingquan

Flowless: Extracting Densest Subgraphs Without Flow Computations

• DOI: 10.1145/3366423.3380140
• 发表时间: 2019-10
• 期刊: Proceedings of The Web Conference 2020
• 作者: Digvijay Boob;Yu Gao;Richard Peng;Saurabh Sawlani;Charalampos E. Tsourakakis;Di Wang;Junxing Wang

Vertex Sparsification for Edge Connectivity

• DOI: 10.1137/1.9781611976465.74
• 发表时间: 2020-07
• 作者: Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Yunbum Kook;Yang P. Liu;Richard Peng;Mark Sellke-Mark-Sell

Solving Sparse Linear Systems Faster than Matrix Multiplication

比矩阵乘法更快地求解稀疏线性系统

• DOI: 10.1137/1.9781611976465.31
• 发表时间: 2021
• 作者: Peng, Richard;Vempala, Santosh S.
• 通讯作者: Vempala, Santosh S.

Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds

• DOI: 10.1137/1.9781611975994.79
• 发表时间: 2019-08
• 期刊: ArXiv
• 作者: D. Durfee;Laxman Dhulipala;Janardhan Kulkarni;Richard Peng;Saurabh Sawlani;Xiaorui Sun