DBScholar

Back to papers

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
h81f6b51ef7581a23
Venue
PODS
Year
2014
Pagerank
9.7857214e-05
Overall Rank
1,726 | 88.41%
DOI
10.1145/259438.2594547

Incoming Non-self Citations Over Time

Authors

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.

Rank Citing Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021236408
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015334386
1,252 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011334813
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011147959
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
1,813 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5759542e-05
4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.584648e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
5,454 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1225019e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
6,692 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 5.7048435e-05
8,639 LogiQL: a Declarative Language for Enterprise Applications 2015 PODS 5.2961325e-05
8,769 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.2811408e-05
8,860 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.2620362e-05
8,862 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.2616231e-05
11,077 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9769913e-05
12,211 Efficient Exploration of Linked Data 2018 SIGMOD 4.9769913e-05
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.

Previous Page 1 / 1 Next

Semantically Similar Papers