PODS 2024: Tutorials
Tutorial 1: Closing the Gap Between Theory and Practice in Query Optimization
Speaker: Thomas Neumann (TU Munich)
Abstract
Query optimization, and in particular the problem of join ordering, has a huge impact on the performance of database systems. Accordingly, it has been widely studied in the literature, but there is a, perhaps surprising, gap between techniques that have been proposed in venues like PODS and the techniques that are used in typical systems. There are several reasons for that, but one of them is that many theoretical approaches look at asymptotic complexity, while systems tends to primarily care about the performance of a query for a given database instance in absolute terms. This tutorial looks at the differences and tries to bring both worlds closer together.
Tutorial 2: Approximation Algorithms on Matrices - with some Database Applications!
Speaker: David Woodruff (CMU)
Abstract
In this talk I will cover dimensionality reduction techniques, or sketching, for solving optimization problems on large matrices. Classical polynomial time solutions to optimization problems involving matrices are often no longer efficient given the large size of matrices arising on big data sets. Instead, one seeks linear or sometimes even sublinear time solutions to such optimization problems. These often involve randomized algorithms and come at the price of a small approximation error. The idea behind sketching techniques is to reduce a large instance of a problem to a much smaller instance of the same problem in such a way that solving the small instance gives an approximate solution to the large instance. Oftentimes the smaller problem is now so small that one can directly apply a classical polynomial time algorithm to solve it directly. Thus, the emphasis is on how to perform the reduction itself to the small problem very quickly, i.e., in linear or sub-linear time. I will survey a wide range of technique for this, which often have the form of multiplying the input matrix by a random matrix, or have the form of sampling or recursive sampling.
