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: 2315
Venue: SIGMOD
Year: 1984
Pagerank: 0.00048351457
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 14 of 64 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,398	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB	6.2320592e-05
5,653	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	6.1332953e-05
5,789	Seiden: Revisiting Query Processing in Video Database Systems	2023	VLDB	6.0874367e-05
5,868	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	6.0613238e-05
6,061	VergeDB: A Database for IoT Analytics on Edge Devices	2021	CIDR	5.9910733e-05
6,590	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	5.8316635e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
7,443	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	5.6166792e-05
7,648	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	5.575838e-05
8,204	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4667903e-05
8,492	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.4145838e-05
8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.3355988e-05
11,700	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	5.093636e-05
13,224	Local and Global Query Optimization Mechanisms for Relational Databases	1985	VLDB	5.093636e-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.0024089429
417	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018819871
1,405	Top-down statistical estimation on a database	1983	SIGMOD	0.00010875661

Semantically Similar Papers

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