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
- 12659
- Venue
- VLDB
- Year
- 2022
- Pagerank
- 7.018912e-05
- Overall Rank
- 3,516 | 75.57%
- 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,781 |
Flow-Loss: Learning Cardinality Estimates That Matter |
2021 |
VLDB |
8.1282042e-05 |
| 4,466 |
Robust Join Processing with Diamond Hardened Joins |
2024 |
VLDB |
6.1545841e-05 |
| 5,978 |
SafeBound: A Practical System for Generating Cardinality Bounds |
2023 |
SIGMOD |
5.2424396e-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 |
| 8,035 |
Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores |
2025 |
VLDB |
4.5967078e-05 |
| 8,271 |
Adaptive Factorization Using Linear-Chained Hash Tables |
2025 |
CIDR |
4.539672e-05 |
| 8,274 |
Galley: Modern Query Optimization for Sparse Tensor Programs |
2025 |
SIGMOD |
4.5392079e-05 |
| 9,727 |
SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning |
2025 |
SIGMOD |
4.2901665e-05 |
| 9,845 |
Path-centric Cardinality Estimation for Subgraph Matching |
2025 |
VLDB |
4.2680295e-05 |
| 10,104 |
Query Optimization for Database-Returning Queries |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,372 |
Soft and Constrained Hypertree Width |
2025 |
PODS |
4.1905499e-05 |
| 10,455 |
LpBound in Action: Cardinality Estimation with One-Sided Guarantees |
2025 |
SIGMOD |
4.1905499e-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.00059446482 |
| 114 |
Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries |
1988 |
SIGMOD |
0.00046317654 |
| 141 |
Selectivity Estimation Without the Attribute Value Independence Assumption |
1997 |
VLDB |
0.00041819767 |
| 223 |
Wavelet-Based Histograms for Selectivity Estimation |
1998 |
SIGMOD |
0.00032829841 |
| 373 |
Selectivity Estimation using Probabilistic Models |
2001 |
SIGMOD |
0.00025354685 |
| 527 |
Self-tuning Histograms: Building Histograms Without Looking at Data |
1999 |
SIGMOD |
0.00020862475 |
| 941 |
Wander Join: Online Aggregation via Random Walks |
2016 |
SIGMOD |
0.00015147831 |
| 1,019 |
An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment |
1993 |
SIGMOD |
0.00014623543 |
| 1,045 |
Estimating the Selectivity of XML Path Expressions for Internet Scale Applications |
2001 |
VLDB |
0.00014451072 |
| 1,104 |
Cardinality Estimation Done Right: Index-Based Join Sampling |
2017 |
CIDR |
0.0001398479 |
| 1,194 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013411666 |
| 1,212 |
RDF-3X: a RISC-style Engine for RDF |
2008 |
VLDB |
0.00013255692 |
| 1,334 |
Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins |
2019 |
VLDB |
0.00012543633 |
| 1,756 |
Sampling-Based Query Re-Optimization |
2016 |
SIGMOD |
0.00010659753 |
| 2,143 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4437798e-05 |
| 2,322 |
Statistical Synopses for Graph-Structured XML Databases |
2002 |
SIGMOD |
9.0348397e-05 |
| 3,421 |
Approximate XML Query Answers |
2004 |
SIGMOD |
7.1107127e-05 |
| 3,644 |
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching |
2020 |
SIGMOD |
6.8842065e-05 |
| 5,642 |
Bloom Histogram: Path Selectivity Estimation for XML Data with Updates |
2004 |
VLDB |
5.3964761e-05 |
| 6,705 |
Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation |
2021 |
SIGMOD |
4.9507418e-05 |
| 6,822 |
Computing Join Queries with Functional Dependencies |
2016 |
PODS |
4.9101655e-05 |
| 8,573 |
PostCENN: PostgreSQL with Machine Learning Models for Cardinality Estimation |
2021 |
VLDB |
4.4885745e-05 |
Semantically Similar Papers