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: 1999
Venue: PODS
Year: 2026
Pagerank: 4.1905499e-05
Overall Rank: 10,009 | 30.44%
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
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
1,322	Hypertree Decompositions: Questions and Answers	2016	PODS	0.00012595941
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,804	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1039107e-05
3,009	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7230513e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
7,162	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	4.8085863e-05
7,762	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.6542406e-05
8,027	ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning	2023	VLDB	4.5986382e-05
10,359	Fast Matrix Multiplication meets the Submodular Width	2025	PODS	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
8,521	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	4.4893996e-05
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
3,720	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8139746e-05
10,902	Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization	2024	PODS	4.1905499e-05
5,859	Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries	2021	PODS	5.2963939e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
12,039	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1905499e-05
7,762	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	4.6542406e-05
4,545	Bounded Conjunctive Queries	2014	VLDB	6.0917464e-05