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.0010828372 |
| 411 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00018902089 |
| 414 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00018893507 |
| 673 | Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants | 2007 | PODS | 0.00015095061 |
| 3,617 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS | 7.2557398e-05 |
| 7,052 | The Parameterized Complexity of Database Queries | 2001 | PODS | 5.7171307e-05 |
| 7,053 | Connections in Acyclic Hypergraphs -- Extended Abstract | 1982 | PODS | 5.7171307e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 10,652 | Smallest Synthetic Witnesses for Conjunctive Queries | 2025 | PODS |
| 2 | 7,286 | Efficient Computation of Quantiles over Joins | 2023 | PODS |
| 3 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 4 | 7,451 | The Complexity of Boolean Conjunctive Queries with Intersection Joins | 2022 | PODS |
| 5 | 3,941 | Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins | 2023 | PODS |
| 6 | 411 | Worst-case Optimal Join Algorithms | 2012 | PODS |
| 7 | 3,724 | Overlap Set Similarity Joins with Theoretical Guarantees | 2018 | SIGMOD |
| 8 | 8,047 | Tight Fine-Grained Bounds for Direct Access on Join Queries | 2022 | PODS |
| 9 | 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS |
| 10 | 1,857 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS |