最近傍探索

最近傍探索（）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（）、類似探索（）、最近点探索（）などとも呼ぶ。問題はすなわち、距離空間 "M" における点の集合 "S" があり、クエリ点 "q" ∈ "M" があるとき、"S" の中で "q" に最も近い点を探す、という問題である。多くの場合、"M" には "d"次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。
ドナルド・クヌースは、"The Art of Computer Programming" Vol.3（1973年）で、これを郵便局の問題で表した。これはすなわち、ある住所に最も近い郵便局を求める問題である。
解法.
最近傍探索問題の解法としては、様々なものが提案されている。そのアルゴリズムの品質と利便性は、クエリへの応答にかかる時間とデータ構造が使用するメモリ量で判断される。直観的には、次元の呪いと呼ばれる特徴があるため、あらゆる場合に最適な解法は存在しないと言われている。
線形探索.
最も単純な解法は、クエリで示された点とデータベース内の他の全ての点との距離を全部計算して、最も近いものを探すことである。データベースが小さい場合は問題ないが、その大きさや次元が増大すると急激に遅くなる。線形探索の処理時間は O("Nd") であり、"N" は "S" の基数、"d" は "S" の次元である。検索時にデータ構造は特に必要ないので、データベース以外の余分なメモリ消費はない。
空間分割.
1970年代から、この問題に分枝限定法が適用されるようになった。ユークリッド空間の場合、この手法は空間索引または空間アクセス法として知られている。NNS問題を解くための空間分割法もいくつか考案された。最も単純な手法としてはkd木がある。これは、探索空間を再帰的に半分に2分割していくものである。クエリは、この木を根から葉に向かって辿っていくことで処理される（各ノードでどちらに行くかをクエリの内容と比較して判断する）。一定次元でのクエリ処理時間は O(log "N") となる。R木というデータ構造も最近傍探索用に設計された。
一般の距離空間における分枝限定法の適用例として、やがある。
局所性鋭敏型ハッシュ.
局所性鋭敏型ハッシュ（LSH）は、距離空間内の各点に距離空間的操作を施すことで、グループ分けする技法である。ある距離尺度で互いに近い点は同じグループになる確率が高くなる。
応用.
最近傍探索は、以下のような様々な分野で使われている。