AF: Small: Data Stream Algorithms with Application to Linear Algebra

AF:小:数据流算法及其在线性代数中的应用

基本信息

  • 批准号:
    1815840
  • 负责人:
  • 金额:
    $ 43.4万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2018
  • 资助国家:
    美国
  • 起止时间:
    2018-06-01 至 2023-05-31
  • 项目状态:
    已结题

项目摘要

Many important problems in machine learning, scientific computing, and statistics benefit from fast procedures for solving numerical linear algebra problems. At the same time, many large-scale datasets, such as internet search logs, network traffic, and sensor network data, have been studied in data-stream literature. Surprisingly, a number of fast procedures used in numerical linear algebra have been made possible by exploiting tools that were originally developed in the data-stream literature. These developments are based on a technique called sketching, which is a tool for quickly compressing a problem to a smaller version of itself, for which one can then afford to run a much slower procedure on the smaller problem. A major goal of this project is to study foundational problems in the data-stream domain, and develop their connections to problems in numerical linear algebra. The algorithms developed here will be accessible to graduate and undergraduate students from computer science, machine learning, and mathematics, and the investigator plans to integrate the results of the project into a graduate course on algorithms for big data, as well as undergraduate algorithms courses. The investigator is actively working with underrepresented minority and undergraduate researchers on topics directly related to this project.The first main thrust of this project is to develop new techniques for fundamental problems in data streams where the goal is to use minimal amount of memory while running algorithms over one pass on a data stream. Such problems include statistical problems - such as estimating the variance, moments, most frequent items, heavy hitters - for many of which optimal memory bounds are still unknown. Another challenge in this domain is that of processing massive streams for real-world graphs, such as geometric intersection graphs, which arise in cellular networks and scheduling theory. By studying a breadth of problems in different corners of data streams, the investigator plans to develop new techniques and build unexpected applications. The second main thrust of the project is to develop new algorithms and hardness results for fundamental problems in numerical linear algebra, connecting such problems to the study of data streams. CountSketch, which is a low-memory heavy hitters algorithm, paved the way for obtaining time-optimal algorithms for regression. This project will continue to push forward such connections, for example, by studying CountSketch in the context of tensors, which is a new application domain. The project will also investigate many deterministic (instead of randomized) data stream algorithms, and understanding their role in linear algebra. A major goal is to understand the limitations of speedups to linear algebra problems. One particular problem of interest here is to obtain low rank approximation with spectral norms.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.
机器学习、科学计算和统计学中的许多重要问题都得益于解决数值线性代数问题的快速程序。与此同时,在数据流文献中,已经研究了许多大规模的数据集,如互联网搜索日志、网络流量和传感器网络数据。令人惊讶的是,通过利用最初在数据流文献中开发的工具,数值线性代数中使用的许多快速过程已经成为可能。这些发展是基于一种名为草图的技术,这是一种快速将问题压缩为自身较小版本的工具,因此人们可以对较小的问题运行一个慢得多的过程。这个项目的一个主要目标是研究数据流领域的基本问题,并发展它们与数值线性代数问题的联系。这里开发的算法将对计算机科学、机器学习和数学的研究生和本科生开放,研究人员计划将该项目的结果整合到大数据算法研究生课程和本科算法课程中。研究人员正在积极地与代表不足的少数民族和本科生研究人员就与该项目直接相关的主题进行合作。该项目的第一个主要推动力是为数据流中的基本问题开发新的技术,目标是在数据流上一遍运行算法时使用最少的内存。这类问题包括统计问题--例如估计方差、矩、最频繁项、重击次数--对于其中许多问题,最优存储界限仍是未知的。这一领域的另一个挑战是处理现实世界图的海量流,例如在蜂窝网络和调度理论中出现的几何交叉图。通过研究数据流不同角落的广泛问题,研究人员计划开发新技术和构建意想不到的应用程序。该项目的第二个主要目的是为数值线性代数中的基本问题开发新的算法和困难结果,将这些问题与数据流的研究联系起来。CountSketch是一种低内存的重量级算法,它为获得时间最优的回归算法铺平了道路。该项目将继续推动这种联系,例如,通过在张量的背景下研究CountSketch,这是一个新的应用领域。该项目还将研究许多确定性(而不是随机化)数据流算法,并了解它们在线性代数中的作用。一个主要目标是了解加速到线性代数问题的限制。这里一个特别感兴趣的问题是获得谱规范的低等级近似。这一奖项反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(71)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
深度神经网络的跨度恢复及其输入混淆的应用
  • DOI:
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jayaram, Rajesh;Woodruff, David P.;Zhang, Richard
  • 通讯作者:
    Zhang, Richard
Matrix Sketching with Applications to Regression and Optimization
矩阵草图及其在回归和优化中的应用
Perfect $L_p$ Sampling in a Data Stream
数据流中的完美 $L_p$ 采样
  • DOI:
    10.1137/18m1229912
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    1.6
  • 作者:
    Jayaram, Rajesh;Woodruff, David
  • 通讯作者:
    Woodruff, David
The ℓp-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
小维中的 β 子空间草图问题及其支持向量机的应用
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Li, Yi;Lin, Honghao;Woodruff, David P.
  • 通讯作者:
    Woodruff, David P.
{{ 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 }}

David Woodruff其他文献

Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020
理论计算机科学的愿景:2020 年 TCS 愿景研讨会报告
  • DOI:
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Shuchi Chawla;Jelani Nelson;C. Umans;David Woodruff
  • 通讯作者:
    David Woodruff
