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.3162039e-05
Overall Rank: 4,250 | 70.47%
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.00022304724
2,271	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	9.1467959e-05
6,285	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1231886e-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.00051431888
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
5,971	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.2466276e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
473	Sampling Large Databases for Association Rules	1996	VLDB	0.00022304724
9,524	Analysis and Application of Adaptive Sampling	2000	PODS	4.3268997e-05
7,246	Learning to Sample: Counting with Complex Queries	2020	VLDB	4.7847433e-05
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
291	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00028778973
8,345	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5361313e-05
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121