{"ID":2860341,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.04249","arxiv_id":"2510.04249","title":"Ambidextrous Degree Sequence Bounds for Pessimistic Cardinality Estimation","abstract":"In a large database system, upper-bounding the cardinality of a join query is a crucial task called $\\textit{pessimistic cardinality estimation}$. Recently, Abo Khamis, Nakos, Olteanu, and Suciu unified related works into the following dexterous framework. Step 1: Let $(X_1, \\dotsc, X_n)$ be a random row of the join, equating $H(X_1, \\dotsc, X_n)$ to the log of the join cardinality. Step 2: Upper-bound $H(X_1, \\dotsc, X_n)$ using Shannon-type inequalities such as $H(X, Y, Z) \\le 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$\" in the underlying graph, we proposed $\\textit{ambidextrous}$ bounds that count \"claw pairs ${\\ni}\\!{-}\\!{\\in}$\". 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 $\\texttt{com-Youtube}$ dataset, the best dexterous bound is $1.2 \\cdot 10^9$, the best ambidextrous bound is $5.1 \\cdot 10^8$, and the actual cardinality is $1.8 \\cdot 10^7$.","short_abstract":"In a large database system, upper-bounding the cardinality of a join query is a crucial task called $\\textit{pessimistic cardinality estimation}$. Recently, Abo Khamis, Nakos, Olteanu, and Suciu unified related works into the following dexterous framework. Step 1: Let $(X_1, \\dotsc, X_n)$ be a random row of the join, e...","url_abs":"https://arxiv.org/abs/2510.04249","url_pdf":"https://arxiv.org/pdf/2510.04249v1","authors":"[\"Yu-Ting Lin\",\"Hsin-Po Wang\"]","published":"2025-10-05T15:34:18Z","proceeding":"cs.DB","tasks":"[\"cs.DB\",\"cs.IT\"]","methods":"[]","has_code":false}