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
- 13798
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.2656547e-05
- Overall Rank
- 9,877 | 31.29%
- 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.00059038975 |
| 331 |
The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing |
2018 |
VLDB |
0.00027214222 |
| 583 |
FAQ: Questions Asked Frequently |
2016 |
PODS |
0.00019717214 |
| 690 |
An Analytical Study of Large SPARQL Query Logs |
2018 |
VLDB |
0.00018099792 |
| 789 |
Cypher: An Evolving Query Language for Property Graphs |
2018 |
SIGMOD |
0.00016634256 |
| 1,193 |
Join Size Estimation Subject to Filter Conditions |
2015 |
VLDB |
0.00013414989 |
| 1,369 |
Random Sampling over Joins Revisited |
2018 |
SIGMOD |
0.00012339777 |
| 1,394 |
Real-time Constrained Cycle Detection in Large Dynamic Graphs |
2018 |
VLDB |
0.0001221552 |
| 1,703 |
Are We Ready For Learned Cardinality Estimation? |
2021 |
VLDB |
0.00010836769 |
| 1,924 |
In-Memory Subgraph Matching: An In-depth Study |
2020 |
SIGMOD |
0.00010077055 |
| 2,142 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4507296e-05 |
| 3,001 |
Neural Subgraph Counting with Wasserstein Estimator |
2022 |
SIGMOD |
7.7404487e-05 |
| 3,646 |
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching |
2020 |
SIGMOD |
6.8853079e-05 |
| 5,972 |
SafeBound: A Practical System for Generating Cardinality Bounds |
2023 |
SIGMOD |
5.2474768e-05 |
| 6,289 |
Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach |
2024 |
VLDB |
5.1275309e-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 |
| 11,306 |
Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality |
2023 |
VLDB |
4.1945683e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,417 |
Robust Query Driven Cardinality Estimation under Changing Workloads |
2023 |
VLDB |
6.2037371e-05 |
| 3,449 |
Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation |
2022 |
VLDB |
7.0824319e-05 |
| 2,142 |
Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities |
2019 |
SIGMOD |
9.4507296e-05 |
| 1,638 |
Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation |
2022 |
VLDB |
0.00011049779 |
| 3,646 |
G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching |
2020 |
SIGMOD |
6.8853079e-05 |
| 6,383 |
Sample-Efficient Cardinality Estimation Using Geometric Deep Learning |
2024 |
VLDB |
5.0884322e-05 |
| 10,149 |
CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations |
2026 |
SIGMOD |
4.1945683e-05 |
| 3,990 |
FactorJoin: A New Cardinality Estimation Framework for Join Queries |
2023 |
SIGMOD |
6.5581983e-05 |
| 3,511 |
Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs |
2022 |
VLDB |
7.0254052e-05 |
| 10,619 |
Data-Agnostic Cardinality Learning from Imperfect Workloads |
2025 |
VLDB |
4.1945683e-05 |