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.7902443e-05
Overall Rank
1,725 | 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.00021246
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015341557
1,249 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011340141
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011152286
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
1,812 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5803973e-05
4,463 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5877664e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
5,449 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1254016e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
6,688 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 5.7075454e-05
8,631 LogiQL: a Declarative Language for Enterprise Applications 2015 PODS 5.2986408e-05
8,761 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.283642e-05
8,850 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.2645282e-05
8,852 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.2641151e-05
11,068 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9793485e-05
12,205 Efficient Exploration of Linked Data 2018 SIGMOD 4.9793485e-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