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: 1998
Venue: PODS
Year: 2026
Pagerank: 4.1945683e-05
Overall Rank: 10,009 | 30.37%
DOI: 10.1145/3767719

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
1,328	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012565612
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
7,163	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8132033e-05
7,761	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.658708e-05
8,026	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	4.6030518e-05
10,347	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
10,927	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.1945683e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
3,719	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8204683e-05
10,898	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1945683e-05
5,858	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	5.2997454e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05
7,761	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.658708e-05
4,546	Bounded Conjunctive Queries	2014	VLDB	6.0987778e-05