これがこれに適したフォーラムであるかどうかは完全にはわかりません。
小さなデータベース クラスター (4 ボックス) があり、各マシンにはデータセット全体のシャードがあります。
特定のデータ ポイントの四分位数を計算する必要がありますが、一度にデータセット全体にアクセスすることなく実行する必要があります。
これは可能ですか？
編集私は正確な答えを好むでしょうが、合理的な近似もおそらくうまくいくでしょう.
質問する
548 次
2 に答える
1
その場合、正確な四分位数を計算することはできませんが、QDigest アルゴリズムが問題を解決します。かなり良い近似値を得ることができます。これを一度確認できます。Java 実装はhttps://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/quantile/QDigest.javaで入手できます。
これにより、各クラスターで QDigest データ構造を作成できます。データセットの四分位数の要約を維持する超圧縮データ構造。さらに、これらのデータ構造の結合を実行して、問題を解決できます。
したがって、各クラスターで QDigest のインスタンスを作成し、結果を組み合わせるには、クラスターごとにこれらのインスタンスの結合を実行するだけで、四分位数の適切な近似値が得られます。
詳細については、QDigest の論文をたどることができます。
于 2014-01-13T11:42:36.623 に答える