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)
Incoming Non-self Citations Over Time
Authors
- 1. Mahmoud Abo Khamis (State University of New York at Buffalo)
- 2. Hung Q. Ngo (State University of New York at Buffalo)
- 3. Christopher Ré (Stanford University)
- 4. Atri Rudra (State University of New York at Buffalo)
BibTeX Citation
@inproceedings{khamis_pods15,
address = {New York, NY, USA},
series = {{PODS} '15},
title = {{Joins via Geometric Resolutions: Worst-case and Beyond}},
url = {https://dl.acm.org/doi/10.1145/2745754.2745776},
doi = {10.1145/2745754.2745776},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Khamis, Mahmoud Abo and Ngo, Hung Q. and Ré, Christopher and Rudra, Atri},
year = {2015}
}Incoming Citations (Sorted by Pagerank)
Showing 22 of 22 citing papers.
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 5 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0010828372 |
| 209 | Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs | 2009 | VLDB | 0.00024932174 |
| 290 | An Overview of Query Optimization in Relational Systems | 1998 | PODS | 0.0002227038 |
| 360 | Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs | 2011 | SIGMOD | 0.00020182846 |
| 382 | Conjunctive-Query Containment and Constraint Satisfaction | 1998 | PODS | 0.00019546431 |
| 411 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00018902089 |
| 414 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00018893507 |
| 1,673 | Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width | 2001 | PODS | 0.00010040854 |
| 1,699 | Beyond Worst-case Analysis for Joins with Minesweeper | 2014 | PODS | 9.975915e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,296 | Succinct Structure Representations for Efficient Query Optimization | 2026 | SIGMOD |
| 2 | 4,401 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS |
| 3 | 1,286 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 4 | 8,235 | Computing Complex Temporal Join Queries Efficiently | 2022 | SIGMOD |
| 5 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 6 | 3,617 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS |
| 7 | 411 | Worst-case Optimal Join Algorithms | 2012 | PODS |
| 8 | 10,153 | Faster Relational Algorithms Using Geometric Data Structures | 2026 | PODS |
| 9 | 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS |
| 10 | 1,740 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |