Beyond Worst-case Analysis for Joins with Minesweeper
Summary: Minesweeper: an index-aware join algorithm using certificate complexity for beyond-worst-case guarantees. Runs linear in certificate+output for β-acyclic queries (extensions to bounded treewidth/triangle); β-cyclic cases can force superlinear time. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Hung Q. Ngo (State University of New York at Buffalo)
- 2. Dung T. Nguyen (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{ngo_pods14,
address = {New York, NY, USA},
series = {{PODS} '14},
title = {{Beyond Worst-case Analysis for Joins with Minesweeper}},
url = {https://dl.acm.org/doi/10.1145/259438.2594547},
doi = {10.1145/259438.2594547},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Ngo, Hung Q. and Nguyen, Dung T. and Ré, Christopher and Rudra, Atri},
year = {2014}
}
Incoming Citations (Sorted by Pagerank)
Showing 18 of 18 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 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.0010679641 |
| 402 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00019104625 |
| 421 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00018516535 |
| 684 | Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants | 2007 | PODS | 0.00014798237 |
| 3,660 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.1218018e-05 |
| 7,186 | The Parameterized Complexity of Database Queries | 2001 | PODS | 5.5912387e-05 |
| 7,187 | Connections in Acyclic Hypergraphs -- Extended Abstract | 1982 | PODS | 5.5912387e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,095 | Smallest Synthetic Witnesses for Conjunctive Queries | 2025 | PODS |
| 2 | 7,435 | Efficient Computation of Quantiles over Joins | 2023 | PODS |
| 3 | 3,494 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 4 | 6,955 | The Complexity of Boolean Conjunctive Queries with Intersection Joins | 2022 | PODS |
| 5 | 3,992 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS |
| 6 | 402 | Worst-case Optimal Join Algorithms | 2012 | PODS |
| 7 | 3,596 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD |
| 8 | 8,212 | Tight Fine-Grained Bounds for Direct Access on Join Queries | 2022 | PODS |
| 9 | 315 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS |
| 10 | 1,812 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS |