The Power of Sampling in Knowledge Discovery

Summary: Approximates truth of tuple-relational-calculus sentences by random sampling, introducing two error measures for universal sentences. Gives near-tight sample-size bounds to catch all n k-quantifier universals with error ≥ ε: O((log n)/ε) or O(|M|^{1-1/k}·log n/ε), and extends to universal–existential cases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1019
Venue: PODS
Year: 1994
Pagerank: 6.323083e-05
Overall Rank: 4,253 | 70.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jyrki Kivinen
2. Heikki Mannila

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
473	Sampling Large Databases for Association Rules	1996	VLDB	0.0002233798
2,266	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	9.1540815e-05
6,286	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1280225e-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
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
5,965	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.2518232e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,523	Analysis and Application of Adaptive Sampling	2000	PODS	4.331052e-05
473	Sampling Large Databases for Association Rules	1996	VLDB	0.0002233798
7,251	Learning to Sample: Counting with Complex Queries	2020	VLDB	4.7890519e-05
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
315	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.0002802103
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868