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.00036817139
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.00071056708
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052097907
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.0004772731
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029618887
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028621958
178 The Vertica Analytic Database: C-Store 7 Years Later 2012 VLDB 0.00026620521
214 On the Computation of Multidimensional Aggregates 1996 VLDB 0.00024650285
267 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00022713652
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002251422
295 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00021908194
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
429 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018445263
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016938992
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016244162
656 Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies 1996 VLDB 0.0001506436
743 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014309723
746 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014282427
821 Query Execution Techniques for Caching Expensive Methods 1996 SIGMOD 0.00013655214
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
1,244 Compressing SQL Workloads 2002 SIGMOD 0.00011369155
1,537 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.00010324934
1,722 A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data 2014 SIGMOD 9.7921604e-05
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5535288e-05
2,034 RainForest - A Framework for Fast Decision Tree Construction of Large Datasets 1998 VLDB 9.152958e-05
2,164 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9309999e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6685874e-05
2,432 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4742372e-05
2,672 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 8.1456115e-05
2,773 Approximate Selection with Guarantees using Proxies 2020 VLDB 8.0318294e-05
2,989 Adapting to Source Properties in Processing Data Integration Queries 2004 SIGMOD 7.7736772e-05
3,092 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6548729e-05
3,132 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 7.6107287e-05
3,212 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5324957e-05
3,213 Turbo-Charging Estimate Convergence in DBO 2009 VLDB 7.5304969e-05
3,224 Graph Cube: On Warehousing and OLAP Multidimensional Networks 2011 SIGMOD 7.5099873e-05
3,273 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.469873e-05
4,314 Density Biased Sampling: An Improved Method for Data Mining and Clustering 2000 SIGMOD 6.6668377e-05
4,330 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 6.6564176e-05
4,519 Arnold: Declarative Crowd-Machine Data Integration 2013 CIDR 6.5602428e-05
4,857 Efficiently Approximating Query Optimizer Plan Diagrams 2008 VLDB 6.3772435e-05
5,325 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1799938e-05
5,583 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 6.0739524e-05
5,658 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0460211e-05
5,701 Approximate Quantiles and the Order of the Stream 2006 PODS 6.0289493e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
6,169 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8600493e-05
6,885 Estimating the Impact of Unknown Unknowns on Aggregate Query Results 2016 SIGMOD 5.6546466e-05
7,426 Learning to be a Statistician: Learned Estimator for Number of Distinct Values 2022 VLDB 5.5295692e-05
7,515 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 5.5029699e-05
7,849 Automated design of multidimensional clustering tables for relational databases 2004 VLDB 5.4395228e-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.0023943337
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040025054
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030462671
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026384065
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,203 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,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD
6 955 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,936 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