最近傍探索とは？わかりやすく解説

最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 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木というデータ構造も最近傍探索用に設計された。

一般の距離空間における分枝限定法の適用例として、VP木やBk木がある。

局所性鋭敏型ハッシュ

局所性鋭敏型ハッシュ（LSH）は、距離空間内の各点に距離空間的操作を施すことで、グループ分けする技法である。ある距離尺度で互いに近い点は同じグループになる確率が高くなる。

派生

k近傍法は、クエリに最も近い方から k 個の近傍を特定する。
近似最近傍探索 (英: approximate nearest neighbor, ANN) は、次元の呪いへの対策として最近特に人気がある。
最近傍距離比 (英: nearest neighbor distance ratio) とは、距離の絶対値ではなく距離と距離の比を用いる方式。内容に基づく画像検索（CBIR）で使われることがある。より一般的には、いくつかのマッチング問題と関連する。
最近点対問題 (英: closest pair problem)とは、点集合の中から最も近い距離の点のペアを1組捜すアルゴリズムであり、 $O(n\log n)$

最近傍探索とは？ わかりやすく解説