Applying the Golden Rule of Sampling for Query Estimation

Summary: Proposes a sampling method based on von Neumann's golden rule to estimate range-query size in databases. Randomly samples the frequency domain using the cumulative frequency distribution, with no prior distribution knowledge, delivering lower error than Min-Skew and wavelet baselines and scalable to higher dimensions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3352
Venue: SIGMOD
Year: 2001
Pagerank: 8.5070756e-05
Overall Rank: 2,493 | 82.90%
DOI: 10.1145/375663.375724

Incoming Non-self Citations Over Time

Authors

1. Yi-Leh Wu (University of California Santa Barbara)
2. Divyakant Agrawal (University of California Santa Barbara)
3. Amr El Abbadi (University of California Santa Barbara)

BibTeX Citation

@inproceedings{wu_sigmod01,
        title = {{Applying the Golden Rule of Sampling for Query Estimation}},
        author = {Wu, Yi-Leh and Agrawal, Divyakant and Abbadi, Amr El},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375724},
        url = {https://dl.acm.org/doi/10.1145/375663.375724},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.8181027e-05
4,405	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.7218674e-05
5,490	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.200262e-05
6,654	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.8131331e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
8,556	Effective Change Detection Using Sampling	2002	VLDB	5.4119882e-05
8,689	Adaptive Index Structures	2002	VLDB	5.3843737e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
2	173	Simple Random Sampling from Relational Databases	1986	VLDB
3	992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
4	36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD
5	7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
6	2,413	A Sampling Algebra for Aggregate Estimation	2013	VLDB
7	8,379	Sampling Big Ideas in Query Optimization	2023	PODS
8	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
9	8,183	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR
10	339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD