{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:10:33Z","timestamp":1762963833709,"version":"3.45.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS 2314527, SHF 2312195, IIS 2507117"],"award-info":[{"award-number":["IIS 2314527, SHF 2312195, IIS 2507117"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"WWTF","doi-asserted-by":"crossref","award":["10.47379\/ICT2201, 10.47379\/VRG18013, 10.47379\/NXT22018"],"award-info":[{"award-number":["10.47379\/ICT2201, 10.47379\/VRG18013, 10.47379\/NXT22018"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,11,10]]},"abstract":"<jats:p>While extensive research on query evaluation has achieved consistent improvements in the time complexity of algorithms, the space complexity of query evaluation has been largely ignored. This is a particular challenge in settings with strict pre-defined space constraints. In this paper, we examine the combined space-time complexity of conjunctive queries (CQs) and, more generally, of sum-product queries (SPQs). We propose several classes of space-efficient algorithms for evaluating SPQs, and we show that the optimal time complexity is almost always achievable with asymptotically lower space complexity than traditional approaches.<\/jats:p>","DOI":"10.1145\/3767719","type":"journal-article","created":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T15:06:02Z","timestamp":1762959962000},"page":"1-21","source":"Crossref","is-referenced-by-count":0,"title":["The Space-Time Complexity of Sum-Product Queries"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2267-3276","authenticated-orcid":false,"given":"Kyle","family":"Deeds","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7206-2518","authenticated-orcid":false,"given":"Timo Camillo","family":"Merkl","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"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, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"A. Abboud V. Vassilevska Williams and O. Weimann. Consequences of faster alignment of sequences. In J. Esparza P. Fraigniaud T. Husfeldt and E. Koutsoupias editors Automata Languages and Programming - 41st International Colloquium ICALP 2014 Copenhagen Denmark July 8-11 2014 Proceedings Part I volume 8572 of Lecture Notes in Computer Science pages 39-51. Springer 2014."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451014"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER59578.2024.00039"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718141"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3348514"},{"key":"e_1_2_1_10_1","volume-title":"The space-time complexity of sum-product queries. CoRR, abs\/2509.11920","author":"Deeds K.","year":"2025","unstructured":"K. Deeds, T. C. Merkl, R. Pichler, and D. Suciu. The space-time complexity of sum-product queries. CoRR, abs\/2509.11920, 2025."},{"key":"e_1_2_1_11_1","series-title":"Graduate texts in mathematics","volume-title":"R. Diestel. Graph Theory","year":"2012","unstructured":"R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.","edition":"4"},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"50th International Colloquium on Automata, Languages, and Programming, ICALP 2023","volume":"261","author":"Fan A. Z.","year":"2023","unstructured":"A. Z. Fan, P. Koutris, and H. Zhao. The fine-grained complexity of boolean conjunctive queries and sum-product problems. In K. Etessami, U. Feige, and G. Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 127:1-127:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2023."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196962"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_1_15_1","first-page":"1076","volume-title":"Proceedings of the 9th International Joint Conference on Artificial Intelligence","author":"Freuder E. C.","year":"1985","unstructured":"E. C. Freuder and M. J. Quinn. Taking advantage of stable sets of variables in constraint satisfaction problems. In A. K. Joshi, editor, Proceedings of the 9th International Joint Conference on Artificial Intelligence. Los Angeles, CA, USA, August 1985, pages 1076-1078. Morgan Kaufmann, 1985."},{"volume-title":"Google cluster data v3. https:\/\/github.com\/google\/cluster-data\/blob\/master\/clusterdata2019.md","year":"2019","key":"e_1_2_1_16_1","unstructured":"Google. Google cluster data v3. https:\/\/github.com\/google\/cluster-data\/blob\/master\/clusterdata2019.md, 2019."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_22_1","first-page":"414","volume-title":"Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019","author":"Khamis M. A.","year":"2019","unstructured":"M. A. Khamis, R. R. Curtin, B. Moseley, H. Q. Ngo, X. Nguyen, D. Olteanu, and M. Schleich. On functional aggregate queries with additive inequalities. In D. Suciu, S. Skritek, and C. Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 414-431. ACM, 2019."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725235"},{"key":"e_1_2_1_24_1","volume-title":"FAQ: questions asked frequently. CoRR, abs\/1504.04044","author":"Khamis M. A.","year":"2015","unstructured":"M. A. Khamis, H. Q. Ngo, and A. Rudra. FAQ: questions asked frequently. CoRR, abs\/1504.04044, 2015."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588676"},{"key":"e_1_2_1_28_1","first-page":"1236","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Lincoln A.","year":"2018","unstructured":"A. Lincoln, V. Vassilevska Williams, and R. R. Williams. Tight hardness for shortest cycles and paths in sparse graphs. In A. Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252. SIAM, 2018."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3719003"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_31_1","first-page":"1","volume-title":"10th Innovations in Theoretical Computer Science Conference, ITCS 2019","volume":"124","author":"McKay D. M.","year":"2019","unstructured":"D. M. McKay and R. R. Williams. Quadratic time-space lower bounds for computing natural functions with a random oracle. In A. Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 56:1-56:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_33_1","first-page":"37","volume-title":"Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012","author":"Ngo H. Q.","year":"2012","unstructured":"H. Q. Ngo, E. Porat, C. R\u00e9, and A. Rudra. Worst-case optimal join algorithms: [extended abstract]. In M. Benedikt, M. Kr\u00f6tzsch, and M. Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 37-48. ACM, 2012."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588677"},{"key":"e_1_2_1_37_1","first-page":"96","volume-title":"Proc. 17th International Conference on Database Theory (ICDT)","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In N. Schweikardt, V. Christophides, and V. Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96-106. OpenProceedings.org, 2014."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611489"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588675"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T16:08:35Z","timestamp":1762963715000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,11,10]]}},"alternative-id":["10.1145\/3767719"],"URL":"https:\/\/doi.org\/10.1145\/3767719","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,11,10]]}}}