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.1945683e-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.00059038975 |
| 502 | Worst-case Optimal Join Algorithms | 2012 | PODS | 0.00021526612 |
| 1,442 | What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? | 2017 | PODS | 0.00011956109 |
| 2,142 | Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities | 2019 | SIGMOD | 9.4507296e-05 |
| 3,775 | Bag Query Containment and Information Theory | 2020 | PODS | 6.775636e-05 |
| 5,972 | SafeBound: A Practical System for Generating Cardinality Bounds | 2023 | SIGMOD | 5.2474768e-05 |
| 6,824 | Computing Join Queries with Functional Dependencies | 2016 | PODS | 4.9144789e-05 |
| 6,969 | LpBound: Pessimistic Cardinality Estimation using ℓp-Norms of Degree Sequences | 2025 | SIGMOD | 4.8799937e-05 |
| 7,344 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS | 4.7565607e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,090 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD | 5.2148332e-05 |
| 5,972 | SafeBound: A Practical System for Generating Cardinality Bounds | 2023 | SIGMOD | 5.2474768e-05 |
| 602 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019352415 |
| 3,511 | Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs | 2022 | VLDB | 7.0254052e-05 |
| 7,344 | Join Size Bounds using l_p-Norms on Degree Sequences | 2024 | PODS | 4.7565607e-05 |
| 74 | Efficient Query Evaluation on Probabilistic Databases | 2004 | VLDB | 0.00057857292 |
| 8,966 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS | 4.4193184e-05 |
| 5,685 | Exact Cardinality Query Optimization with Bounded Execution Cost | 2019 | SIGMOD | 5.3717535e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 4,546 | Bounded Conjunctive Queries | 2014 | VLDB | 6.0987778e-05 |