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
1622
Venue
PODS
Year
2014
Pagerank
9.975915e-05
Overall Rank
1,699 | 88.35%
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
321 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021283186
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
636 Answering Conjunctive Queries under Updates 2017 PODS 0.0001551856
1,246 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011504088
1,320 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011166426
1,740 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.875587e-05
1,857 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.6047945e-05
4,371 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.738679e-05
5,321 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.2659937e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
6,565 Tractability Beyond beta-Acyclicity for Conjunctive Queries with Negation 2021 PODS 5.8382688e-05
8,464 LogiQL: a Declarative Language for Enterprise Applications 2015 PODS 5.4198965e-05
8,598 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.4049137e-05
8,686 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.3849387e-05
8,698 SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms 2023 VLDB 5.3830073e-05
10,622 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 5.093636e-05
11,905 Efficient Exploration of Linked Data 2018 SIGMOD 5.093636e-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