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: 3291
Venue: SIGMOD
Year: 2001
Pagerank: 8.0417349e-05
Overall Rank: 2,840 | 80.27%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026698826
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
1,239	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013091459
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
2,369	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9462051e-05
4,347	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2588401e-05
4,815	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	5.8978716e-05
5,588	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4193309e-05
6,485	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0386161e-05
8,314	Effective Change Detection Using Sampling	2002	VLDB	4.5392079e-05
8,440	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.505741e-05
8,471	Adaptive Index Structures	2002	VLDB	4.4986491e-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	Pagerank
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
8,602	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4822166e-05
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
2,995	A Sampling Algebra for Aggregate Estimation	2013	VLDB	7.7606324e-05
8,467	Sampling Big Ideas in Query Optimization	2023	PODS	4.4995247e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
8,345	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5361313e-05
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381