权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

SPX: Automatically Parallelizing Approximate Data Analysis with Mergeable Summaries

SPX：通过可合并摘要自动并行化近似数据分析

基本信息

批准号：
1918989
负责人：
Justin Thaler
金额：
$ 61.42万
依托单位：
Georgetown University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1918989&HistoricalAwards=false
关键词：
SPX Automatically Parallelizing Approximate Data

项目摘要

When analyzing massive data sets, generating exact answers to even very basic queries can require huge amounts of compute resources (memory, compute time, and network communication). Fortunately, in many settings, approximate answers suffice. Nevertheless, designing algorithms that operate efficiently at large scale remains a significant challenge. This project studies highly efficient, highly accurate, and highly scalable algorithms for approximate query processing. The key ingredient enabling such efficiency is streaming algorithms that generate mergeable summaries. Streaming algorithms in general compute a small summary of the data, from which it is possible to derive accurate (though approximate) answers to queries. When these summaries are also mergeable, one can process many data sets independently and combine their summaries to answer queries about their combinations (union, intersection, etc). Mergeable summaries enable massive data sets to be processed in highly scalable ways by distributing the data across machines, summarizing each partition, and seamlessly combining the results.This project will develop mergeable summaries for a variety of fundamental problems for which no practical mergeable summary is known (such as entropy approximation and unsupervised-learning tasks including k-means clustering and logistic regression). For other commonly-used problems, such as estimating the number of distinct items in a data stream, the project will substantially improve upon known, already practical, mergeable summaries. This project is tightly entwined with the development of the Data Sketches library, an open-source library of production-quality implementations of mergeable summaries that is widely used in industry and government.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.

在分析海量数据集时，即使是非常基本的查询，也需要大量的计算资源（内存、计算时间和网络通信）。幸运的是，在许多情况下，近似的答案就足够了。然而，设计大规模有效运行的算法仍然是一个重大挑战。本计画研究高效率、高准确度、高扩充性的近似查询处理演算法。实现这种效率的关键因素是生成可合并摘要的流算法。流算法通常计算数据的一个小摘要，从中可以得出查询的准确（尽管近似）答案。当这些摘要也是可合并的时，人们可以独立地处理许多数据集，并且联合收割机组合它们的摘要以回答关于它们的组合（并集、交集等）的查询。可合并摘要通过将数据分布在机器上，汇总每个分区，并无缝组合结果，使海量数据集以高度可扩展的方式进行处理。该项目将为各种基本问题开发可合并摘要，这些问题目前还没有实用的可合并摘要（例如熵近似和无监督学习任务，包括k均值聚类和逻辑回归）。对于其他常用的问题，例如估计数据流中不同项目的数量，该项目将大大改进已知的，已经实用的，可合并的摘要。该项目与Data Sketches库的开发紧密相连，Data Sketches库是一个开源的可合并摘要的生产质量实现库，广泛用于工业和政府。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（16）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Optimal Parallel Algorithms in the Binary-Forking Model

二分叉模型中的最优并行算法

DOI：
10.1145/3350755.3400227
发表时间：
2020
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Blelloch, Guy E.;Fineman, Jeremy T.;Gu, Yan;Sun, Yihan
通讯作者：
Sun, Yihan

Parallel Shortest Paths with Negative Edge Weights

具有负边权重的并行最短路径

DOI：
10.1145/3490148.3538583
发表时间：
2022
期刊：
SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina

Contention Resolution with Message Deadlines

DOI：
10.1145/3350755.3400239
发表时间：
2020-07
期刊：
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Kunal Agrawal;M. A. Bender;Jeremy T. Fineman;Seth Gilbert;Maxwell Young
通讯作者：
Kunal Agrawal;M. A. Bender;Jeremy T. Fineman;Seth Gilbert;Maxwell Young

Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths

改进工作跨度权衡单一源可达性和近似最短路径

DOI：
10.1145/3350755.3400222
发表时间：
2020
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina

Brief Announcement: Nested Active-Time Scheduling

简短公告：嵌套活动时间调度

DOI：
10.1145/3490148.3538554
发表时间：
2022
期刊：
SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Cao, Nairen;Fineman, Jeremy T.;Li, Shi;Mestre, Julián;Russell, Katina;Umboh, Seeun William
通讯作者：
Umboh, Seeun William