Multiplexed Reservoir Sampling

Xixuan Feng Arun Kumar Benjamin Recht Christopher Ré: "Towards a Unified Architecture for in-RDBMS Analytics", In. Proc, SIGMOD, 2012.

だいぶ昔に読んだ論文だけどIn-database AnalyticsのBismarckの論文にMultiplexed Reservoir Samplingというのがあって、それを使うと収束が早いというのが？に思ったので書く。

まず、Reservoir samplingについての前提知識を必要とするのでWikipediaのエントリを参照のこと。 次のようなアルゴリズムで最後に残ったsamplesはランダムなものになっているサンプリング手法。

Multiplexed Reservoir Samplingの概念図は次のとおり。