Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems
Summary: Tutorial survey of worst-case optimal join algorithms, connecting AGM-style output bounds and information-theoretic inequalities to executable algorithms. Reviews cross-disciplinary techniques, practical adoption, and foundational open problems. (summarized by gpt-5.6-luna on Jul 26 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Hung Q. Ngo (RelationalAI Inc.)
BibTeX Citation
@inproceedings{ngo_pods18,
address = {New York, NY, USA},
series = {{PODS} '18},
title = {{Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems}},
url = {https://dl.acm.org/doi/10.1145/3196959.3196990},
doi = {10.1145/3196959.3196990},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Ngo, Hung Q.},
year = {2018}
}
Incoming Citations (Sorted by Pagerank)
Showing 31 of 81 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 27 of 27 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,907 | Worst Case Optimal Joins on Relational and XML data | 2018 | SIGMOD |
| 2 | 4,401 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins | 2016 | PODS |
| 3 | 7,882 | Efficiently Computing Join Orders with Heuristic Search | 2023 | SIGMOD |
| 4 | 2,462 | Output-optimal Parallel Algorithms for Similarity Joins | 2017 | PODS |
| 5 | 1,286 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 6 | 5,601 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD |
| 7 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 8 | 1,857 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS |
| 9 | 1,740 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |
| 10 | 411 | Worst-case Optimal Join Algorithms | 2012 | PODS |