Weighted Reservoir Sampling: Randomly Sampling Streams

Abstract

Reservoir sampling is a family of algorithms that, given a stream of N elements, randomly select a K-element subset in a single pass. Usually, K is defined as a small constant, but N need not be known in advance.