The Space-Time Complexity of Sum-Product Queries
Published in PODS 2026, 2025
This paper studies the combined space and time complexity of evaluating conjunctive queries (CQs) and sum-product queries (SPQs), an area largely ignored by prior work focused only on time complexity. It gives several classes of space-efficient algorithms that achieve optimal time complexity with asymptotically lower space complexity than traditional approaches.
Recommended citation: Deeds, K., Merkl, T. C., Pichler, R., & Suciu, D. (2025). The Space-Time Complexity of Sum-Product Queries. Proceedings of the ACM on Management of Data, 3(5), Article 283, 1-21. https://doi.org/10.1145/3767719
Recommended citation: Deeds, K., Merkl, T. C., Pichler, R., & Suciu, D. (2025). The Space-Time Complexity of Sum-Product Queries. Proceedings of the ACM on Management of Data, 3(5), Article 283, 1-21. https://doi.org/10.1145/3767719
Download Paper