In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Wellington M. Cabrera Arevalo

will defend his dissertation

Optimized Algorithms for Data Analysis in Parallel Database Systems

Abstract

Large data sets are generally stored on disk following an organization as rows, columns or arrays, with row storage being the most common. On the other hand, matrix multiplication is frequently found in machine learning algorithms as an important primitive operation. Since database management systems do not support matrix operations, analytical tasks are commonly performed outside the database system, in external libraries or mathematical tools. In this work, we optimize several analytic algorithms that benefit from a fast in-database matrix multiplication. Specifically, we study how to compute in-database parallel matrix multiplication to solve two major family of big data analytics problems: machine learning models and graph algoriths. We focus on three cases: the product of a matrix by its transposed, the powers of a square matrix and iteration of matrix-vector multiplication. Based on this foundation, we introduce important optimizations to the computation of fundamental linear models in machine learning: linear regression, variable selection and principal components analysis. On the other hand, we present parallel graph algorithms that take advantage of matrix powers and parallel vector multiplication to solve several graph problems: transitive closure, all pairs shortest paths, reachability from a single source vertex, single source shortest paths, connected components and PageRank.

Date: Thursday, March 30, 2017
Time: 10:00 AM 
Place: PGH 550
Advisor: Dr. Carlos Ordonez

Faculty, students, and the general public are invited.