DBScholar

Back to papers

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
hed41d0504ea8a160
Venue
VLDB
Year
1995
Pagerank
0.00036725074
Overall Rank
78 | 99.48%
DOI
-

Incoming Non-self Citations Over Time

Authors

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 50 of 60 citing papers.

Rank Citing Paper Year Venue Pagerank
11 Implementing Data Cubes Efficiently 1996 SIGMOD 0.00070860346
26 Models and Issues in Data Stream Systems 2002 PODS 0.00051942573
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047654188
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029532435
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
177 The Vertica Analytic Database: C-Store 7 Years Later 2012 VLDB 0.00026571747
214 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00024576033
259 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022881075
268 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022654182
296 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021874894
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016221103
660 Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies 1996 VLDB 0.00015022694
745 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014267268
750 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014246313
822 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013616674
1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012114187
1,246 Compressing SQL Workloads 2002 SIGMOD 0.00011355447
1,534 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010309919
1,721 A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data 2014 SIGMOD 9.7821782e-05
1,828 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5396315e-05
2,046 RainForest - A Framework for Fast Decision Tree Construction of Large Datasets 1998 VLDB 9.1229933e-05
2,176 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9031141e-05
2,310 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6493038e-05
2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4532693e-05
2,682 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 8.1203255e-05
2,777 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0101016e-05
3,001 Adapting to Source Properties in Processing Data Integration Queries 2004 SIGMOD 7.7492907e-05
3,093 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6378811e-05
3,136 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.5902303e-05
3,219 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.50928e-05
3,220 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 7.5077984e-05
3,235 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 7.4859375e-05
3,284 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.4455194e-05
4,329 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.64569e-05
4,331 Density Biased Sampling: An Improved Method for Data Mining and Clustering 2000 SIGMOD 6.644974e-05
4,537 Arnold: Declarative Crowd-Machine Data Integration 2013 CIDR 6.5399966e-05
4,876 Efficiently Approximating Query Optimizer Plan Diagrams 2008 VLDB 6.357646e-05
5,341 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1596655e-05
5,598 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 6.053914e-05
5,670 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0266818e-05
5,712 Approximate Quantiles and the Order of the Stream 2006 PODS 6.0096683e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
6,183 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8417594e-05
6,881 Estimating the Impact of Unknown Unknowns on Aggregate Query Results 2016 SIGMOD 5.6415853e-05
7,446 Learning to be a Statistician: Learned Estimator for Number of Distinct Values 2022 VLDB 5.5113049e-05
7,534 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.4849807e-05
7,838 Automated design of multidimensional clustering tables for relational databases 2004 VLDB 5.4264579e-05
Previous Page 1 / 2 Next

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.0023948467
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00039922419
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030398363
183 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026316699
Previous Page 1 / 1 Next

Semantically Similar Papers

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