Simple Sampling Techniques for Discovery Science

Osamu WATANABE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.1   pp.19-26
Publication Date: 2000/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Issue on Surveys on Discovery Science)
Category: 
Keyword: 
random sampling,  the Chernoff bound,  the Hoeffding bound,  the central limit theorem,  sequential sampling,  adaptive sampling,  

Full Text: PDF>>
Buy this Article




Summary: 
We explain three random sampling techniques that are simple but widely applicable for various problems involving huge data sets. The first technique is an immediate application of large deviation bounds. The second and the third ones are sequential sampling or adaptive sampling techniques. We fix one simple problem and explain these techniques by demonstrating algorithms for this problem and discussing their correctness and efficiency.