{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:58:20Z","timestamp":1775595500002,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]},{"name":"NSF IIS","award":["2314527"],"award-info":[{"award-number":["2314527"]}]},{"name":"NSF SHF","award":["2312195"],"award-info":[{"award-number":["2312195"]}]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021-231956"],"award-info":[{"award-number":["200021-231956"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>\n                    This paper introduces\n                    <jats:sc>CorrBound<\/jats:sc>\n                    , a cardinality estimator that exploits the correlations between the join columns across and within relations. The state-of-the-art estimators do not observe such correlations and can therefore yield poor estimates. By explicitly accounting for correlations,\n                    <jats:sc>CorrBound<\/jats:sc>\n                    can significantly improve the accuracy of cardinality estimation.\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:sc>CorrBound<\/jats:sc>\n                    supports multi-join queries (acyclic or cyclic) with conjunctions of equality and range predicates and group-by clauses. Its estimate is the optimal solution of a linear program whose constraints encode data statistics and Shannon inequalities. It uses a new information inequality that captures the intra- and inter-relation correlations of join columns and uses the generalized inner product of degree vectors of join columns. This inequality also captures the \u2113\n                    <jats:sub>p<\/jats:sub>\n                    -norm inequality used by the state-of-the-art estimator LpBound.\n                  <\/jats:p>\n                  <jats:p>\n                    The inequality comes with a high-dimensionality challenge: managing the cardinality tensor defined by the generalized inner products of many large degree vectors. To keep the estimation time feasible,\n                    <jats:sc>CorrBound<\/jats:sc>\n                    uses two compression techniques that retain the accuracy of the inner products: sketches of degree vectors and low-rank decomposition of the cardinality tensor.\n                  <\/jats:p>\n                  <jats:p>\n                    We experimentally evaluate\n                    <jats:sc>CorrBound<\/jats:sc>\n                    against traditional, pessimistic, and machine learning-based estimators on the JOBlight and STATS, and subgraph matching benchmarks. Our main finding is that\n                    <jats:sc>CorrBound<\/jats:sc>\n                    can be more accurate than the state of the art while maintaining a low estimation time.\n                  <\/jats:p>","DOI":"10.1145\/3786633","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["<scp>CorrBound:<\/scp>\n                    Cardinality Estimation Accounting for Inter- and Intra-relation Correlations"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-6651-3900","authenticated-orcid":false,"given":"Christoph","family":"Mayer","sequence":"first","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0930-1980","authenticated-orcid":false,"given":"Haozhe","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"additional","affiliation":[{"name":"RelationalAI, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2267-3276","authenticated-orcid":false,"given":"Kyle","family":"Deeds","sequence":"additional","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651597"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2001.1813"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1545"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035921"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"G. Cormode and K. Yi. 2020. Small Summaries for Big Data. Cambridge University Press. 2020033065 https:\/\/books.google.com\/books?id=6in-DwAAQBAJ","DOI":"10.1017\/9781108769938"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375685"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288367"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.61"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233340"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375727"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654932"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689209"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/S12532-017-0130-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725233"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452840"},{"key":"e_1_2_1_27_1","unstructured":"Sai Vikneshwar Mani Jayaraman Corey Ropell and Atri Rudra. 2021. Worst-case Optimal Binary Join Algorithms under General $ell_p$ Constraints. arXiv:2112.01003 [cs.DB] https:\/\/arxiv.org\/abs\/2112.01003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526154"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457246"},{"key":"e_1_2_1_30_1","volume-title":"Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR. http:\/\/cidrdb.org\/cidr2019\/papers\/p101-kipf-cidr19.pdf"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070111X"},{"key":"e_1_2_1_32_1","volume-title":"CIDR","author":"Leis Viktor","unstructured":"Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper, and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling. In CIDR. http:\/\/cidrdb.org\/cidr2017\/papers\/p9-leis-cidr17.pdf"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526179"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_2_1_36_1","unstructured":"Jan Motl and Oliver Schulte. 2024. Stats Stack Exchange Network Dataset. https:\/\/relational.fel.cvut.cz\/dataset\/Stats The CTU Prague Relational Learning Repository."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636229"},{"key":"e_1_2_1_38_1","series-title":"New Series","volume-title":"An extension of a certain theorem in inequalities. Messenger of Mathematics","author":"Rogers L. J.","year":"1888","unstructured":"L. J. Rogers. 1888. An extension of a certain theorem in inequalities. Messenger of Mathematics, New Series, Vol. XVII, 10 ( 1888), 145\u2013-150."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882948"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386121"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3749646.3749683"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/J.1538-7305.1948.TB01338.X"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639321"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402724"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588935"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00035"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588721"},{"key":"e_1_2_1_52_1","volume-title":"BayesCard: A Unified Bayesian Framework for Cardinality Estimation. CoRR","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu and Amir Shaikhha. 2020. BayesCard: A Unified Bayesian Framework for Cardinality Estimation. CoRR, Vol. abs\/2012.14743 (2020). arXiv:2012.14743 https:\/\/arxiv.org\/abs\/2012.14743"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725321"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:57:47Z","timestamp":1775591867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786633"],"URL":"https:\/\/doi.org\/10.1145\/3786633","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}