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.00036828234
Overall Rank
77 | 99.49%
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.00071084324
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052121228
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029627449
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028633995
179 The Vertica Analytic Database: C-Store 7 Years Later 2012 VLDB 0.00026611886
214 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00024656893
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022722971
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022509573
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021914399
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
519 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016942879
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016245271
655 Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies 1996 VLDB 0.00015070228
742 Dynamic Multidimensional Histograms 2002 SIGMOD 0.0001431602
745 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014288286
821 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013660347
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,242 Compressing SQL Workloads 2002 SIGMOD 0.00011373611
1,536 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010327422
1,720 A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data 2014 SIGMOD 9.7965659e-05
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5575424e-05
2,031 RainForest - A Framework for Fast Decision Tree Construction of Large Datasets 1998 VLDB 9.1572841e-05
2,162 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.935022e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6708797e-05
2,433 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4766785e-05
2,677 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 8.1461074e-05
2,776 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0309448e-05
2,987 Adapting to Source Properties in Processing Data Integration Queries 2004 SIGMOD 7.7773398e-05
3,090 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6584982e-05
3,131 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6141006e-05
3,211 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.536045e-05
3,213 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 7.5328015e-05
3,222 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 7.5135441e-05
3,272 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.4734096e-05
4,313 Density Biased Sampling: An Improved Method for Data Mining and Clustering 2000 SIGMOD 6.6699869e-05
4,330 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.6595681e-05
4,518 Arnold: Declarative Crowd-Machine Data Integration 2013 CIDR 6.5632796e-05
4,855 Efficiently Approximating Query Optimizer Plan Diagrams 2008 VLDB 6.3799739e-05
5,318 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1828476e-05
5,582 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 6.0768264e-05
5,656 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0488629e-05
5,698 Approximate Quantiles and the Order of the Stream 2006 PODS 6.0317949e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
6,168 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8627239e-05
6,880 Estimating the Impact of Unknown Unknowns on Aggregate Query Results 2016 SIGMOD 5.6573214e-05
7,429 Learning to be a Statistician: Learned Estimator for Number of Distinct Values 2022 VLDB 5.5300853e-05
7,510 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.5055437e-05
7,845 Automated design of multidimensional clustering tables for relational databases 2004 VLDB 5.4420146e-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.0023947656
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040035279
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030470848
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026389403
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS
2 103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB
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,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD
6 956 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,933 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD
9 267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB
10 295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS