MIT
34
Random Sampling
lGeneral tool for
faster algorithms:
»pick a small, representative sample
»analyze it quickly (small)
»extrapolate to original (representative)
lSpeed-accuracy
tradeoff
»smaller sample means less time
»but also less accuracy