データストリームのランダムなサブセットを保持する方法は？

Question

私は自分のサーバーを流れるイベントのストリームを持っています。私はそれらのすべてを保存することはできませんが、私は定期的にいくつかを集約して処理したいと思います。ですから、ストリームのサブセットは、見たことのあるすべてのものをランダムにサンプリングしたままにしておきたいのですが、最大サイズに制限されています。

新しいアイテムごとに、ストアドセットに追加するかどうか、または破棄するかどうかを決定するアルゴリズムが必要です。私がそれを追加して、すでに私の限界に達しているなら、古いアイテムの1つを追い出すアルゴリズムが必要です。

明らかに、これは私が自分の制限を下回っている限りは簡単です（すべて保存してください）。しかし、一度限界を過ぎてしまえば、古いアイテムや新しいアイテムに偏っていなくても、どのようにして良いランダムサンプリングを維持できますか？

おかげで、

Answer 1

this paperは、あなたが探しているもの、それはあなたの検索で良い出発点であってもよい、正確ではありませんが。

Answer 2

は、先入れ先出し（FIFO）キューにサンプルを格納します。

サンプル間で非常に多くのイベントのサンプリングレートを設定するか、イベントのパターンに応じてこれを少しランダム化します。

すべてのn番目のイベントを保存するか、レートによって通知されるたびに、キューの最後までスティックします。

サイズが大きすぎる場合は、トップを外します。

Answer 3

各イベントを記録し、そのイベントをインデックス可能なデータ構造に格納する確率を割り当てます。構造体のサイズがしきい値に達すると、ランダムな要素を削除して新しい要素を追加します。 Rubyでは、これを行うことができます：

@storage = [] 
prob = 0.002 

while (message = getnextMessage) do 
    @storage.delete((rand() * @storage.length).floor) if @storage.length > MAX_LEN 
    @storage << message if (rand() < prob) 
end 

これはイベントが発生したときのあなたの最大サイズと非バイアスに対応します。また、保存された要素をバケットに分割し、複数の要素を持つバケットから要素を削除することで、削除される要素を選択することもできます。バケツメソッドでは、たとえば、1時間ごとの1つを保持することができます。

また、サンプリング理論はBig Mathです。あなたがこれについての素人のアイデア以上を必要とする場合は、あなたの地域の資格のある数学者に相談する必要があります。

Answer 4

これは、受け取る予定のイベントの総数がわからず、サブセット内に最小数の要素が必要ないと仮定しています。

arr = arr[MAX_SIZE] //Create a new array that will store the events. Assuming first index 1. 
counter = 1 //Initialize a counter. 

while(receiving event){ 
    random = //Generate a random number between 1 and counter 
    if(counter == random){ 
    if(counter <= MAX_SIZE){ 
     arr[counter] = event 
    } 
    else{ 
     tmpRandom = //Generate a random number between 1 and MAX_SIZE 
     arr[tmpRandom] = event 
    } 
    } 
    counter =+ 1 

} 

Answer 5

これは一般的なインタビューの質問です。

簡単な方法の1つは、n番目の要素を確率k/n（または1のいずれか小さい方）で保存することです。新しいサンプルを保存するために要素を削除する必要がある場合は、ランダム要素を削除します。

これにより、n個の要素の均一なランダムなサブセットが得られます。あなたがnを知らない場合は、それを見積もり、ほぼ一様なサブセットを得ることができます。

Answer 6

これはランダムサンプリングと呼ばれます。出典：http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k]; // result 
integer i, j; 

// fill the reservoir array 
for each i in 1 to k do 
    R[i] := S[i] 
done; 

// replace elements with gradually decreasing probability 
for each i in k+1 to length(S) do 
    j := random(1, i); // important: inclusive range 
    if j <= k then 
     R[j] := S[i] 
    fi 
done 

まともな説明/証明：あなたは最小サブセットのサイズをhttp://propersubset.com/2010/04/choosing-random-elements.html