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.00011383141
Overall Rank: 1,556 | 89.19%
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
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
1,948	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9938634e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05
5,049	High-Performance Row Pattern Recognition Using Joins	2023	VLDB	5.7275467e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
6,625	Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation	2021	PODS	4.9841228e-05
8,350	LogiQL: a Declarative Language for Enterprise Applications	2015	PODS	4.5342845e-05
8,470	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	4.4993203e-05
8,772	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	4.451034e-05
10,336	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1905499e-05
10,639	Is Integer Linear Programming All You Need for Deletion Propagation?	2025	VLDB	4.1905499e-05
11,706	Efficient Exploration of Linked Data	2018	SIGMOD	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
623	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018976192
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
6,238	The Parameterized Complexity of Database Queries	2001	PODS	5.1369162e-05
6,239	Connections in Acyclic Hypergraphs -- Extended Abstract	1982	PODS	5.1369162e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,500	Ranked Enumeration of Minimal Triangulations	2019	PODS	4.7135369e-05
10,371	Smallest Synthetic Witnesses for Conjunctive Queries	2025	PODS	4.1905499e-05
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
7,328	The Complexity of Boolean Conjunctive Queries with Intersection Joins	2022	PODS	4.7560344e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
4,350	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.2576191e-05
8,029	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.598451e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05