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: 2254
Venue: SIGMOD
Year: 1984
Pagerank: 0.00080571183
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,141	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	5.6627467e-05
5,206	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	5.625641e-05
6,306	Seiden: Revisiting Query Processing in Video Database Systems	2023	VLDB	5.1146055e-05
6,311	VergeDB: A Database for IoT Analytics on Edge Devices	2021	CIDR	5.1112212e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
7,392	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	4.737456e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
7,612	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	4.6919232e-05
7,911	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	4.6143141e-05
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05
9,238	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.3648789e-05
9,621	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	4.3125802e-05
11,506	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.1905499e-05
13,036	Local and Global Query Optimization Mechanisms for Relational Databases	1985	VLDB	4.1905499e-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.0040465394
226	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.0003243274
613	Top-down statistical estimation on a database	1983	SIGMOD	0.00019104493

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
3,706	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR	6.8232992e-05
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
360	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025768448
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
291	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00028778973
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514