Sampling Big Ideas in Query Optimization

Summary: Survey of weighted and coordinated sampling methods for query optimization, using samples as concise summaries to scale complex analytics. Emphasizes simple, practical algorithms for streaming and distributed data that enable low‑overhead, coordinated estimates across queries and partitions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1933
Venue: PODS
Year: 2023
Pagerank: 5.4151005e-05
Overall Rank: 8,413 | 42.48%
DOI: 10.1145/3584372.3589935

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen (Google; Tel Aviv University)

BibTeX Citation

@inproceedings{cohen_pods23,
        address = {New York, NY, USA},
        series = {{PODS} '23},
        title = {{Sampling Big Ideas in Query Optimization}},
        url = {https://dl.acm.org/doi/10.1145/3584372.3589935},
        doi = {10.1145/3584372.3589935},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Edith},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,287	Sampling Methods for Inner Product Sketching	2024	VLDB	5.4346419e-05
8,824	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.3497363e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029118258
1,607	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.0001019774
2,799	All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis	2014	PODS	8.0881652e-05
3,498	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.3461408e-05
6,028	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	5.9903901e-05
7,674	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	5.5533023e-05
12,415	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	5.0723324e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,149	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB
2	149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
3	2,185	Optimal Sampling From Distributed Streams	2010	PODS
4	4,712	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB
5	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
6	7,369	Reservoir Sampling over Joins	2024	SIGMOD
7	7,449	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
8	54	On Random Sampling over Joins	1999	SIGMOD
9	5,220	Sampling Algorithms in a Stream Operator	2005	SIGMOD
10	174	Simple Random Sampling from Relational Databases	1986	VLDB