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: 1018
Venue: PODS
Year: 1994
Pagerank: 6.6181342e-05
Overall Rank: 4,584 | 68.56%
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
462	Sampling Large Databases for Association Rules	1996	VLDB	0.00018065337
2,872	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	8.0104819e-05
5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	6.1062071e-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
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
6,847	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.7554494e-05

Semantically Similar Papers

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