Effective Use of Block-Level Sampling in Statistics Estimation

Summary: Block-level sampling is efficient but error-prone for statistics. Proposes a two-phase adaptive histogram algorithm using a phase-1 sample and a subset-extraction technique to adapt estimators to block-level distinct-value data; experiments show accuracy and speed gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hceca721f336d5413
Venue: SIGMOD
Year: 2004
Pagerank: 9.5575424e-05
Overall Rank: 1,826 | 87.73%
DOI: 10.1145/1007568.1007602

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Gautam Das (Microsoft)
3. Utkarsh Srivastava (Stanford University)

BibTeX Citation

@inproceedings{chaudhuri_sigmod04,
        title = {{Effective Use of Block-Level Sampling in Statistics Estimation}},
        author = {Chaudhuri, Surajit and Das, Gautam and Srivastava, Utkarsh},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007602},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007602},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
322	Tuning Database Configuration Parameters with iTuned	2009	VLDB	0.00021041865
888	Pay-as-you-go User Feedback for Dataspace Systems	2008	SIGMOD	0.00013255989
2,354	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.5896515e-05
3,145	Early Accurate Results for Advanced Analytics on MapReduce	2012	VLDB	7.5965257e-05
3,984	Data Canopy: Accelerating Exploratory Statistical Analysis	2017	SIGMOD	6.8741188e-05
4,069	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD	6.821366e-05
5,288	PolarDB-IMCI: A Cloud-Native HTAP Database System at Alibaba	2023	SIGMOD	6.1944376e-05
5,348	Adaptive and Robust Query Execution for Lakehouses at Scale	2024	VLDB	6.1690434e-05
5,745	Scalable Progressive Analytics on Big Data in the Cloud	2013	VLDB	6.0090513e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
5,985	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	5.926154e-05
6,967	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	5.6323307e-05
8,028	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	5.4041252e-05
8,331	LAQy: Efficient and Reusable Query Approximations via Lazy Sampling	2023	SIGMOD	5.3532622e-05
9,013	Learning-based Property Estimation with Polynomials	2024	SIGMOD	5.2375369e-05
11,192	PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models	2025	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020329113
492	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00017408001
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
2	2,456	A Sampling Algebra for Aggregate Estimation	2013	VLDB
3	12,596	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
4	5,534	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
5	267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB
6	519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD
7	9,849	Analysis and Application of Adaptive Sampling	2000	PODS
8	12,653	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS
9	77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB
10	295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS