MLB - その１。

ずいぶん、勘違いをしていたみたいなので、しっかり論文を読む事にした。

階層がいくつかあり、上位階層（下位階層よりかなり少ない）が下位階層のある範囲に格納した要素数をカウントしていて、最小ポテンシャル点を探索する際にヒントになるというものだと認識していた。レベルをいくつかにすべきかは、最大枝長で決めるという単に１レベルバケットを拡張したものかと思っていたのだが、実際にはそうではなかった。

「階層数＝レベル数」、「最大枝長で最大レベルは定まる」ことは同じだが、上位階層と下位階層の関係が異なっている。


まずは、基礎となっている部分から見いこう。図を用いた方がわかりやすいので、こちらを参照していただくとよいだろう。

まずは図の見方になるが、以下のようになっている。
・十進数の数字は MLB に格納された点のポテンシャルになっている。
・十進数の数字のビット表現（２進数表現）として、最下位ビット～最上位ビットとなっている。今回はそれぞれ 0 ～ 4 レベルとする。


次に挿入操作について。

１、まず最後に MLB から取り出した点のポテンシャルを覚えておく。
　　ex) 10

２、１のポテンシャルから、どれだけビットが変化したものを挿入するかをチェックする。
　　その際、変化したビットのうち、最大のレベルとそのビットを確認。
　　ex) 10 と 14 であれば、01010 と 01110 なので、2-level で、1 となる。

３、２で求めた レベルとビットから、挿入するバケットを決定する。
　　ex) 2-level, 1 --> B(2,1)


他の要素も同様に決定すると、B(0, 1), B(2, 1), B(3, 0) となる。