k-d treeとは、K-Dimensional treeの略で、K次元のデータの最近傍点を探索するための手法です[1]。検索対象のデータ数を
とした時、データの次元数が大きすぎると線形探索と計算量が変わらないそうです[1]。なお線形探索とは、全探索の１種で一個ずつ検索対象をチェックするアルゴリズムを指します[2]。木の形成は、下記の２つの図にあるように、各ノードのデータを２つに分割していくことで行います。分割は、深さに対応した軸（例えば３次元のデータなら、１層目はX、２層目はY、３層目はZ、４層目はX）の値を比較することで行います。どの様な比較をするかは、実装に依ってことなります。これ以上分割できない/しない所までいったら、木の形成は完了です。
調べた限りは書いていないのですが、深さに対応した軸は自ら決めてよいのだと思います。これによっても、もちろん探索スピードは変化するかと思います。特にN次元のデータなんだけれども特定の軸方向にはデータが０ or 殆ど変わらない場合は、その軸を無視してもいいのだと思います。
出展:[2]
出展: [3]
