BFPRT AlgorithmBFPRT Algorithm

先日ローランギャロスにテニス観戦に行ってきました。松浦です。
フランスでは全仏オープン決勝(ジョコビッチ vs ナダル)があり、先週から
INRIAのラボでも昼食時はテニスの話題が沢山出て盛り上がっています。

今日はBFPRTアルゴリズムを紹介したいと思います。
BFPRTは最悪時でもO(N log N)を保証する中央値ソートの一種です。

スライドを用意したので、詳細は上記の資料に譲るとして、
固定長の部分配列に分割して中央値群の中央値を選択していく過程を見たり、
中央値の近似値と真の中央値のずれの原因を理解したり、そういう事が
他の所でもヒントになればと思い紹介しました。

BFPRT algorithm

View more presentations from Satoshi MATSUURA

例えばセンサネットワークにおいてデータを収集する過程で、
最大値、最小値、中央値を集めたいとします。精度はそこそこで良いので、
出来るだけ集約して転送データ量を減らしたい環境を想定すると、
ソートしないまでもBFPRTを知っていたら、収集過程と精度の関係を
見積もることも容易です。他にも応用例を色々と考えて見てください。

by MATSUURA Satoshi