K近傍kd木

kd木を使って指定した点から距離が近い順にK個の点を探索する
プログラムのテストです。最近傍探索を少し変えるとできました。

マウスクリックした10近傍の点を探す。

wikiを参考に作りました。
http://ja.wikipedia.org/wiki/Kd%E6%9C%A8

最近傍探索、二次元、100万点×1000回のテストでは、
・kd木：16msec
・線形探索（全探索）：160秒
でした。１万倍の速度です。K近傍探索だともっと差がつくかも。
すごい発明だと思います。
Ｋ近傍探索はいろんな場所で使えると思いますので、
いつでも使えるようになっておいて損はないと思います。
例えば、Webのコンテンツ検索とか内部で使っているかもしれません。
（画像を特徴量ベクトルに変換して照合する）

次元数が増えると効率が悪くなるとのことらしいですが、
どうなんでしょうかね。