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.00047864281
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.0004772731
57 On Random Sampling over Joins 1999 SIGMOD 0.00040095727
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036476265
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
115 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00031727517
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003136296
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026384065
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.0002378554
253 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023047482
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002251422
275 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022404363
284 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022205848
339 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020561716
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019822444
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
448 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00018121533
482 Query Optimization for XML 1999 VLDB 0.00017590408
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016938992
541 BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics 2020 VLDB 0.00016663833
644 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00015209065
785 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00013999898
806 Universality of Serial Histograms 1993 VLDB 0.00013786471
955 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.0001286095
1,004 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012588952
1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012524973
1,061 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012208639
1,065 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012202293
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010729775
1,574 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010190239
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8614576e-05
1,826 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5535288e-05
1,931 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.3511556e-05
1,960 StatiX: Making XML Count 2002 SIGMOD 9.3083244e-05
2,164 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9309999e-05
2,295 ThalamusDB: Approximate Query Processing on Multi-Modal Data 2024 SIGMOD 8.6822982e-05
2,455 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.4377251e-05
2,984 Optimizing Boolean Expressions in Object Bases 1992 VLDB 7.780464e-05
3,000 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7657164e-05
3,303 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.4400795e-05
3,361 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.3726415e-05
3,380 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.353368e-05
3,607 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.1645803e-05
3,756 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 7.0456217e-05
3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8874168e-05
4,076 Estimating Block Accesses When Attributes Are Correlated 1986 VLDB 6.8157153e-05
4,347 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.6457039e-05
4,511 A Blackboard Architecture for Query Optimization in Object Bases 1993 VLDB 6.5666591e-05
4,546 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5406658e-05
4,651 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.4836419e-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.0023943337
424 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018487052
1,429 Top-down statistical estimation on a database 1983 SIGMOD 0.00010690396
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 275 Optimal Histograms with Quality Guarantees 1998 VLDB
2 7,574 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS
3 3,132 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 284 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 867 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
9 491 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD
10 58 Statistical Estimators for Relational Algebra Expressions 1988 PODS