An Information Theoretic Approach to Estimating Query Size Bounds.

Abstract: Cardinality estimation is one of the most important problems in database management. One aspect of cardinality estimation is to derive a good upper bound on the output size of a query, given a statistical profile of the inputs. In recent years, a promising information-theoretic approach was devised to address this problem, leading to robust cardinality estimators which are used in practice. The information theoretic approach led to many interesting open questions surrounding optimizing a linear function on the almost-entropic or polymatroidal cones. This talk introduces the problem, the approach, summarizes some known results, and lists open questions.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.