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)

Paper ID: 1623
Venue: PODS
Year: 2014
Pagerank: 0.00011392493
Overall Rank: 1,557 | 89.17%
DOI: 10.1145/259438.2594547

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 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,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05
5,059	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	5.7277656e-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,626	Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation	2021	PODS	4.9889109e-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
8,775	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	4.4553047e-05
10,324	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1945683e-05
10,631	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1945683e-05
11,701	Efficient Exploration of Linked Data	2018	SIGMOD	4.1945683e-05

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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
6,239	The Parameterized Complexity of Database Queries	2001	PODS	5.1417208e-05
6,240	Connections in Acyclic Hypergraphs -- Extended Abstract	1982	PODS	5.1417208e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,501	Ranked Enumeration of Minimal Triangulations	2019	PODS	4.7180617e-05
10,359	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1945683e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
7,332	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7606012e-05
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
4,353	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.263585e-05
8,028	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.6028646e-05
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05