Use of Sampling 1. Initial hypotheses from sample

• Sample entire database.
• construct H based on sample
• correct H: climb bottom up to eliminate h where d(h)=0, then continue search.

 
2. Sampled joins

use only a sample of each join

use error probability guarantees to make sure you do not miss one of the best k hypotheses  

---