演講者：王新博教授 ( 國立臺灣大學電機工程學系 )

日   期：2025 年 09 月 17 日（星期三）13:30

地   點：國立高雄大學理學院 408 室

講   題：Ambidextrous Degree Sequence Bounds for Pessimistic Cardinality Estimation

摘   要：

In a large database system, upper-bounding the cardinality of a join query is a crucial task called pessimistic cardinality estimation.  Recently, Abo Khamis, Nakos, Olteanu, and Suciu unified related works into the following dexterous framework. Step 1: Let (X_1, ..., X_n) be a random row of the join, equating H(X_1, ..., X_n) to the log of the join cardinality.  Step 2: Upper-bound H(X_1, ..., X_n) using Shannon-type inequalities such as H(X, Y, Z) ≤ H(X) + H(Y|X) + H(Z|Y).  Step 3: Upper-bound H(X_i) + p H(X_j | X_i) using the p-norm of the degree sequence of the underlying graph of a relation.

While old bound in step 3 count claws in the underlying graph, we proposed ambidextrous bounds that count claw pairs.  The new bounds are provably not looser and empirically tighter: they overestimate by x^{3/4} times when the old bounds overestimate by x times.  An example is counting friend triples in the com-Youtube dataset, the best dexterous bound is 1.2 * 10^9, the best ambidextrous bound is 5.1 * 10^8, and the actual cardinality is 1.8 * 10^7.

Hsin-Po Wang is an Assistant Professor in EE and GICE at NTU. His research interests lie in information theory and coding theory, where he applies techniques in algebra, combinatorics, and probability theory to polar codes, group testing, distributed storage, distributed computation, sampling algorithms, and database optimization. Hsin-Po earned his B.Sc. in Math at NTU and completed his Ph.D. in Math at UIUC. He has held research positions at UC San Diego, UC Berkeley, and the Simons Institute for the Theory of Computing. Known for his extensive, creative use of Tikz figures in papers, Hsin-Po is equally passionate about speedrun techniques for educational purposes and assembling binder clips into fullerene-like structures.