SPX: Automatically Parallelizing Approximate Data Analysis with Mergeable Summaries

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

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.