CAREER: Pushing the Theoretical Limits of Scalable Distributed Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Science and engineering are becoming more reliant on analyzing data sets that have massive size. Processing these data sets typically requires using many machines, such as on the cloud, meaning that algorithms and software for data processing need to be redesigned to efficiently use a large number of machines. This project will give algorithmic techniques for distributed computing models (aka frameworks) such as Spark. Such a framework enables programmers to easily deploy algorithms on tens to thousands of machines as long as the algorithm fits into the computational restrictions of the framework. The algorithmic primitives developed will be tools that algorithm designers and programmers can leverage to analyze large amounts of data on many machines. This will impact industry, science and the economy that is increasingly reliant on large data analysis. Research outcomes will be integrated with education by including the latest research on data analytics in the undergraduate and master of science in business analytics programs. Massively distributed frameworks such as Spark and MapReduce are a key technology for processing large data sets. These systems have traditionally been used to solve relatively simple problems. Recent investigation has shown they are potentially useful for a richer class of applications. With this potential as a proof-of-concept, this project will discover algorithmic techniques tailored to these frameworks to unlock their underlying power and broaden their applicability. A recently developed theoretical model of computation will be used to drive the development of algorithmic techniques designed to leverage the unique features of the frameworks. The new algorithms and techniques will be used to offer scalable solutions for key problems arising in graph processing, data mining, and bioinformatics. Specifically, the project will develop algorithms to compute shortest paths on massive graphs, algorithms for local alignment of biological sequences and some of the first provably scalable algorithms for hierarchical clustering. Achieving these goals can influence practice and theoretical research similarly to successes in other areas such as streaming algorithms. 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.