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.7545941e-05
Overall Rank
1,734 | 88.38%
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
318 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021178303
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
639 Answering Conjunctive Queries under Updates 2017 PODS 0.00015289346
1,253 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011316982
1,296 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011119184
1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010090639
1,821 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5466386e-05
4,487 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5628751e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
5,469 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1022571e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
6,707 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 5.6859798e-05
8,658 LogiQL: a Declarative Language for Enterprise Applications 2015 PODS 5.2786293e-05
8,788 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.263678e-05
8,872 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.2459616e-05
8,881 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.2442249e-05
11,138 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9605343e-05
12,254 Efficient Exploration of Linked Data 2018 SIGMOD 4.9605343e-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