SPX: Automatically Parallelizing Approximate Data Analysis with Mergeable Summaries

Georgetown University, Washington DC

Investigators

Abstract

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.