Back to papers
Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs
Summary: Analyzes two classes of summary-based cardinality estimators for graph DBMS: optimistic estimators with precomputed statistics and pessimistic LP-based estimators. Using Cardinality Estimation Graphs (CEGs), demonstrates that path choice (max vs min weight) depends on query structure, unifying optimistic and pessimistic approaches for cross-optimization.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 12658
- Venue
- VLDB
- Year
- 2022
- Pagerank
- 7.0254052e-05
- Overall Rank
- 3,511 | 75.58%
- DOI
-
10.14778/3529337.3529339
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 13 of 13 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,783 |
Flow-Loss: Learning Cardinality Estimates That Matter |
2021 |
VLDB |
8.1293383e-05 |
| 4,465 |
Robust Join Processing with Diamond Hardened Joins |
2024 |
VLDB |
6.1604282e-05 |
| 5,972 |
SafeBound: A Practical System for Generating Cardinality Bounds |
2023 |
SIGMOD |
5.2474768e-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 |
| 8,034 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.6010599e-05 |
| 8,275 |
Adaptive Factorization Using Linear-Chained Hash Tables |
2025 |
CIDR |
4.5439841e-05 |
| 8,279 |
Galley: Modern Query Optimization for Sparse Tensor Programs |
2025 |
SIGMOD |
4.5435639e-05 |
| 9,728 |
SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning |
2025 |
SIGMOD |
4.2942813e-05 |
| 9,845 |
Path-centric Cardinality Estimation for Subgraph Matching |
2025 |
VLDB |
4.2721228e-05 |
| 10,104 |
Query Optimization for Database-Returning Queries |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,360 |
Soft and Constrained Hypertree Width |
2025 |
PODS |
4.1945683e-05 |
| 10,445 |
LpBound in Action: Cardinality Estimation with One-Sided Guarantees |
2025 |
SIGMOD |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 22 of 22 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 |
| 116 |
Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries |
1988 |
SIGMOD |
0.00046148737 |
| 141 |
Selectivity Estimation Without the Attribute Value Independence Assumption |
1997 |
VLDB |
0.00041786333 |
| 222 |
Wavelet-Based Histograms for Selectivity Estimation |
1998 |
SIGMOD |
0.00032828302 |
| 372 |
Selectivity Estimation using Probabilistic Models |
2001 |
SIGMOD |
0.00025354779 |
| 529 |
Self-tuning Histograms: Building Histograms Without Looking at Data |
1999 |
SIGMOD |
0.00020828852 |
| 943 |
Wander Join: Online Aggregation via Random Walks |
2016 |
SIGMOD |
0.00015145883 |
| 1,020 |
An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment |
1993 |
SIGMOD |
0.00014624893 |
| 1,046 |
Estimating the Selectivity of XML Path Expressions for Internet Scale Applications |
2001 |
VLDB |
0.00014462307 |
| 1,105 |
Cardinality Estimation Done Right: Index-Based Join Sampling |
2017 |
CIDR |
0.00013990395 |
| 1,193 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013414989 |
| 1,213 |
RDF-3X: a RISC-style Engine for RDF |
2008 |
VLDB |
0.0001325231 |
| 1,333 |
Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins |
2019 |
VLDB |
0.00012523806 |
| 1,758 |
Sampling-Based Query Re-Optimization |
2016 |
SIGMOD |
0.00010655546 |
| 2,142 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4507296e-05 |
| 2,316 |
Statistical Synopses for Graph-Structured XML Databases |
2002 |
SIGMOD |
9.0419716e-05 |
| 3,419 |
Approximate XML Query Answers |
2004 |
SIGMOD |
7.1173416e-05 |
| 3,646 |
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching |
2020 |
SIGMOD |
6.8853079e-05 |
| 5,632 |
Bloom Histogram: Path Selectivity Estimation for XML Data with Updates |
2004 |
VLDB |
5.4014372e-05 |
| 6,704 |
Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation |
2021 |
SIGMOD |
4.9554912e-05 |
| 6,824 |
Computing Join Queries with Functional Dependencies |
2016 |
PODS |
4.9144789e-05 |
| 8,576 |
PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation |
2021 |
VLDB |
4.4927989e-05 |
Semantically Similar Papers