SPX: Automatically Parallelizing Approximate Data Analysis with Mergeable Summaries

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

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.