Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
Summary: Polynomial-time algorithm computes the polymatroid bound for simple degree constraints and produces a proof sequence to accelerate PANDA-based conjunctive query evaluation. Introduces a practical flow bound and discusses computational limits for extending to broader degree-constraint classes. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Sungjin Im
- 2. Benjamin Moseley
- 3. Hung Q. Ngo
- 4. Kirk Pruhs
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,149 | CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations | 2026 | SIGMOD | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 71 | How Good Are Query Optimizers, Really? | 2016 | VLDB | 0.00059446482 |
| 503 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021517145 |
| 1,452 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00011922523 |
| 2,143 | Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities | 2019 | SIGMOD | 9.4437798e-05 |
| 3,782 | Bag Query Containment and Information Theory | 2020 | PODS | 6.7691169e-05 |
| 5,978 | SafeBound: A Practical System for Generating Cardinality Bounds | 2023 | SIGMOD | 5.2424396e-05 |
| 6,822 | Computing Join Queries with Functional Dependencies | 2016 | PODS | 4.9101655e-05 |
| 6,967 | LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences | 2025 | SIGMOD | 4.875312e-05 |
| 7,337 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS | 4.7532633e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,978 | SafeBound: A Practical System for Generating Cardinality Bounds | 2023 | SIGMOD | 5.2424396e-05 |
| 6,094 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD | 5.2099705e-05 |
| 603 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019334592 |
| 3,516 | Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs | 2022 | VLDB | 7.018912e-05 |
| 7,337 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS | 4.7532633e-05 |
| 74 | Efficient Query Evaluation on Probabilistic Databases | 2004 | VLDB | 0.00057797415 |
| 8,972 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS | 4.4150824e-05 |
| 5,696 | Exact Cardinality Query Optimization with Bounded Execution Cost | 2019 | SIGMOD | 5.367449e-05 |
| 8,850 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4324268e-05 |
| 4,545 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0917464e-05 |