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

1. Gregory Piatetsky-Shapiro (New York University; Strategic Information)
2. Charles Connell (Boston University; Strategic Information)

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 16 of 66 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,933	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	6.3474817e-05
5,211	Seiden: Revisiting Query Processing in Video Database Systems	2023	VLDB	6.2253642e-05
5,525	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB	6.0940332e-05
5,985	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	5.926154e-05
6,189	VergeDB: A Database for IoT Analytics on Edge Devices	2021	CIDR	5.8568233e-05
6,694	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.7068014e-05
7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.5103311e-05
7,568	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	5.49478e-05
7,801	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	5.4507311e-05
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-05
8,659	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.2930951e-05
9,142	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.220581e-05
10,874	BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector	2026	VLDB	4.9793485e-05
10,909	Incremental Query Optimizer Statistics in Amazon Redshift	2026	VLDB	4.9793485e-05
12,005	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9793485e-05
13,514	Local and Global Query Optimization Mechanisms for Relational Databases	1985	VLDB	4.9793485e-05

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

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