{"ID":2870918,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11920","arxiv_id":"2509.11920","title":"The Space-Time Complexity of Sum-Product Queries","abstract":"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.","short_abstract":"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-ti...","url_abs":"https://arxiv.org/abs/2509.11920","url_pdf":"https://arxiv.org/pdf/2509.11920v3","authors":"[\"Kyle Deeds\",\"Timo Camillo Merkl\",\"Reinhard Pichler\",\"Dan Suciu\"]","published":"2025-09-15T13:36:55Z","proceeding":"cs.DB","tasks":"[\"cs.DB\"]","methods":"[]","has_code":false}