Back to papers
Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation
Summary: COLOR uses graph coloring and compression to produce compact topology-aware summaries for subgraph cardinality estimation in many-to-many join graph queries. Key optimizations make estimation tractable and yield up to 103× accuracy gains while keeping memory small, inference fast, builds cheap, and updates graceful.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 13799
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.2615675e-05
- Overall Rank
- 9,876 | 31.37%
- DOI
-
10.14778/3705829.3705834
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 17 of 17 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 |
| 327 |
The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing |
2018 |
VLDB |
0.00027312381 |
| 564 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00020002796 |
| 657 |
An Analytical Study of Large SPARQL Query Logs |
2018 |
VLDB |
0.00018581389 |
| 787 |
Cypher: An Evolving Query Language for Property Graphs |
2018 |
SIGMOD |
0.00016624372 |
| 1,194 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013411666 |
| 1,372 |
Random Sampling over Joins Revisited |
2018 |
SIGMOD |
0.0001233325 |
| 1,392 |
Real-time Constrained Cycle Detection in Large Dynamic Graphs |
2018 |
VLDB |
0.00012224015 |
| 1,699 |
Are We Ready For Learned Cardinality Estimation? |
2021 |
VLDB |
0.00010848882 |
| 1,906 |
In-Memory Subgraph Matching: An In-depth Study |
2020 |
SIGMOD |
0.00010135267 |
| 2,143 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4437798e-05 |
| 2,988 |
Neural Subgraph Counting with Wasserstein Estimator |
2022 |
SIGMOD |
7.7752463e-05 |
| 3,644 |
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching |
2020 |
SIGMOD |
6.8842065e-05 |
| 5,978 |
SafeBound: A Practical System for Generating Cardinality Bounds |
2023 |
SIGMOD |
5.2424396e-05 |
| 6,288 |
Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach |
2024 |
VLDB |
5.1226099e-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 |
| 11,308 |
Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality |
2023 |
VLDB |
4.1905499e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,413 |
Robust Query Driven Cardinality Estimation under Changing Workloads |
2023 |
VLDB |
6.1989918e-05 |
| 3,455 |
Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation |
2022 |
VLDB |
7.0760196e-05 |
| 2,143 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4437798e-05 |
| 1,638 |
Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation |
2022 |
VLDB |
0.00011050093 |
| 3,644 |
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching |
2020 |
SIGMOD |
6.8842065e-05 |
| 6,382 |
Sample-Efficient Cardinality Estimation Using Geometric Deep Learning |
2024 |
VLDB |
5.0835686e-05 |
| 10,149 |
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations |
2026 |
SIGMOD |
4.1905499e-05 |
| 3,992 |
FactorJoin: A New Cardinality Estimation Framework for Join Queries |
2023 |
SIGMOD |
6.5519369e-05 |
| 3,516 |
Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs |
2022 |
VLDB |
7.018912e-05 |
| 10,627 |
Data-Agnostic Cardinality Learning from Imperfect Workloads |
2025 |
VLDB |
4.1905499e-05 |