The Polymatroid Bound: Extensions and Applications in Database Query Evaluation (part 2).

Abstract: This is the second part of the talk, the first part of which took place on May 24. I continue our discussion of information-theoretic upper bounds on the output sizes of database queries. I will recap the polymatroid bound and present a corresponding query evaluation algorithm, called PANDA, whose runtime matches the polymatroid bound [Abo Khamis et al, PODS’17]. I will also discuss this algorithm's shortcomings and related open problems. Acquaintance with the first part of the talk is very desirable, although formally it is not required.

Computer scienceMathematics

Audience: researchers in the discipline

( paper )

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.