Speaker

Kirk Pruhs

Abstract

The current standard practice for a data scientist, confronted with a machine learning task on relational data, is to issue a feature extraction query to extract the (carefully curated) data from a relational database by joining together multiple tables to materialize a design matrix, and then to import this design matrix into some machine learning tool to train the model. This standard practice is not ideal for several reasons, one of which is that computing relational joins is computationally expensive (exponential in the worst case). I will discuss efforts to develop "relational algorithms" for commonly-arising geometric problems that commonly arise in machine learning applications. Informally a "relational algorithm" is an efficient algorithm that works directly on the relational data. My emphasis will be on providing a gentle introduction of the basic foundational ideas that should be understandable by a broad audience.

Bio

Kirk Pruhs is a professor of computer science at the University of Pittsburgh, specializing in foundational algorithmic research. He is also a consultant for the startup RelationalAI for algorithmic problems arising from database applications. He lived in Iowa City early enough in his childhood to have eaten at Hamburg Inn No. 1, and have had Ed Podolak as a neighbor.