DBScholar

Back to papers

G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching

Summary: Introduces G-CARE, a unified framework to realize and benchmark all existing cardinality-estimation techniques for subgraph matching on graph and relational DBs. Evaluation on RDF and non-RDF graphs shows widespread inaccuracies in prior methods; a simple online-aggregation sampling approach consistently outperforms them. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h3c01fbbd52f83660
Venue
SIGMOD
Year
2020
Pagerank
7.9698957e-05
Overall Rank
2,824 | 81.02%
DOI
10.1145/3318464.3389702

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{park_sigmod20,
        title = {{G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching}},
        author = {Park, Yeonsu and Ko, Seongyun and Bhowmick, Sourav S and Kim, Kyoungmin and Hong, Kijae and Han, Wook-Shin},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389702},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389702},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
982 Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation 2022 VLDB 0.00012714044
2,014 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1832045e-05
2,634 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1993804e-05
2,846 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9453616e-05
2,974 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7938744e-05
3,160 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5807496e-05
4,123 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7927568e-05
5,422 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1361195e-05
5,901 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9539374e-05
6,045 PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration 2021 SIGMOD 5.9054678e-05
6,469 Cardinality Estimation over Knowledge Graphs with Embeddings and Graph Neural Networks 2024 SIGMOD 5.7743636e-05
6,818 ASM: Harmonizing Autoregressive Model, Sampling, and Multi-dimensional Statistics Merging for Cardinality Estimation 2024 SIGMOD 5.672718e-05
8,682 Galley: Modern Query Optimization for Sparse Tensor Programs 2025 SIGMOD 5.2905577e-05
8,891 Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds 2025 VLDB 5.2559789e-05
9,650 gSWORD: GPU-accelerated Sampling for Subgraph Counting 2024 SIGMOD 5.1453267e-05
10,057 SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning 2025 SIGMOD 5.0875952e-05
10,184 Path-centric Cardinality Estimation for Subgraph Matching 2025 VLDB 5.0651993e-05
10,215 Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation 2025 VLDB 5.0584922e-05
10,253 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.050482e-05
10,675 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 4.9793485e-05
10,740 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 4.9793485e-05
10,882 Efficient GPU-Accelerated Local Subgraph Counting 2026 VLDB 4.9793485e-05
11,186 Rule-Based Graph Cleaning with GPUs on a Single Machine 2025 SIGMOD 4.9793485e-05
11,312 X-Blossom: Massive Parallelization of Graph Maximum Matching 2025 VLDB 4.9793485e-05
11,546 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 27 of 27 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061066921
236 LinkBench: a Database Benchmark Based on the Facebook Social Graph 2013 SIGMOD 0.00023671522
239 The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018 VLDB 0.000235107
376 Scalable Semantic Web Data Management Using Vertical Partitioning 2007 VLDB 0.00019626699
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019444411
387 The LDBC Social Network Benchmark: Interactive Workload 2015 SIGMOD 0.00019426275
438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018286607
481 Robust Query Processing through Progressive Optimization 2004 SIGMOD 0.00017603972
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016726545
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015785583
750 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014265196
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013938779
860 G-CORE: A Core for Future Graph Query Languages 2018 SIGMOD 0.00013406849
954 RDF-3X: a RISC-style Engine for RDF 2008 VLDB 0.00012867202
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011627329
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010576304
1,542 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010308631
1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.9088372e-05
1,907 An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing 2017 VLDB 9.397856e-05
3,390 Experimental Analysis of Streaming Algorithms for Graph Partitioning 2019 SIGMOD 7.3509644e-05
3,506 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 7.2501249e-05
4,068 Beyond Macrobenchmarks: Microbenchmark-based Graph Database Evaluation 2019 VLDB 6.8215122e-05
4,795 Calibrating the Query Optimizer Cost Model of IRO-DB, an Object-Oriented Federated Database System 1996 VLDB 6.4123869e-05
7,286 Experimental Analysis of Distributed Graph Systems 2018 VLDB 5.565865e-05
8,735 RBench: Application-Specific RDF Benchmarking 2015 SIGMOD 5.2905469e-05
8,831 Graph Data Models, Query Languages and Programming Paradigms 2018 VLDB 5.2681194e-05
Previous Page 1 / 1 Next

Semantically Similar Papers