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: 2253
Venue: SIGMOD
Year: 1984
Pagerank: 0.00080435857
Overall Rank: 28 | 99.81%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Gregory Piatetsky-Shapiro
2. Charles Connell

Incoming Citations (Sorted by Pagerank)

Showing 14 of 64 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,140	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	5.668209e-05
5,214	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	5.624434e-05
6,311	VergeDB: A Database for IoT Analytics on Edge Devices	2021	CIDR	5.1161316e-05
6,315	Seiden: Revisiting Query Processing in Video Database Systems	2023	VLDB	5.1142298e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8163484e-05
7,395	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	4.7420041e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
7,611	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	4.6964271e-05
7,928	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	4.613455e-05
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4275272e-05
9,621	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	4.3167167e-05
10,497	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.1945683e-05
11,502	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.1945683e-05
13,025	Local and Global Query Optimization Mechanisms for Relational Databases	1985	VLDB	4.1945683e-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.0040449103
228	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00032269684
615	Top-down statistical estimation on a database	1983	SIGMOD	0.00019128024

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8163484e-05
3,702	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8295759e-05
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
315	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.0002802103
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564