Database Paper Browser

Back to papers

Towards Estimation Error Guarantees for Distinct Values

Summary: Prove any sublinear-sample estimator for distinct counts must suffer large error on some natural distributions unless it reads a large fraction of the data. Give an estimator matching this lower bound and practical heuristics for typical distributions, validated empirically. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1217
Venue
PODS
Year
2000
Pagerank
0.0002497492
Overall Rank
378 | 97.38%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 59 citing papers.

Rank Citing Paper Year Venue Pagerank
10,012 A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables 2026 SIGMOD 4.1945683e-05
10,227 Sample-based Distinct Cardinality Estimation for Multiple Attributes in Multi-Dataset Queries 2026 VLDB 4.1945683e-05
10,498 PLM4NDV: Minimizing Data Access for Number of Distinct Values Estimation with Pre-trained Language Models 2025 SIGMOD 4.1945683e-05
10,534 AdaNDV: Adaptive Number of Distinct Value Estimation via Learning to Select and Fuse Estimators 2025 VLDB 4.1945683e-05
10,639 Cardinality Estimation for Having-Clauses 2025 VLDB 4.1945683e-05
10,935 Automated Clustering Recommendation With Database Zone Maps 2024 SIGMOD 4.1945683e-05
12,108 Space-Efficient Estimation of Statistics over Sub-Sampled Streams 2012 PODS 4.1945683e-05
12,531 Join-Distinct Aggregate Estimation over Update Streams 2005 PODS 4.1945683e-05
12,626 Estimating the Output Cardinality of Partial Preaggregation with a Measure of Clusteredness 2003 VLDB 4.1945683e-05
Previous Page 2 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
59 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064501896
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
134 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00042452811
237 An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server 1997 VLDB 0.00031726304
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,835 Learning-based Property Estimation with Polynomials 2024 SIGMOD 4.4394021e-05
3,702 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 6.8295759e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4275272e-05
12,166 Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information 2011 PODS 4.1945683e-05
6,244 Approximate Distinct Counts for Billions of Datasets 2019 SIGMOD 5.139669e-05
727 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00017508726
308 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00028142852
7,610 Learning to be a Statistician: Learned Estimator for Number of Distinct Values 2022 VLDB 4.6965039e-05
1,797 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 0.00010523169
59 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064501896