MULTI-LEVEL RESERVOIR SAMPLING OVER DISTRIBUTED DATABASES AND DISTRIBUTED STREAMS

摘要

A system and method for random sampling of distributed data, including distributed data streams. The system and method use a multi-level reservoir sampling technique that leverages the conventional reservoir sampling algorithm for distributed data or distributed data streams. The method establishes an intermediate reservoir for each distributed data source or data stream and populates the intermediate reservoirs with a sample of data elements received from each distributed data source or data stream. A final reservoir is established and data elements are randomly selected from each one of the intermediate reservoirs to populate the final reservoir.