Learning to Sample: Counting with Complex Queries

Summary: Two-phase learning-to-sample: sample to train a classifier, then guide stratified counting for complex queries. Theory derives optimal stratification; empirically compares against quantification and weighted/stratified sampling across real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12431
Venue: VLDB
Year: 2020
Pagerank: 5.7178054e-05
Overall Rank: 7,048 | 51.65%
DOI: 10.14778/3368289.3368302

Incoming Non-self Citations Over Time

Authors

1. Brett Walenz (Duke University)
2. Stavros Sintos (Duke University)
3. Sudeepa Roy (Duke University)
4. Jun Yang (Duke University)

BibTeX Citation

@article{walenz_vldb20,
        title = {{Learning to Sample: Counting with Complex Queries}},
        author = {Walenz, Brett and Sintos, Stavros and Roy, Sudeepa and Yang, Jun},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {3},
        pages = {389--401},
        doi = {10.14778/3368289.3368302},
        url = {https://doi.org/10.14778/3368289.3368302},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,907	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB	7.0278233e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,576	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.8364729e-05
8,124	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD	5.4829513e-05
9,626	Spatial Query Optimization With Learning	2024	VLDB	5.2434488e-05
10,760	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00077458002
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00022238183
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
568	SageDB: A Learned Database System	2019	CIDR	0.0001641553
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
1,736	A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data	2014	SIGMOD	9.8984415e-05
3,945	Exploiting Correlations for Expensive Predicate Evaluation	2015	SIGMOD	7.0055154e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	484	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD
2	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
3	6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
4	3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
5	10,186	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD
6	1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD
7	7,335	Reservoir Sampling over Joins	2024	SIGMOD
8	9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD
9	1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB
10	55	Statistical Estimators for Relational Algebra Expressions	1988	PODS