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: h3b3b26408a593df0
Venue: PODS
Year: 1994
Pagerank: 6.4726631e-05
Overall Rank: 4,679 | 68.55%
DOI: 10.1145/182591.182601

Incoming Non-self Citations Over Time

Authors

1. Jyrki Kivinen (University of California Santa Cruz)
2. Heikki Mannila (University of Helsinki)

BibTeX Citation

@inproceedings{kivinen_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{The Power of Sampling in Knowledge Discovery}},
        url = {https://dl.acm.org/doi/10.1145/182591.182601},
        doi = {10.1145/182591.182601},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kivinen, Jyrki and Mannila, Heikki},
        year = {1994}
}

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.00017673931
2,904	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	7.8801067e-05
5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9718136e-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
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
346	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020329113
6,994	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.6266148e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	473	Sampling Large Databases for Association Rules	1996	VLDB
2	9,849	Analysis and Application of Adaptive Sampling	2000	PODS
3	7,166	Learning to Sample: Counting with Complex Queries	2020	VLDB
4	36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD
5	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
6	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
7	492	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD
8	8,347	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR
9	175	Simple Random Sampling from Relational Databases	1986	VLDB
10	1,011	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS