algorithm - 分位数を動的に監視するアルゴリズム

Question

一部のデータの分位点を推定したい。データが大きすぎて、メモリに収まりません。そして、新しいデータが入り続けています。非常に限られたメモリと計算で、これまでに観測されたデータの変位値を監視するアルゴリズムを知っている人はいますか? P2 アルゴリズムは便利だと思います。しかし、非常に裾の重い分散している私のデータではうまく機能しません。

Answer 1

値スペースをビンに分割することを検討してください。各ビンには、範囲内の値のカウントが含まれています。

探している分位数が期待されるポイントの周りでビンを小さくすることを試みることができます。

ビンの数を十分に大きくすると、これは非常にうまく機能するはずです。