Sampling-Based Estimation of the Number of Distinct Values of an Attribute

Summary: Proposes several sampling-based estimators for the number of distinct values (NDV) of an attribute and empirically compares them on highly-skewed real-world data. Introduces a hybrid estimator that blends a smoothed jackknife with Shlosser's method, maximizing precision for given sampling fraction and scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8279
Venue: VLDB
Year: 1995
Pagerank: 0.00064450997
Overall Rank: 60 | 99.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 58 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11	Implementing Data Cubes Efficiently	1996	SIGMOD	0.0011695087
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072660894
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
247	On the Computation of Multidimensional Aggregates	1996	VLDB	0.00030923842
310	The Vertica Analytic Database: C-Store 7 Years Later	2012	VLDB	0.0002815547
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272747
600	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.00019400653
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
699	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.0001794078
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
1,443	Compressing SQL Workloads	2002	SIGMOD	0.00011944621
1,458	RainForest - A Framework for Fast Decision Tree Construction of Large Datasets	1998	VLDB	0.00011888676
1,683	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.0001091276
1,790	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	0.00010529479
2,054	Graph Cube: On Warehousing and OLAP Multidimensional Networks	2011	SIGMOD	9.682102e-05
2,056	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6692561e-05
2,177	A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data	2014	SIGMOD	9.371335e-05
2,844	Selectivity Estimation in Extensible Databases - A Neural Network Approach	1998	VLDB	8.0308994e-05
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7082045e-05
3,108	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5547127e-05
3,123	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.5270618e-05
3,133	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	7.4979168e-05
3,331	Adapting to Source Properties in Processing Data Integration Queries	2004	SIGMOD	7.2094696e-05
3,553	Approximate Selection with Guarantees using Proxies	2020	VLDB	6.9763548e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
3,808	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	6.7416988e-05
3,827	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7195959e-05
4,024	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5177066e-05
4,177	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.3768049e-05
4,181	Arnold: Declarative Crowd-Machine Data Integration	2013	CIDR	6.3725128e-05
4,835	MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions	2019	SIGMOD	5.8861112e-05
5,119	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6774637e-05
5,344	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB	5.5579641e-05
5,742	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	5.3432178e-05
5,967	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.247088e-05
6,277	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1260947e-05
6,943	Estimating the Impact of Unknown Unknowns on Aggregate Query Results	2016	SIGMOD	4.8876509e-05
7,414	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	4.7312542e-05
7,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-05
7,591	Automated design of multidimensional clustering tables for relational databases	2004	VLDB	4.6986414e-05
7,611	Learning to be a Statistician: Learned Estimator for Number of Distinct Values	2022	VLDB	4.6920008e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
133	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00043220055
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
1,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
1,790	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	0.00010529479
896	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00015486851
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
5,066	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	5.7157182e-05
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236