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.00024943236
Overall Rank
380 | 97.37%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 59 citing papers.

Rank Citing Paper Year Venue Pagerank
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072660894
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
627 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00018959896
737 On Synopses for Distinct-Value Estimation Under Multiset Operations 2007 SIGMOD 0.00017377393
917 Democratizing Data Science through Interactive Curation of ML Pipelines 2019 SIGMOD 0.00015324193
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011289028
1,683 Cardinality Estimation: An Experimental Survey 2018 VLDB 0.0001091276
1,756 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010659753
1,790 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 0.00010529479
1,970 Compressed Linear Algebra for Large-Scale Machine Learning 2016 VLDB 9.9024431e-05
2,177 A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data 2014 SIGMOD 9.371335e-05
2,269 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1507118e-05
2,424 The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing 2014 SIGMOD 8.8415494e-05
2,583 Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee 2016 SIGMOD 8.4973431e-05
2,779 Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries 2008 VLDB 8.1314377e-05
2,805 Query-Oriented Data Cleaning with Oracles 2015 SIGMOD 8.103731e-05
2,841 Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies 2009 VLDB 8.0396876e-05
2,881 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9671512e-05
3,013 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 7.7082045e-05
3,108 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.5547127e-05
3,123 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5270618e-05
3,133 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 7.4979168e-05
3,292 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2598265e-05
3,553 Approximate Selection with Guarantees using Proxies 2020 VLDB 6.9763548e-05
3,706 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 6.8232992e-05
3,827 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 6.7195959e-05
3,868 CORADD: Correlation Aware Database Designer for Materialized Views and Indexes 2010 VLDB 6.6786821e-05
4,621 Automated Generation of Materialized Views in Oracle 2020 VLDB 6.036749e-05
4,835 MNC: Structure-Exploiting Sparsity Estimation for Matrix Expressions 2019 SIGMOD 5.8861112e-05
5,012 Dynamically Optimizing Queries over Large Scale Data Platforms 2014 SIGMOD 5.7543101e-05
5,344 Efficiently Approximating Query Optimizer Plan Diagrams 2008 VLDB 5.5579641e-05
5,867 ABS: a System for Scalable Approximate Queries with Accuracy Guarantees 2014 SIGMOD 5.2933639e-05
5,907 Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA 2014 SIGMOD 5.2741214e-05
6,160 Compression Aware Physical Database Design 2011 VLDB 5.1750659e-05
6,194 Automatic Optimization of Matrix Implementations for Distributed Machine Learning and Linear Algebra 2021 SIGMOD 5.1592984e-05
6,277 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 5.1260947e-05
6,365 Pre-training Summarization Models of Structured Datasets for Cardinality Estimation 2022 VLDB 5.0892829e-05
6,372 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.0878306e-05
6,763 Robustness Metrics for Relational Query Execution Plans 2018 VLDB 4.9291549e-05
6,943 Estimating the Impact of Unknown Unknowns on Aggregate Query Results 2016 SIGMOD 4.8876509e-05
7,414 Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g 2008 SIGMOD 4.7312542e-05
7,611 Learning to be a Statistician: Learned Estimator for Number of Distinct Values 2022 VLDB 4.6920008e-05
7,666 Fast Detection of Denial Constraint Violations 2022 VLDB 4.6792751e-05
8,162 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 4.5686903e-05
8,345 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 4.5361313e-05
8,834 ByteCard: Enhancing ByteDance’s Data Warehouse with Learned Cardinality Estimation 2024 SIGMOD 4.4351469e-05
8,835 Learning-based Property Estimation with Polynomials 2024 SIGMOD 4.4351469e-05
8,893 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 4.4232868e-05
9,230 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 4.3650857e-05
Previous Page 1 / 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.

Previous Page 1 / 1 Next

Semantically Similar Papers