kD-tree - おべんきょうwiki

kD-tree

k Dimensional Tree のこと．
要するに多次元ベクトルを二分木で保持するのだが
そのときのキーとなる要素を深さで決める．
例えば二次元なら縦，横，縦，横．．．と割っていくことになる．

kD-treeを用いた最近傍探索

木構造を構築するときと同様のやり方で最近傍探索を高速化できる．
が，実際には高次元になるにつれて探索効率が悪くなる．
特に最悪時にはオーダーが全探索と同じになるため，オーバーヘッドを考慮すると全探索より遅い．
高次元ではANNやLSHのような手法を使うべき．

参考リスト

• http://en.wikipedia.org/wiki/Kd-tree