AF: Small: Scalable Algorithms for Data and Network Analysis
AF:小型:用于数据和网络分析的可扩展算法
基本信息
- 批准号:1815254
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-06-01 至 2022-05-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Data-based decision-making involving big input data sets require a lot of time for algorithms to process them. In computer science, efficient algorithms are generally considered to be the ones whose running time does not increase "too fast" when input size grows. "Scalable algorithms" are among the most efficient algorithms, because their running time is required to be nearly linear or even sub-linear with respect to the problem size. In other words, their complexity scales gracefully when the input size scales up. In the age of Big Data, efficient algorithms are in higher demand now more than ever before. While big data takes us into the asymptotic world envisioned by the pioneers of computer science, the explosive growth of problem size has also significantly challenged the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to the traditional polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. Thus, scalability, instead of polynomial-time computability, should be elevated to the central complexity notion for characterizing efficient computation, and this will be the focus of algorithm design for network sciences and big data. This project will focus on the design and analysis of scalable algorithms. One of its primary objective is to build bridges between the area of algorithm design and the fields of network sciences and machine learning. If successful, the project will help to provide a rigorous algorithmic framework for designing new scalable data and network analysis algorithms. By focusing on notions of algorithmic efficiency --- such as scalability --- that respect the sensibilities of researchers in these disciplines as to what constitutes a practical algorithm in the age of big data, this project aims to increase the value of theoretical analyses to researchers in these fields. As this project combines ideas from many disciplines within one coherent research effort, lectures and tutorials presented on the fruits of the project will help cross-fertilize the disciplines within its scope. The development of theoretical algorithms that might have practical applicability should simplify education in algorithms for students beyond theoretical computer science, and allow discussion of practically important heuristics at early stages of computer science education. The interdisciplinary nature of this research will enable broader engagements with PhD students and researchers in network sciences, machine learning, numerical analysis, and social science and hence will enhance the chance to be successful in supporting and working with women and minority researchers.The technical goal of this project is to systematically extend the family of algebraic, numerical, and combinatorial techniques from the recent breakthroughs in Laplacian linear solvers and max-flows/min-cuts, to a wide-range of problems that arise in network analysis, data mining, and machine learning. This project aims to show that these techniques --- including advanced sampling, sparsification, and local exploration of networks --- will play increasing roles in improving algorithmic scalability. It contains several open questions and conjectures ranging from network analysis to distribution sampling to social influences towards this goal. By providing new algorithmic insights into various dynamic processes over graphs, the project also aims to improve the understanding of network facets beyond static graph structures in order to develop better algorithmic theory for network sciences.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.
基于数据的决策涉及大量的输入数据集,需要大量的时间来处理它们。在计算机科学中,高效算法通常被认为是当输入大小增加时,其运行时间不会“过快”增长的算法。“可扩展算法”是最有效的算法之一,因为它们的运行时间要求相对于问题大小是接近线性甚至亚线性的。换句话说,当输入大小增加时,它们的复杂度也会优雅地增加。在大数据时代,对高效算法的需求比以往任何时候都高。虽然大数据将我们带入了计算机科学先驱所设想的渐近世界,但问题规模的爆炸性增长也极大地挑战了高效算法的经典概念:根据传统的多项式时间表征,过去被认为是高效的算法可能不再足以解决今天的问题。高效的算法应该具有可扩展性,这不仅是可取的,而且是必要的。因此,可扩展性,而不是多项式时间可计算性,应该被提升到表征高效计算的核心复杂性概念,这将是网络科学和大数据算法设计的重点。该项目将侧重于可扩展算法的设计和分析。其主要目标之一是在算法设计领域与网络科学和机器学习领域之间建立桥梁。如果成功,该项目将有助于为设计新的可扩展数据和网络分析算法提供严格的算法框架。通过关注算法效率(如可扩展性)的概念,尊重这些学科的研究人员对大数据时代实用算法构成的敏感性,该项目旨在增加理论分析对这些领域研究人员的价值。由于这个项目在一个连贯的研究工作中结合了许多学科的想法,关于项目成果的讲座和教程将有助于在其范围内交叉施肥。可能具有实际适用性的理论算法的发展应该简化学生在理论计算机科学之外的算法教育,并允许在计算机科学教育的早期阶段讨论实际重要的启发式。这项研究的跨学科性质将使网络科学、机器学习、数值分析和社会科学领域的博士生和研究人员能够更广泛地参与其中,因此将增加成功支持女性和少数民族研究人员并与之合作的机会。该项目的技术目标是系统地扩展代数,数值和组合技术家族,从最近在拉普拉斯线性求解和最大流量/最小切割方面的突破,到网络分析,数据挖掘和机器学习中出现的广泛问题。该项目旨在展示这些技术——包括高级采样、稀疏化和网络的局部探索——将在提高算法可扩展性方面发挥越来越大的作用。它包含几个开放的问题和猜想,从网络分析到分布抽样,再到实现这一目标的社会影响。通过对图上的各种动态过程提供新的算法见解,该项目还旨在提高对静态图结构之外的网络方面的理解,以便为网络科学开发更好的算法理论。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(6)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Quantum-Inspired Combinatorial Games: Algorithms and Complexity
受量子启发的组合游戏:算法和复杂性
- DOI:10.4230/lipics.fun.2022.11
- 发表时间:2022
- 期刊:
- 影响因子:0
- 作者:Kyle G. Burke;Matthew Ferland;S. Teng
- 通讯作者:S. Teng
Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable
选举团的计算分析:竞选活动很困难,但大致可控
- DOI:10.1609/aaai.v35i6.16668
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Dehghani, Sina;Saleh, Hamed;Seddighin, Saeed;Teng, Shang-Hua
- 通讯作者:Teng, Shang-Hua
A graph-theoretical basis of stochastic-cascading network influence: Characterizations of influence-based centrality
- DOI:10.1016/j.tcs.2020.04.016
- 发表时间:2020-07
- 期刊:
- 影响因子:0
- 作者:Wei Chen;S. Teng;Hanrui Zhang
- 通讯作者:Wei Chen;S. Teng;Hanrui Zhang
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
通过(战略上)失败来赢得战争:解决无向地理中格兰迪价值观的复杂性
- DOI:10.1109/focs52979.2021.00119
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Kyle G. Burke;Matthew Ferland;S. Teng
- 通讯作者:S. Teng
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis.
量子逻辑综合中 CNOT 电路的最佳空间深度权衡。
- DOI:
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Jiang, Jiaqing;Sun, Xiaoming;Teng, Shang-Hua;Wu, Bujiao;Wu, Kewen;Zhang, Jialin
- 通讯作者:Zhang, Jialin
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Shanghua Teng其他文献
Shanghua Teng的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Shanghua Teng', 18)}}的其他基金
Conference: FOCS Conference Student and Postdoc Travel Support
会议:FOCS 会议学生和博士后旅行支持
- 批准号:
2332110 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF:Small: Transformation of Mathematical Games: Quantum Inspiration
AF:Small:数学游戏的转变:量子灵感
- 批准号:
2308744 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
SODA Conference Student and Postdoc Travel Support
SODA 会议学生和博士后旅行支持
- 批准号:
2204906 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
FOCS Conference Student and Postdoc Travel Support
FOCS 会议学生和博士后旅行支持
- 批准号:
2204910 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Conference: FOCS Conference Student and Postdoc Travel Support
会议:FOCS 会议学生和博士后旅行支持
- 批准号:
2232320 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
SODA Conference Student and Postdoc Travel Support
SODA 会议学生和博士后旅行支持
- 批准号:
2004246 - 财政年份:2020
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Student and Post-Doctoral Travel Grants for the 2019 Foundations of Computer Science (FOCS) Conference
2019 年计算机科学基础 (FOCS) 会议的学生和博士后旅费资助
- 批准号:
1935617 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Foundations of Computer Science (FOCS) Conference Student and Postdoc Travel Support
计算机科学基础 (FOCS) 会议学生和博士后旅行支持
- 批准号:
1833230 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond
AF:大型:协作研究:代数图算法:拉普拉斯算子及其他算法
- 批准号:
1111270 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Medium:Smoothed Analysis in Multi-Objective Optimization, Machine Learning, and Algorithmic Game Theory
AF:中:多目标优化、机器学习和算法博弈论中的平滑分析
- 批准号:
0964481 - 财政年份:2010
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: U.S.-Ireland R&D Partnership: CIF: AF: Small: Enabling Beyond-5G Wireless Access Networks with Robust and Scalable Cell-Free Massive MIMO
合作研究:美国-爱尔兰 R
- 批准号:
2322191 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Collaborative Research: U.S.-Ireland R&D Partnership: CIF: AF: Small: Enabling Beyond-5G Wireless Access Networks with Robust and Scalable Cell-Free Massive MIMO
合作研究:美国-爱尔兰 R
- 批准号:
2322190 - 财政年份:2023
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Scalable and Topologically Versatile Material Point Methods for Complex Materials in Multiphysics Simulation
AF:小型:协作研究:多物理场仿真中复杂材料的可扩展且拓扑通用的质点方法
- 批准号:
2153863 - 财政年份:2021
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Rigorous Approaches for Scalable Privacy-preserving Deep Learning
AF:小型:协作研究:可扩展的隐私保护深度学习的严格方法
- 批准号:
1908281 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Rigorous Approaches for Scalable Privacy-preserving Deep Learning
AF:小型:协作研究:可扩展的隐私保护深度学习的严格方法
- 批准号:
1908384 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Rigorous Approaches for Scalable Privacy-preserving Deep Learning
AF:小型:协作研究:可扩展的隐私保护深度学习的严格方法
- 批准号:
1910100 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Scalable and Topologically Versatile Material Point Methods for Complex Materials in Multiphysics Simulation
AF:小型:协作研究:多物理场仿真中复杂材料的可扩展且拓扑通用的质点方法
- 批准号:
1812944 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Scalable and Topologically Versatile Material Point Methods for Complex Materials in Multiphysics Simulation
AF:小型:协作研究:多物理场仿真中复杂材料的可扩展且拓扑通用的质点方法
- 批准号:
1813624 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Scalable, high-order mesh-free algorithms applied to bulk-surface biomechanical problems
AF:小型:协作研究:应用于体表面生物力学问题的可扩展、高阶无网格算法
- 批准号:
1717556 - 财政年份:2017
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Collaborative Research: Scalable, high-order mesh-free algorithms applied to bulk-surface biomechanical problems
AF:小型:协作研究:应用于体表面生物力学问题的可扩展、高阶无网格算法
- 批准号:
1714844 - 财政年份:2017
- 资助金额:
$ 50万 - 项目类别:
Standard Grant