The Space-Time Complexity of Sum-Product Queries

Summary: Analyzes combined space–time tradeoffs for conjunctive and general sum-product queries, introducing space-aware complexity measures. Proposes classes of space-efficient SPQ algorithms and shows optimal time is achievable with asymptotically lower space than traditional methods. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 2060
Venue: PODS
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,182 | 30.15%
DOI: 10.1145/3767719

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Kyle Deeds (University of Washington)
2. Timo Camillo Merkl (Vienna University of Technology)
3. Reinhard Pichler (Vienna University of Technology)
4. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{deeds_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{The Space-Time Complexity of Sum-Product Queries}},
        url = {https://dl.acm.org/doi/10.1145/3767719},
        doi = {10.1145/3767719},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Deeds, Kyle and Merkl, Timo Camillo and Pichler, Reinhard and Suciu, Dan},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
814	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00013841737
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
2,330	Hypertree Decompositions and Tractable Queries	1999	PODS	8.7447066e-05
3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
6,159	General and Fractional Hypertree Decompositions: Hard and Easy Cases	2018	PODS	5.9542729e-05
7,195	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	5.6765621e-05
7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	5.6466593e-05
7,978	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	5.514996e-05
10,643	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,154	Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum	2026	PODS
2	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
3	4,819	Space efficiency in Synopsis construction algorithms	2005	VLDB
4	10,020	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS
5	4,781	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS
6	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
7	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
8	7,195	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS
9	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
10	4,393	Bounded Conjunctive Queries	2014	VLDB