k-d trees (k-dimensional tree)

k次元空間をいくつかの部分空間に分けて考えるデータ構造．

Nearest Neighbor Search(NNS)などで用いられることが多い．

k次元を2分し二分木として表現することで，探索を0(log n)，ワーストO(n)で探索可能．

参考：http://en.wikipedia.org/wiki/Kd-tree