Linear Models for Item Scores: Reliability, Covariance Structure, and Psychometric Inference
项目分数的线性模型:可靠性、协方差结构和心理测量推理
  • DOI:
  • 发表时间:
    1993
  • 期刊:
  • 影响因子:
    0
  • 作者:
    David Woodruff
  • 通讯作者:
    David Woodruff
Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients
Grass:使用结构化稀疏梯度计算高效的低内存 LLM 训练
  • DOI:
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Aashiq Muhamed;Oscar Li;David Woodruff;Mona Diab;Virginia Smith
  • 通讯作者:
    Virginia Smith
A Primate Genome Project Deserves High Priority
灵长类动物基因组计划值得高度重视
  • DOI:
  • 发表时间:
    2000
  • 期刊:
  • 影响因子:
    56.9
  • 作者:
    E. McConkey;A. Varki;J. Allman;K. Benirschke;F. Crick;T. Deacon;F. D. de Waal;A. Dugaiczyk;P. Gagneux;M. Goodman;L. Grossman;D. Gumucio;T. Insel;K. Kidd;M. King;K. Krauter;R. Kucherlapati;A. Motulsky;D. Nelson;P. Oefner;George E. Palade;George E. Palade;O. Ryder;C. Stewart;J. Sikela;A. Stone;David Woodruff
  • 通讯作者:
    David Woodruff
“Socialist Accounting” by Karl Polanyi: with preface “Socialism and the embedded economy”
  • DOI:
    10.1007/s11186-016-9276-9
  • 发表时间:
    2016-08-17
  • 期刊:
  • 影响因子:
    1.400
  • 作者:
    Johanna Bockman;Ariane Fischer;David Woodruff
  • 通讯作者:
    David Woodruff

David Woodruff的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('David Woodruff', 18)}}的其他基金

Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
  • 批准号:
    2335412
  • 财政年份:
    2024
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
Travel Support for 16th Tri-Annual International Conference on Stochastic Programming (ICSP); Davis, California; 24-28 July 2023
第 16 届三年一度的随机规划国际会议 (ICSP) 的差旅支持;
  • 批准号:
    2309931
  • 财政年份:
    2023
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
New insights into complex molecule-surface interactions through local structure determination
通过局部结构测定对复杂分子-表面相互作用的新见解
  • 批准号:
    EP/D034329/1
  • 财政年份:
    2006
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Research Grant
Surface, subsurface and buried interface structure at the atomic scale; pushing the limits of medium energy ion scattering
原子尺度的表面、次表面和埋入界面结构;
  • 批准号:
    EP/E021786/1
  • 财政年份:
    2006
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Research Grant
Molecular Evolution and Systematics of Marmosets (Primates: Callithrix)
狨猴的分子进化和系统学(灵长类动物:Callithrix)
  • 批准号:
    9511194
  • 财政年份:
    1995
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
CRB: Population Viability and Biodiversity Following Rainforest Fragmentation
CRB:雨林破碎化后的人口生存能力和生物多样性
  • 批准号:
    9300182
  • 财政年份:
    1993
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
DNA Sequences and Fingerprints from Chimpanzee Hair: A New Approach to Establishing Genetic and Evolutionary Relationships
黑猩猩毛发的 DNA 序列和指纹:建立遗传和进化关系的新方法
  • 批准号:
    9011896
  • 财政年份:
    1990
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Continuing Grant
CRB: Population Viability of Tropical Forest Vertebrates
CRB:热带森林脊椎动物的种群活力
  • 批准号:
    9000486
  • 财政年份:
    1990
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Continuing Grant
Genetic Variation and Systematics of Cerion and Biomphalaria(Mollusca: Gastropoda)
Cerion 和 Bimphalaria(软体动物:腹足纲)的遗传变异和系统学
  • 批准号:
    8500733
  • 财政年份:
    1985
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
Genetics of Host-Parasite Compatibility: Snail Resistance to a Trematode
宿主-寄生虫相容性的遗传学:蜗牛对吸虫的抗性
  • 批准号:
    8311210
  • 财政年份:
    1984
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard 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: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
  • 批准号:
    2218814
  • 财政年份:
    2022
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
  • 批准号:
    2218813
  • 财政年份:
    2022
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: Small: The Geometry of Learning on Structured Data Objects
AF:小:结构化数据对象学习的几何
  • 批准号:
    2115677
  • 财政年份:
    2021
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: Small: Algorithms and Data Structures with Predictions
AF:小:具有预测的算法和数据结构
  • 批准号:
    2101140
  • 财政年份:
    2021
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: Small: New Directions for Parallel Data Structures
AF:小:并行数据结构的新方向
  • 批准号:
    2103483
  • 财政年份:
    2021
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: Small: Expanding the Reach of Topological Data Analysis
AF:小:扩大拓扑数据分析的范围
  • 批准号:
    2049010
  • 财政年份:
    2020
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
CIF: AF: Small: Data Processing Against Synchronization Errors
CIF:AF:小:针对同步错误的数据处理
  • 批准号:
    2006455
  • 财政年份:
    2020
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: Small: Expanding the Reach of Topological Data Analysis
AF:小:扩大拓扑数据分析的范围
  • 批准号:
    2007961
  • 财政年份:
    2020
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: SMALL: Finding Models of Data and Mathematical Objects
AF:小:寻找数据和数学对象的模型
  • 批准号:
    1909634
  • 财政年份:
    2019
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Dynamic data structures for vectors and graphs in sublinear memory
AF:小:协作研究:亚线性存储器中向量和图形的动态数据结构
  • 批准号:
    1908821
  • 财政年份:
    2019
  • 资助金额:
    $ 43.4万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了