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长期参与算法解决问题的外展活动，重点是使这些活动更容易为代表性不足的群体所接受，并使研究生的参与制度化。这个项目提出要研究的问题，线性系统解算器和图上的优化，是算法设计中研究最多的问题。以前对这些主题的工作导致了许多广泛使用的算法和数据结构。该项目的主要方法是通过图形拉普拉斯矩阵结合数值和组合算法原语的进展，称为设计图形算法的“拉普拉斯范式”。PI和合作者最近和正在进行的工作为涉及图拉普拉斯算子的许多关键问题带来了当前最好的算法，更重要的是，大大拓宽了解决问题的范围。这些结果的一个基本主题是，最强大的工具与中间算法状态一起工作，该项目的重点是使用数据结构中的思想对这种现象进行更深入的研究，这些数据结构也构建和重用中间算法状态。这些研究方向将导致新的算法结构，为静态和动态数据的计算提供改进的工具，并使基于图形和矩阵计算的新应用成为可能。该奖项反映了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

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

Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity

最佳离线动态 2、3 边/顶点连接

• 发表时间: 2019
• 期刊: Proceedings
• 作者: Peng, Richard;Sandlund, Bryce;Sleator, Daniel D
• 通讯作者: Sleator, Daniel D