Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation

Speaker(s)

Krzysztof Żyndul

Affiliation

MIMUW

Language of the talk

Polish

Date

June 10, 2025, 10:15 a.m.

Room

room 4060

Title in English

Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation

Seminar

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

W moim referacie przedstawię estymator LpBound, zaprezentowany w pracy "LpBound: Pessimistic Cardinality Estimation using lp-Norms of Degree Sequences". Estymator ten wyznacza dowodliwie ścisłe, górne ograniczenie na rozmiar wyników zapytań. Wykorzystuje do tego lp-normy ciągów stopni relacji oraz teorię informacji. Na podstawie wyników eksperymentalnych zawartych w publikacji porównam skuteczność i wydajność LpBound z tradycyjnymi estymatorami stosowanymi w systemach Postgres i DuckDB.

---