Problem Statement Randomly choosing k items from a list S containing n items where n is too large or unknown. Method: Reservoir Sampling Steps: keep the first item in memory for the next item i (i > 1) keep the new item with probability 1/i ignore the new item with probability 1 – 1/i It is easy to prove that when there are n items, … Continue reading Reservoir sampling