要素U (最初はサイズが不明) のセットがあり、 n << |のランダム サンプルを生成したいと考えています。う| 要素。これには、ストリーム サンプリングが適切に機能します。
Uをいくつかのサブセットに分割し、各サブセットのランダム サンプルを取得したときに問題が発生します (各サンプルにはk <= n要素が含まれますが、通常はk = n )。また、各サブセットに含まれる要素の数も知っています。これらのサンプルを (できれば一度に 2 つのサンプルをマージして) 1 つのサイズnサンプルに結合する方法を知りたいです。
別の言い方をすれば、異なるセットAとB、およびランダム サンプルaとbが与えられた場合、 cがA ∪ Bのランダム サンプルであり、 cのサイズを指定できるように、 c ⊆ a ∪ bを作成したいと思います(通常 | c | は | a | とほぼ同じサイズになります)。
まだUからサンプリングしているように振る舞います。サンプルを選択するには、最初にサンプルの元となるサブセットS_iを選択します。相対的なS_iサイズに比例してこれを行います。したがって、S_1がUの20％である場合、20％の確率でS_1からサンプルを選択します。サブセットを選択したら、そのサブセットからサンプルのいずれかを取得して、最終サンプルで使用できます。k値がn未満の場合、これは問題に遭遇する可能性がありますが、通常k = nの場合、おそらく問題にはなりません。
これをAとBの定式化の観点から考えると、次のようにcを構築します。A | / | A∪B | _ _ 次のサンプルを;から取得します。確率で| B | / | A∪B | _ _ = 1-（| A | /| A∪B |） bから次のサンプルを取得します。（上記で述べたように、| a |がn *（| A | /| A∪B |）（および| bに相当するもの）よりもいくらか大きくない場合、これは問題にぶつかる可能性があります。|）しかし、そうだとすれば、やりたいことができるかどうかは私にはわかりません。）これにより、一度に2つのサブセットのサンプルを作成できます。
|A|==|B|の場合 |a|==|b| であれば、まったく心配する必要はありません。aUb から通常のランサム サンプリングを行うだけです。