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: 3290
Venue: SIGMOD
Year: 2001
Pagerank: 8.0448428e-05
Overall Rank: 2,835 | 80.28%
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.00026702512
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
1,254	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00013027411
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
4,350	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2645054e-05
4,831	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	5.8924198e-05
5,579	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	5.4245689e-05
6,491	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0429323e-05
8,320	Effective Change Detection Using Sampling	2002	VLDB	4.5435639e-05
8,448	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.5100508e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-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.00036625711
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
8,605	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4865144e-05
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
2,995	A Sampling Algebra for Aggregate Estimation	2013	VLDB	7.7587199e-05
8,470	Sampling Big Ideas in Query Optimization	2023	PODS	4.5038423e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745