Joins via Geometric Resolutions: Worst-case and Beyond

Summary: Introduce a geometric framework that formalizes index inference as “geometric resolution”, reducing join evaluation to a geometric problem and yielding an algorithm that achieves the fractional hypertree‑width bound. Also gives beyond‑worst‑case guarantees for B‑trees, multidimensional structures and multiple indices per table, and connects to logical resolution and backtracking-with-memoization perspectives. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1661
Venue: PODS
Year: 2015
Pagerank: 9.0776226e-05
Overall Rank: 2,296 | 84.03%
DOI: 10.1145/2745754.2745776

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
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
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
5,059	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	5.7277656e-05
5,077	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	5.7153846e-05
5,493	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4771449e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
6,639	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	4.9801324e-05
7,332	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7606012e-05
8,031	BSX : Subgraph Matching with Batch Backtracking Search	2025	SIGMOD	4.6018906e-05
8,354	LogiQL: a Declarative Language for Enterprise Applications	2015	PODS	4.538638e-05
8,472	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.5036378e-05
10,324	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1945683e-05
10,483	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.1945683e-05
10,631	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
407	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00024004562
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493
2,015	Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width	2001	PODS	9.7901938e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
10,921	Optimal (Multiway) Spatial Joins	2024	PODS	4.1945683e-05
6,305	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	5.1209718e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05