DBScholar

Back to papers

Accurate Estimation Of The Number Of Tuples Satisfying A Condition

Summary: Introduces distribution steps: histograms with equal-height buckets to bound selectivity error for predicates rel op constant. Increasing steps lowers error; derives worst-case and average-case estimation formulas, plus fast sampling-based construction; targets query optimization and statistical queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hb17a1ef3414506c9
Venue
SIGMOD
Year
1984
Pagerank
0.00047863192
Overall Rank
36 | 99.76%
DOI
10.1145/602259.602294

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{piatetskyshapiro_sigmod84,
        title = {{ACCURATE ESTIMATION OF THE NUMBER OF TUPLES SATISFYING A CONDITION}},
        author = {Piatetsky-Shapiro, Gregory and Connell, Charles},
        series = {{SIGMOD} '84},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/602259.602294},
        url = {https://dl.acm.org/doi/10.1145/602259.602294},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 66 citing papers.

Rank Citing Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
57 On Random Sampling over Joins 1999 SIGMOD 0.00040108301
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036487763
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
115 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00031742473
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003137356
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026389403
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023792809
252 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023050233
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022509573
275 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022413521
283 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022214789
341 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020539791
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019829769
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
448 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00018129161
482 Query Optimization for XML 1999 VLDB 0.00017598607
519 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016942879
541 BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics 2020 VLDB 0.00016657685
646 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.0001520859
785 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00014005637
806 Universality of Serial Histograms 1993 VLDB 0.00013792174
956 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00012865801
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012594522
1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012529816
1,064 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202282
1,082 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012122749
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010734049
1,574 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010194928
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8655879e-05
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5575424e-05
1,929 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3546057e-05
1,960 StatiX: Making XML Count 2002 SIGMOD 9.3125715e-05
2,162 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.935022e-05
2,450 ThalamusDB: Approximate Query Processing on Multi-Modal Data 2024 SIGMOD 8.4474092e-05
2,456 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.4377192e-05
2,983 Optimizing Boolean Expressions in Object Bases 1992 VLDB 7.7839431e-05
3,005 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7621043e-05
3,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4424817e-05
3,361 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3760492e-05
3,379 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.3568458e-05
3,613 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.162283e-05
3,874 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 6.953738e-05
3,967 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8905715e-05
4,078 Estimating Block Accesses When Attributes Are Correlated 1986 VLDB 6.8185552e-05
4,346 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.6488514e-05
4,510 A Blackboard Architecture for Query Optimization in Object Bases 1993 VLDB 6.5696737e-05
4,546 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5436884e-05
4,648 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.4867043e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
422 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018492336
1,429 Top-down statistical estimation on a database 1983 SIGMOD 0.00010693006
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 275 Optimal Histograms with Quality Guarantees 1998 VLDB
2 7,568 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS
3 3,131 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
4 806 Universality of Serial Histograms 1993 VLDB
5 242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
6 283 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD
7 448 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB
8 866 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
9 492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD
10 58 Statistical Estimators for Relational Algebra Expressions 1988 PODS