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

Summary: Introduces sampling estimators for attribute cardinality, including a skew-aware hybrid combining smoothed jackknife and Shlosser methods. First broad empirical comparison on highly skewed real database distributions; hybrid achieves best average precision. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8469
Venue: VLDB
Year: 1995
Pagerank: 0.00037277061
Overall Rank: 75 | 99.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Peter J. Haas (IBM)
2. Jeffrey F. Naughton (University of Wisconsin)
3. S. Seshadri (Indian Institute of Technology)
4. Lynne Stokes (University of Texas)

BibTeX Citation

@article{haas_vldb95,
        title = {{Sampling-Based Estimation of the Number of Distinct Values of an Attribute}},
        author = {Haas, Peter J. and Naughton, Jeffrey F. and Seshadri, S. and Stokes, Lynne},
        journal = {PVLDB},
        series = {{VLDB} '95},
        pages = {311},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 59 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,556	Effective Change Detection Using Sampling	2002	VLDB	5.4119882e-05
9,206	A Data Quality Metric (DQM): How to Estimate the Number of Undetected Errors in Data Sets	2017	VLDB	5.3058708e-05
9,392	A Step Toward Deep Online Aggregation	2023	SIGMOD	5.2755515e-05
10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS	5.093636e-05
10,515	Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries	2026	VLDB	5.093636e-05
10,774	PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models	2025	SIGMOD	5.093636e-05
10,806	AdaNDV: Adaptive Number of Distinct Value Estimation via Learning to Select and Fuse Estimators	2025	VLDB	5.093636e-05
12,258	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	5.093636e-05
12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS	5.093636e-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.0024089429
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026881845

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB
2	1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS
3	36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD
4	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
5	1,806	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD
6	934	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB
7	55	Statistical Estimators for Relational Algebra Expressions	1988	PODS
8	4,846	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD
9	255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB
10	288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS