DBScholar

Back to papers

CS2: A New Database Synopsis for Query Estimation

Summary: CS2 proposes Correlated Sample Synopsis for accurate join and selection estimation using correlated samples to preserve join structure with storage. Introduces reverse sampling and a reverse estimator; unbiased, competitive with baselines at the same space. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h227a3046622f5446
Venue
SIGMOD
Year
2013
Pagerank
9.4150583e-05
Overall Rank
1,892 | 87.29%
DOI
10.1145/2463676.2463701

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{yu_sigmod13,
        title = {{CS2: A New Database Synopsis for Query Estimation}},
        author = {Yu, Feng and Hou, Wen-Chi and Luo, Cheng and Che, Dunren and Zhu, Mengxia},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2463701},
        url = {https://dl.acm.org/doi/10.1145/2463676.2463701},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
15 How Good Are Query Optimizers, Really? 2016 VLDB 0.00061067652
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014749318
749 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014261044
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013934719
1,997 Track Join: Distributed Joins with Minimal Network Traffic 2014 SIGMOD 9.2126022e-05
3,208 Efficiently Approximating Selectivity Functions using Low Overhead Regression Models 2020 VLDB 7.5355264e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2548566e-05
4,330 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.6564176e-05
5,006 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.3159614e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
8,042 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.3999898e-05
8,351 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.3480813e-05
11,135 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.9769913e-05
11,298 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023943337
32 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00049714561
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040025054
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036476265
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003136296
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029618887
169 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00027126333
242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023354266
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020320726
471 Robust Query Processing through Progressive Optimization 2004 SIGMOD 0.00017744392
535 Optimizing the Performance of a Relational Algebra Database Interface 1975 SIGMOD 0.00016782455
700 Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data 2001 SIGMOD 0.00014675903
726 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.00014459508
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012588952
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011543634
2,537 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD 8.3249336e-05
3,852 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9756022e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,132 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
2 11,957 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD
3 153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD
4 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
5 749 Join Size Estimation Subject to Filter Conditions 2015 VLDB
6 346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD
7 1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
8 1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS
9 58 Statistical Estimators for Relational Algebra Expressions 1988 PODS
10 1,184 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD